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?
Task
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?
Rules
- 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
Test cases:
Input (1-indexed) -> Output (0-indexed/1-indexed)
1 -> 0/1
2 -> 10/11
3 -> 22/23
6 -> 382/383
8 -> 4570/4571
Format:
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.