The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Math::NumSeq::SternDiatomic -- Stern's diatomic sequence

SYNOPSIS

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

DESCRIPTION

This is Moritz Stern's diatomic sequence

    0, 1, 1, 2, 1, 3, 2, 3, ...
    starting i=0

It's constructed by successive levels with a recurrence

    D(0)     = 0
    D(1)     = 1
    D(2*i)   = D(i)
    D(2*i+1) = D(i) + D(i+1)

So the sequence is extended by copying the previous level to the even indices of the next, and at the odd indices the sum of adjacent terms,

   0,                    i=0
   1,                    i=1
   1,      2,            i=2 to 3
   1,  3,  2,  3,        i=4 to 7
   1,4,3,5,2,5,3,4,      i=8 to 15

For example the i=4 row is a copy of the preceding values 1,2 with sums 1+2 and 2+1 interleaved. The value at the end of each row is the sum of the last of the previous row and the first of the current row (which is always 1).

Odd and Even

The sequence makes a repeating pattern even,odd,odd,

    0, 1, 1, 2, 1, 3, 2, 3
    E  O  O  E  O  O  E ...

This can be seen from the copying in the recurrence above. For example the i=8 to 15 row copying to i=16 to 31,

    O . E . O . O . E . O . O . E .      spread
      O   O   E   O   O   E   O   O      sum adjacent

Adding adjacent terms odd+even and even+odd are both odd and odd+odd gives even, so the pattern EOO in the original row spread and added gives EOO again in the next row.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::SternDiatomic->new ()

Create and return a new sequence object.

Random Access

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

Return the $i'th value of the sequence.

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

Return true if $value occurs in the sequence, which means simply integer $value>=0.

SEE ALSO

Math::NumSeq

HOME PAGE

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

LICENSE

Copyright 2011, 2012, 2013 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/>.