[seqfan] Significance of sequence relating powers of two and Fibonacci numbers

Alonso Del Arte alonso.delarte at gmail.com
Fri Jul 7 21:45:48 CEST 2023

A3714 gives the numbers such that their binary representations have no
consecutive 1 bits. Given a length *n*, a very loose upper bound for the
number of numbers in A3714 less than 2^*n* is 2^*n* itself. Allocating an
array with that upper bound wastes A8466(*n*) array slots.

But, at one point, pondering this "binary strings" problem, I got this
sequence: 0, 3, 11, 30, 73, 167, 368, 791, 1671, 3486, 7205, 14787, 30184,
etc., the formula for which also involves the powers of two and the
Fibonacci numbers: 2^*n* − *F*(n + 3). I didn't find it in the OEIS, so I
just assumed I had made some mistake along the way and went to sleep. The
next day, though, I did figure out the formula for the sequence and I
believe I did calculate the sequence correctly before, but now I just can't
figure out its significance.

Does this sequence have any meaningful connection to the binary strings

Alonso del Arte
Author of *Java with TDD from the Beginning
Get it for 75% off with coupon code *SSW75*
before July 31, 2023

More information about the SeqFan mailing list