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).

Since the two highest bits must be "10..." and "11..." is all skipped there's effectively a run of 2^k values (not all of them used of course) followed by a 2^k gap.

Zeckendorf Base

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

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

Each k is chosen as the highest Fibonacci less than the remainder at that point. For example, taking 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 spacing between Fibonacci numbers means after subtracting F(k) the next cannot be F(k-1), only F(k-2) or less, which means 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 fibbinary number, the next number is simply +1 if the lowest bit is 2^2=4 or more. If the low bit is 2^1=2 or 2^0=1 then the run of trailing ...0101 or ...1010 must be cleared and the bit above incremented. For example 1001010 becomes 1010000. This can be done with some bit twiddling

    filled  = (value >> 1) | value
    mask = ((filled+1) ^ filled) >> 1
    next value = (value | mask) + 1

For example

    value  = 1001010
    filled = 1001111
    mask   =    1111
    next   = 1010000

"filled" means any ...01010 ending has the zeros filled in to ...01111, then those low ones can be picked out with +1 and XOR. The +1 includes the bit above that filled part so ...11111, but a shift drops back to a "mask" of just 01111. OR-ing and incrementing then clears those low bits and sets the next higher to make ...10000.

This works for both a ...0101 and ...1010 ending. In fact it also works when the ending has no 01 or 10 run but all zeros ...0000. In that case the result is just a +1 for ...0001.

Note the calculation only works starting from an existing fibbinary value. It won't go from an arbitrary starting value to the next fibbinary as it acts only on the low bits (up to the lowest "00" pair), leaving the higher bits perhaps still with adjacent 1s.

Ith Value

The i'th fibbinary number can be calculated by the Zeckendorf breakdown described above.

    find the biggest F(k) <= i
    subtract i -= F(k)
    fibbinary result += 2^k
    repeat until i=0

To find each F(k) either just work downwards through the Fibonacci numbers, or alternatively since the Fibonaccis grow as (phi^k)/sqrt(5) where phi=(sqrt(5)+1)/2 is the golden ratio, an F(k) could be found by a log base phi of i. Or taking log(2) for the highest bit in i might give 2 or 3 candidates for k. A log base phi is unlikely to be faster, but the log 2 high bit might jump to a nearly-correct place in a table.

Predicate

Testing for a fibbinary value can be done by a shift and AND,

    is_fibbinary = (value & (value >> 1)) == 0

Any adjacent 1 bits will overlap and come through the AND as non-zero.

In Perl & converts float to int so to test a value bigger than an int requires conversion to Math::BigInt or similar. (Floats which are integers but bigger than an UV/IV might be of interest, or it might be thought any float means rounded-off and therefore inaccurate and not of interest. The current code has some experimental BigInt which works, and can accept BigFloat or BigRat integers, but don't rely on this yet.)

SEE ALSO

Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::FibonacciWord

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2011 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

cpanm Math::NumSeq

perl -MCPAN -e shell
install Math::NumSeq