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, ...
being integers which have no adjacent 1 bits in binary, in ascending order.
i fibbinary fibbinary
(decimal) (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 high "11..." is excluded, there's effectively a block of 2^k values (not all of them used) followed by a gap of 2^k values, etc.
The least significant bit of each fibbinary is the Fibonacci word sequence, per Math::NumSeq::FibonacciWord.
All numbers without adjacent 1 bits can also be generated simply by taking the binary expansion and changing each "1" to "01", but this isn't in ascending order the way the fibbinary here is.
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 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, reckoning the Fibonaccis as 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 this sum in an integer,
fibbinary(20) = 2^5 + 2^3 + 2^0 = 41
The gaps between Fibonacci numbers means that after subtracting F(k) the next cannot be F(k1), it must be F(k2) or less. For that reason there's no adjacent 1 bits in the fibbinary numbers.
The connection between no adjacent 1s and the Fibonacci sequence can be seen by considering values with high bit 2^k. The further bits in it cannot have 2^(k1) but only 2^(k2), so effectively the number of new values are not from the previous k1 but the second previous k2, the same way as the Fibonacci sequence adds not the previous term (which would by double) but the one before instead.
FUNCTIONS
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
Random Access
$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. $i = $seq>value_to_i_floor($value)

Return the index i of
$value
or of the next fibbinary number below$value
. $i = $seq>value_to_i_estimate($value)

Return an estimate of the i corresponding to
$value
.
FORMULAS
Next Value
For a given fibbinary number, the next fibbinary is +1 if the lowest bit is 2^2=4 or more. If however the low bit is 2^1=2 or 2^0=1 then the run of low alternating ...101 or ...1010 must be cleared and the bit above set. For example 1001010 becomes 1010000. All cases can be handled quite easily with some bit twiddling
# value=fibbinary
filled = (value >> 1)  value
mask = ((filled+1) ^ filled) >> 1
next value = (value  mask) + 1
For example
value = 1001010
filled = 1101111
mask = 1111
next = 1010000
"filled" means any trailing ...01010 has the zeros filled in to ...01111. Then those low ones can be extracted with +1 and XOR (the usual trick for getting low ones). +1 means the bit above the filled part is included ...11111 but a shift drops back to "mask" just 01111. ORing and incrementing then clears those low bits and sets the next higher bit to make ...10000.
This works for any fibbinary input, both "...10101" and "...1010" endings and also zeros "...0000" ending. In the zeros case the result is just a +1 for "...0001" and that includes input value=0 giving next=1.
Ith Value
The i'th fibbinary number can be calculated as per "Zeckendorf Base" above. Reckoning the Fibonacci numbers as F(0)=1, F(1)=2, F(2)=3, F(3)=5, etc,
find the biggest F(k) <= i
subtract i = F(k)
fibbinary result += 2^k
repeat until i=0
To find each F(k)<=i either just work downwards through the Fibonacci numbers, or the Fibonaccis grow as (phi^k)/sqrt(5) with phi=(sqrt(5)+1)/2 the golden ratio, so an F(k) could be found by a log base phi of i. Or taking log2 of i (the highest bit in i) might give 2 or 3 candidates for k. Calculating log base phi is unlikely to be faster, but log 2 high bit might quickly go to a nearlycorrect 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 overlap in the shift+AND and come through as nonzero.
In Perl &
converts NV float to UV integer. If a value in an NV mantissa is an integer but bigger than a UV then bits will be lost to the &
. Conversion to Math::BigInt
or similar is necessary to preserve the full value. Floats which are integers but bigger than an UV might be of interest, or it might be thought any float means roundedoff and therefore inaccurate and not of interest. The current code has some experimental automatic BigInt conversion which works for floats and for BigFloat or BigRat integers too, but don't rely on this quite yet. (A BigInt input directly is fine of course.)
Value to i Floor
In a fibbinary value each bit becomes a Fibonacci F[i] to add to make i, as per "Zeckendorf Base" above.
If a number is not a fibbinary then the next lower fibbinary can be had by finding the highest 11 pair and changing it and all the bits below to 101010...etc. For example 10011001 is not a fibbinary and must change down to 10010101, ie. the 11001 reduces to 10101, that being the biggest fibbinary noadjacent1s which is 10xxx.
bits 2^k from high to low
if bit set
if prev bit set too
then treat remainder as 010101...
else i += F[k]
If working downwards adding F[k] values then it's easy enough to notice an adjacent 11 pair. An alternative would be to find all 11 pairs per "Predicate" above and the highest 1 bit (if any) is the place to mangle.
Value to i Estimate
In general i grows as a power of phi=1.618 and the values grow as a power of 2. So an estimate can be had from
value = 2^k
i = F[k+1]
~= phi^(k+1) / (phi+1/phi)
~= C * phi^k
where C=phi/(phi+1/phi)
log(i/C)/log(phi) ~= log(value)/log(2)
i_estimate = C * value ^ (log(phi)/log(2))
The power log(phi)/log(2)=0.694 reduces to give an i approximation. That power can also be approximated by shifting off the least significant 10.694=0.306 of the bits of the value. This is fast and may be enough accuracy for a bigint.
highbitpos of value
i_estimate = value >> floor(highbitpos * 0.306)
SEE ALSO
Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::FibonacciWord, Math::NumSeq::GolayRudinShapiro, Math::NumSeq::BaumSweet
HOME PAGE
http://user42.tuxfamily.org/mathnumseq/index.html
LICENSE
Copyright 2011, 2012 Kevin Ryde
MathNumSeq 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.
MathNumSeq 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 MathNumSeq. If not, see <http://www.gnu.org/licenses/>.