Fibonacci Binary Squares

Question

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.

• Kip the Malamute: The first 8x8 square consists of 1s, unless I massively screwed up my implementation somewhere.
• Kip the Malamute: If it makes a difference to anyone, there IS an upper bound for each value. As for how to determine it, I'll leave it as an exercise to the reader.
• Luis Mendo: In what is the index of the first Fibonacci number that contains part of an n-by-n square filled with the same bit?, what do you exactly mean by part? Don't you mean a full square?
• Kip the Malamute: Unless n=1, any square of size n will lie across multiple Fibonacci numbers. I just want to know what the index of the first one of those is.
• Luis Mendo: I see now. Thanks

Answer 1

Wolfram Language (Mathematica), 124 bytes

(n=k=#;While[!Or@@(!FreeQ[Split@Total@PadLeft@IntegerDigits[Fibonacci@t[n-1+b,{b,k}],2],#]&/@{0~(t=Table)~k,k~t~k}),n++];n)&

Try it online!

Answer 2

JavaScript (Node.js), 143 bytes

Expects a BigInt. The output is 0-indexed.

n=>eval("for(i=a=[],g=(p,q=a.reduce((q,v,i)=>i<n?p?q&v:q|v:q))=>q?(p?~q:q)&~-(1n<<n)&&g(p,q/2n):1n;g(a=[++i>2?a[0]+a[1]:1n,...a])&g(););i-[n]")

Try it online!

Commented

This is a version without eval() for readability.

n => { // n = input
for( // main loop:
 i = // i = iteration counter
 a = [], // a[] = Fibonacci sequence in reverse order
 g = ( // g is a helper function taking:
 p, // p = flag (false: test 0s, true: test 1s)
 q = a.reduce( // q = bitmask to be tested
 (q, v, i) => // for each value v at index i in a[]:
 i < n ? // if i is less than n:
 p ? q & v // if p is set, update q to q AND v
 : q | v // otherwise, update it to q OR v
 : // else:
 q // leave q unchanged
 ) // end of reduce()
 ) => //
 q ? // if q is not 0:
 (p ? ~q : q) // take either q or NOT(q) depending on p
 & ~-(1n << n) // isolate the n least significant bits
 && // if the result is not 0 ...
 g(p, q / 2n) // ... try again with q right-shifted by 1
 : // else:
 1n; // stop with a truthy value
 g( // first call to g with a truthy flag:
 a = [ // update a[]:
 ++i > 2 ? // increment i; if it's greater than 2:
 a[0] + a[1] // append the sum of the first 2 terms
 : // else:
 1n, // append 1
 ...a // followed by the existing terms
 ] //
 ) & g(); // second call to g with a falsy flag
); // end of for
return i - [n] } // return the final position

Answer 3

Raku, (削除) 105 (削除ここまで) 101 bytes

->\n{(1,1,*+*...{@_.tail(n)».base(2).flip~~/^(\d*)((\d)0ドル**:{n-1})\d*[' '\d**{0ドル.chars}1ドル\d*]*$/})-n}

Try it online!

Edit: I had to use a workaround for an apparent Raku bug. Later I found that the bug has already been reported, and the bug report suggested a different workaround, four bytes shorter than mine.

This is an anonymous function that takes a single argument n. The body is just a lazy Fabonacci generator with a complicated ending condition between the braces:

(1, 1, * + * ... { ... }) - n

Subtracting n from the sequence coerces it to a number, its length; the difference is returned.

Anyway, as for the ending condition:

• @_.tail(n) looks at just the last n elements of the Fibonacci sequence.
• ».base(2) converts each number to its binary representation.
• .flip coerces that sequence of strings to a single string, joining the individual elements with spaces, then reverses the entire string.
• ~~ / ... / matches that space-delimited string of bit strings against the slash-delimited regex.
• ^ is the beginning of the string.
• (\d*) is zero or more digits. This is the part that comes before the square of identical bits. It's captured in group 0 so that we can check for prefixes of the same length on the following lines.
• ((\d) 0ドル **: {n-1}) is a sequence of n of the same digit, captured in group 1.
• \d* matches zero or more digits to the right of the square of bits.
• [' ' \d ** {0ドル.chars} 1ドル \d* ]* matches, zero or more times, a space, then a digit prefix consisting of the same number of characters as the prefix on the first row, then the row of identical digits in group 1, then zero or more other digits.
• $ is the end of the string.

Answer 4

Python, 182 bytes

def e(n,*l):
 r=[*zip(*[bin(i)[:1:-1]for i in l[:n]])]
 if len(r)>n>=1==min(len({*sum(r[i:i+n],())})for i in range(len(r)-n)):print((len(l)-n)*(n>1));n+=1
 e(n,l[0]+l[1],*l)
e(1,1,1)

Attempt This Online!

Prints the 0-based indices infinitely. (Contains a particularly horrible kludge to deal with n=1; let me know if you have a better solution.)

Answer 5

05AB1E, (削除) 38 (削除ここまで) 35 bytes

∞<.ΔIÝ+Åf2вí2FøI"üÿ"δ.V}Aδ.ý ̃ÅγIn@à

