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.

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

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.

Answer 5

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 6

Charcoal, 43 bytes

Ｎθ⊞υ¹Ｗ¬⊙01⊙υ⬤…⮌υθ№⌕Ａ⮌⍘ξ²×κθν⊞υΣ✂υ±²Ｌυ¹Ｉ⁻Ｌυθ

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

Ｎθ

Input the desired number of bits.

⊞υ¹

Start with F(1)=1.

Ｗ¬⊙01⊙υ⬤…⮌υθ№⌕Ａ⮌⍘ξ²×κθν

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.

⊞υΣ✂υ±²Ｌυ¹

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

Ｉ⁻Ｌυθ

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

Bit twiddling is faster but longer at 65 bytes:

Ｎθ⊞υ¹≔⁰η≔⁰ζＷ¬∨№⍘η²×1θ№⍘ζ²×0θ«⊞υΣ✂υ±²≔↨υ⁰η≔ηζＦ…⮌υθ«≧＆κη≧｜κζ»»Ｉ⁻Ｌυθ

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