and 1 contributors

# NAME

Math::NumSeq::Fibbinary -- without consecutive 1 bits

# SYNOPSIS

`````` use Math::NumSeq::Fibbinary;
my \$seq = Math::NumSeq::Fibbinary->new;
my (\$i, \$value) = \$seq->next;``````

# DESCRIPTION

The fibbinary numbers 0, 1, 2, 4, 5, 8, 9, 10, etc, being integers which have no adjacent 1 bits in binary.

``````    i    fibbinary, and in binary
---   ------------------------
0        0           0
1        1           1
2        2          10
3        4         100
4        5         101
5        8        1000
6        9        1001
7       10        1010
8       16       10000
9       17       10001``````

For example at i=4 fibbinary 5 the next fibbinary is not 6 or 7 because they have adjacent 1 bits (110 and 111), the next is 8 (100).

## Zeckendorf Base

The bits of the fibbinary numbers encode Fibonacci numbers used to represent i in Zeckendorf style Fibonacci base. In this system an integer i is represented as a sum of Fibonacci numbers,

``    i = F(k1) + F(k2) + ... F(kn)``

For example, counting F(0)=1, F(1)=2, etc,

``    20 = 13+5+1 = F(5)+F(3)+F(0)``

The k's are then assembled as 1 bits in binary to encode the representation,

``    fibbinary(20) = 2^5 + 2^3 + 2^0 = 41``

The Zeckendorf form takes the highest Fibonacci F(k) <= i, subtracts that from i, and repeats. The spacing between Fibonacci numbers means after subtracting F(k) the next cannot be F(k-1), only F(k-2) or less, giving no adjacent 1 bits in the fibbinary numbers.

# FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for the behaviour common to all path classes.

`\$seq = Math::NumSeq::All->new (key=>value,...)`

Create and return a new sequence object.

`\$value = \$seq->ith(\$i)`

Return the `\$i`'th fibbinary number.

`\$bool = \$seq->pred(\$value)`

Return true if `\$value` is a fibbinary number, which means that in binary it doesn't have any consecutive 1 bits. Meaning simply a positive integer with

``    (\$value & (\$value<<1)) == 0``

# FORMULAS

## Next Value

For a given set of bits in a fibbinary number, the next number is simply +1 if the lowest bit is 2^2 or more. If the low bit is 2^1 or 2^0 then it must be shifted up 1 place. If doing so makes it adjacent to a bit above it then drop the low bit and that higher bit must be shifted up. Repeat until the shifting doesn't produce an adjacent bit. For binary 1010...10 or 1010...101 this will mean going all the way to the most significant 1 bit and dropping all the lower ones, giving the next fib=2^(k+1).

## Ith Value

The i'th fibbinary number can be calculated by the Zeckendorf breakdown described above. Simply find the biggest F(k) <= i, subtract the F(k) from i, put 2^k to the fibbinary, and repeat.

Since the Fibonacci numbers grow as (phi^k)/sqrt(5), where phi=(sqrt(5)+1)/2 is the golden ratio, the highest F(k) could be found by a logarithm. Or a log(2) highest bit in i could give 2 or 3 candidates.