Given \$n\$, it'll output the 0-based value.

Try it online or verify the first 5 test cases.

Pretty slow. Can barely output \$n=6\$ in about 55 seconds on TIO.

Explanation:

∞ # Push an infinite positive list: [1,2,3,4,5,...]
 < # Decrease it to a non-negative list: [0,1,2,3,4,...]
 .Δ # Pop and find the first value that's truthy for:
 IL # Push a list in the range [1,input]
 + # Add the current value to each in this list
 Åf # For each of these values, get their 0-based Fibonacci number
 2в # Convert each inner Fibonacci number to a binary-list
 í # Reverse each inner list
 2FøI"üÿ"δ.V} # Create overlapping input by input blocks:
 2F } # Loop 2 times:
 ø # Zip/transpose; swapping rows/columns
 I # Push the input-integer
 "üÿ" # Push this string, replacing `ÿ` with the input
 δ # Map over each inner row with this string as argument:
 .V # Evaluate the string as 05AB1E code,
 # where `ü#` creates overlapping items of size `#`
 δ # Map over each row of input by input sized blocks:
 A .ý # Intersperse it with the lowercase alphabet (or any rubbish value)
 ̃ # Then flatten it to a single list
 Åγ # Run-length encode it; pushing the list of values and list of lengths
 In # Push the squared input
 @ # Check for each value whether it's >= this squared input
 à # Get the flattened maximum to check if any is truthy
 # (which means there was an input by input sized block consisting of
 # the same bit)
 # (after which the found index is output implicitly as result)

Minor note: Aδ.ý ̃ÅγIn@à instead of just εε ̃Ë}}à (nested map over the blocks εε...}}; flatten ̃; check if all bits are the same (Ë); any à) is for the first few binary representations of Fibonacci numbers, which are smaller than an \$n\times n\$ block. The 2FøI"üÿ"δ.V} will in those cases result in an empty (nested) list, which is unfortunately truthy for the Ë check.

• Kip the Malamute: Honestly, it's probably not THAT slow - at least not compared to how slow golfed code often is. My implementation code times out calculating n=9 on TIO.

Answer 6

Charcoal, 43 bytes

×ばつκθν⊞υΣ✂υ±2Lυ1I−Lυθ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the desired number of bits.

⊞υ1

Start with F(1)=1.

×ばつκθν

Check the last n Fibonacci numbers to see whether there is an index where they all share an overlapping match of a string of either all n 0s or all n 1s in their binary representations.

⊞υΣ✂υ±2Lυ1

Calculate the next Fibonacci number. Unfortunately I have to start with just one Fibonacci number which makes the formula much longer than normal.

I−Lυθ

Calculate the 0-based index of the first of the last n Fibonacci numbers.

Bit twiddling is faster but longer at 65 bytes:

×ばつ0θ«⊞υΣ✂υ±2≔↨υ0η≔ηζF...⮌υθ«≧&κη≧|κζ»»I−Lυθ

Try it online! Link is to verbose version of code. Explanation: Calculates Fibonacci numbers, taking both the logical Or and logical And of the last n Fibonacci numbers, until either the logical Or contains n 0s or the logical And contains n 1s in their binary representation. Somewhat verbose because I can't take the logical Or or And of a list.

Answer 7

Python 3.8, (削除) 262 (削除ここまで) (削除) 260 (削除ここまで) 205 bytes

Function s that accepts n as input (1-indexed) and returns the index 1-indexed. Quite slow, but in theory it works!

Edit:

• -2 bytes thanks @The Thonnu
• -54 bytes thanks @Neil
• -1 byte: moved i as optional function argument

f=lambda x:x>1and f(x-1)+f(x-2)or x
def s(n,i=0):
 while 1:
 i+=1;b=[bin(f(i+_))[::-1]for _ in range(n)]
 for d in'01':
 for p in range(i):
 for k in b:
 if k[p:p+n]!=d*n:break
 else:return i

Try it online!

---

Commented code (original version):

# lambda function that computes the Fibonacci numbers
f=lambda x: x>1 and f(x-1) + f(x-2) or x
# main function
def s(n):
 # index of the i-th Fibonacci number that is evaluated
 i = 0
 
 while 1:
 
 i + =1
 # list of binary representations of n Fibonacci numbers
 b = [bin(f(i+_-1))[2:][::-1] for _ in range(n)]
 
 # check both digits
 for d in '01':
 
 # find digit at each position in binary repr
 for p in range(len(b[0])):
 # find if repeated digit is substring of binary repr
 if b[0][p:].find(d*n) >= 0:
 
 # search in following Fibonacci numbers
 for k in b[1:]:
 
 # if substring found at different position break loop
 if k[p:].find(d*n) != 0: break
 
 # for loop is terminated, found all substrings at same positions
 else: return i

• The Thonnu: 260
• Neil: Your code has a logic error in that it doesn't correctly compare the index of the substring of the ith element. I fixed that while golfing your code down a bit: Try it online!