and 1 contributors

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

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