perplexus.info :: Sequences : Bits adjacent to 1

Bits adjacent to 1 (Posted on 2022-11-15)

A string of N binary bits has the property that every bit is adjacent to a '1' bit. An example for N=12 is 111011011110.
Note that 010 is not a valid sequence, the 1 bit is not adjacent to any other 1 bit.

How many valid binary sequences of length 20 exist?
What is the smallest length N such that there are over a hundred thousand valid binary sequences?

See The Solution Submitted by Brian Smith

Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

observations

| Comment 3 of 5 |

Call the sequence A.

The even numbered terms of A are the squares of Fibonacci numbers. Specifically term A(2n)=F(n+1)^2.

The odd numbered terms are one more than the product of the square roots of the terms preceding and following.

A(2n-1)=sqrt(A(2n)*A(2n+2))+1

=F(n+1)*F(n+2)+1

The recurrence relation given by OEIS (I'll prove it if I have time)

A(n)=A(n-1)+A(n-3)+A(n-4)

Posted by Jer on 2022-11-15 12:45:37

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info