I was playing with the Fibonacci sequence in binary like so (note that the binary representations are written here from smallest bit to largest bit):
1 1 1 1 01 2 11 3 101 5 0001 8 1011 13 10101 21 010001 34 111011 55 1001101 89 00001001 144 10010111 233 ...
and I noticed that it took until the 11th Fibonacci number (1-indexed) to find a 2-by-2 square of the same bit:
1 00 1101 0 00 01001
I then wondered: in what row does the first n-by-n square filled with the same bit start?
Given an integer n, what is the index of the first Fibonacci number that contains part of an n-by-n square filled with the same bit?
- You can have the Fibonacci sequence be either 0- or 1-indexed
- You do not have to worry about invalid input
- You may use any standard I/O method
- Standard loopholes are forbidden
- This is
code-golf, so the shortest code in bytes per language wins
Input (1-indexed) -> Output (0-indexed/1-indexed) 1 -> 0/1 2 -> 10/11 3 -> 22/23 6 -> 382/383 8 -> 4570/4571
The answers can use one of the following input/output methods, and can be 0- or 1-indexed:
- Given some index n it can return the n-th entry of the list.
- Given some index n it can return all entries up to the n-th one in the sequence.
- Without taking any index, it can output all entries by e.g. ...
- ...printing them one by one (potentially infinitely) or...
- ...returning a list (lazy if the sequence is infinite) or...
- ...returning a generator that represents the whole sequence.