- SEE ALSO
- HOME PAGE
Math::NumSeq::FibonacciWord -- 0/1 related to Fibonacci numbers
use Math::NumSeq::FibonacciWord; my $seq = Math::NumSeq::FibonacciWord->new; my ($i, $value) = $seq->next;
This is a sequence of 0s and 1s formed from the Fibonacci numbers.
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, ... starting i=0
The initial values are 0,1. Then Fibonacci number F(k) many values are copied from the start to extend, repeatedly.
0,1 initial 0,1,0 append 1 value 0,1,0,0,1 append 2 values 0,1,0,0,1,0,1,0 append 3 values 0,1,0,0,1,0,1,0,0,1,0,0,1 append 5 values 0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,0 append 8 values etc
The same sequence is had by starting with 0 and then repeatedly expanding
0 -> 0,1 1 -> 0
Fibbinary and Zeckendorf
The result is also the Fibbinary numbers modulo 2, which is the least significant bit of the Zeckendorf base representation of i.
The Zeckendorf base breakdown subtracts Fibonacci numbers F(k) until reaching 0 or 1. This effectively undoes the above append expansion procedure. (See "Zeckendorf Base" in Math::NumSeq::Fibbinary.)
start at i until i=0 or i=1 do subtract from i the largest Fibonacci number <= i final resulting i=0 or i=1 is Fibonacci word value
For example i=11 has largest Fibonacci<=11 is 8, subtract that to leave 3. From 3 the largest Fibonacci<=3 is 3 itself, subtract that to leave 0 which is the Fibonacci word value for i=11.
Dense Fibonacci Word
fibonacci_word_type => "dense" selects the dense Fibonacci word
1,0,2,2,1,0,2,2,1,1,0,2,1,1,... starting i=0
This is the above plain word with each two values (not overlapping) encoded in a binary style as
plain pair dense value ---------- ----------- 0,0 0 0,1 1 1,0 2
For example the Fibonacci word starts 0,1 so the dense form starts 1. A pair 1,1 never occurs in the plain Fibonacci word so there's no value 3 in the dense form.
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
$seq = Math::NumSeq::FibonacciWord->new ()
$seq = Math::NumSeq::FibonacciWord->new (fibonacci_word_type => $str)
Create and return a new sequence object. The
fibonacci_word_typeoption (a string) can be either
"plain" (the default) "dense"
Move the current i so
$i(and corresponding value) on the next call.
$value = $seq->ith($i)
$i'th value in the sequence. The first value is at i=0.
$bool = $seq->pred($value)
Return true if
$valueoccurs in the sequence. This simply means 0 or 1, or for the dense Fibonacci word 0, 1 or 2.
Copyright 2011, 2012, 2013, 2014 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/>.