I think I have found a way of solving the problem, but I can't construct a formal proof. The solution I made is written in Java, and it uses a counter 'n' to count how many list/array accesses it does. So n should be less than or equal to stringLength*log(stringLength) if it is correct. I tried it for the numbers 0 to 2^22, and it works.

It starts by iterating over the input string and making a list of all the indexes which hold a one. This is just O(n).

Then from the list of indexes it picks a firstIndex, and a secondIndex which is greater than the first. These two indexes must hold ones, because they are in the list of indexes. From there the thirdIndex can be calculated. If the inputString[thirdIndex] is a 1 then it halts.

public static int testString(String input){ //n is the number of array/list accesses in the algorithm int n=0; //Put the indices of all the ones into a list, O(n) ArrayList<Integer> ones = new ArrayList<Integer>(); for(int i=0;i<input.length();i++){ if(input.charAt(i)=='1'){ ones.add(i); } } //If less than three ones in list, just stop if(ones.size()<3){ return n; } int firstIndex, secondIndex, thirdIndex; for(int x=0;x<ones.size()-2;x++){ n++; firstIndex = ones.get(x); for(int y=x+1; y<ones.size()-1; y++){ n++; secondIndex = ones.get(y); thirdIndex = secondIndex*2 - firstIndex; if(thirdIndex >= input.length()){ break; } n++; if(input.charAt(thirdIndex) == '1'){ //This case is satisfied if it has found three evenly spaced ones //System.out.println("This one => " + input); return n; } } } return n; 

}

additional note: the counter n is not incremented when it iterates over the input string to construct the list of indexes. This operation is O(n), so it won't have an effect on the algorithm complexity anyway.