search.cpan.org is shutting down
Kevin Ryde > Math-NumSeq > Math::NumSeq::FibonacciWord

Math-NumSeq-72.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

 Open 0
View/Report Bugs
Module Version: 72

NAME

Math::NumSeq::FibonacciWord -- 0/1 related to Fibonacci numbers

SYNOPSIS

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

DESCRIPTION

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```

Morphism

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

Option `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.

FUNCTIONS

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_type` option (a string) can be either

```    "plain"   (the default)
"dense"```

Iterating

`\$seq->seek_to_i(\$i)`

Move the current i so `next()` will return `\$i` (and corresponding value) on the next call.

Random Access

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

Return the `\$i`'th value in the sequence. The first value is at i=0.

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

Return true if `\$value` occurs in the sequence. This simply means 0 or 1, or for the dense Fibonacci word 0, 1 or 2.

Math::PlanePath::FibonacciWordFractal

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