The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-NumSeq-10
River stage zero No dependents
3 ++
/ Math::NumSeq::Fibbinary

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.

SEE ALSO

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

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