1Math::NumSeq::SternDiatUosmeirc(C3o)ntributed Perl DocumMeanttha:t:iNounmSeq::SternDiatomic(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

14       This is Moritz Stern's diatomic sequence
15
16           0, 1, 1, 2, 1, 3, 2, 3, ...
17           starting i=0
18
19       It's constructed by successive levels with a recurrence
20
21           D(0)     = 0
22           D(1)     = 1
23           D(2*i)   = D(i)
24           D(2*i+1) = D(i) + D(i+1)
25
26       So the sequence is extended by copying the previous level to the next
27       spead out to even indices, and at the odd indices fill in the sum of
28       adjacent terms,
29
30           0,                    i=0
31           1,                    i=1
32           1,      2,            i=2 to 3
33           1,  3,  2,  3,        i=4 to 7
34           1,4,3,5,2,5,3,4,      i=8 to 15
35
36       For example the i=4to7 row is a copy of the preceding row values 1,2
37       with sums 1+2 and 2+1 interleaved.
38
39       For the new value at the end of each row the sum wraps around so as to
40       take the last copied value and the first value of the next row, which
41       is always 1.  This means the last value in each row increments
42       1,2,3,4,5,etc.
43
44   Odd and Even
45       The sequence makes a repeating pattern even,odd,odd,
46
47           0, 1, 1, 2, 1, 3, 2, 3
48           E  O  O  E  O  O  E ...
49
50       This can be seen from the copying in the recurrence above.  For example
51       the i=8 to 15 row copying to i=16 to 31,
52
53           O . E . O . O . E . O . O . E .      spread
54             O   O   E   O   O   E   O   O      sum adjacent
55
56       Adding adjacent terms odd+even and even+odd are both odd.  Adding
57       adjacent odd+odd gives even.  So the pattern E,O,O in the original row
58       when spread and added gives E,O,O again in the next row.
59

FUNCTIONS

61       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
62       classes.
63
64       "$seq = Math::NumSeq::SternDiatomic->new ()"
65           Create and return a new sequence object.
66
67   Random Access
68       "$value = $seq->ith($i)"
69           Return the $i'th value of the sequence.
70
71       "($v0, $v1) = $seq->ith_pair($i)"
72           Return two values "ith($i)" and "ith($i+1)" from the sequence.  As
73           described below ("Ith Pair") two values can be calculated with the
74           same work as one.
75
76       "$bool = $seq->pred($value)"
77           Return true if $value occurs in the sequence, which means simply
78           integer "$value>=0".
79

FORMULAS

81   Next
82       The sequence is iterated using a method by Moshe Newman in
83
84           "Recounting the Rationals, Continued", answers to problem 10906
85           posed by Donald E. Knuth, C. P. Rupert, Alex Smith and Richard
86           Stong, American Mathematical Monthly, volume 110, number 7, Aug-Sep
87           2003, pages 642-643, <http://www.jstor.org/stable/3647762>
88
89       Two successive sequence values are maintained and are advanced by a
90       simple operation.
91
92           maintaining p = seq[i], q = seq[i+1]
93           initial p = seq[0] = 0
94                   q = seq[1] = 1
95
96           p_next = seq[i+1] = q
97           q_next = seq[i+2] = p+q - 2*(p mod q)
98             where the mod operation rounds towards zero
99             0 <= (p mod q) <= q-1
100
101       The form by Newman uses a floor operation.  That suits expressing the
102       iteration in terms of a rational x[i]=p/q.
103
104           p_next              1
105           ------  =  ----------------------
106           q_next     1 + 2*floor(p/q) - p/q
107
108       For separate p,q a little rearrangement gives it in terms of the
109       remainder p mod q, as per formula a(n)=a(n-2)+a(n-1)-2*(a(n-2) mod
110       a(n-1)) by Mike Stay OEIS A002487, November 2006.
111
112           division p = q*floor(p/q) + rem      where rem = (p mod q)
113           then
114           p_next/q_next = 1 / (1 + 2*floor(p/q) - p/q)    per Newman
115                         = q / (2*q*floor(p/q) + q - p)
116                         = q / (2*(p - rem) + q - p)
117                         = q / (p+q - 2*rem)               using p,q
118
119       In terms of the Calkin-Wilf tree this method works because the number
120       of trailing right leg steps can be found by m=floor(p/q), then take a
121       step across, then back down again by m many left leg steps.  When at
122       the right-most edge of the tree the step across goes down by one extra
123       left, thereby automatically wrapping around at the end of each row.
124
125       "seek_to_i()" is implemented by calculating a pair of new p,q values
126       with an "ith_pair()" per below.
127
128   Ith Pair
129       For "ith_pair()" the two sequence values at an arbitrary i,i+1 can be
130       calculated from the bits of i,
131
132           p = 0
133           q = 1
134           for each bit of i from high to low
135             if bit=1 then p += q
136             if bit=0 then q += p
137           return p,q      # are ith(i) and ith(i+1)
138
139       For example i=6 is binary "110" so
140
141                                p,q
142                                ---
143          initial               0,1
144          high bit=1 so p+=q    1,1
145          next bit=1 so p+=q    2,1
146          low  bit=0 so q+=p    2,3   is ith(6),ith(7)
147
148       This is the same as the Calkin-Wilf tree descent, per "Calkin-Wilf
149       Tree" in Math::PlanePath::RationalsTree.  Its X/Y fractions are
150       successive Stern diatomic sequence values.
151
152   Ith Alone
153       If only a single ith() value is desired then a variation can be made on
154       the "Ith Pair" above.  Taking the bits of i from low to high (instead
155       of high to low) gives p=ith(i), but q is not ith(i+1).  Low zero bits
156       can be ignored for this approach since initial p=0 means the steps q+=p
157       for bit=0 do nothing.
158

SEE ALSO

160       Math::NumSeq
161
162       Math::PlanePath::RationalsTree
163

HOME PAGE

165       <http://user42.tuxfamily.org/math-numseq/index.html>
166

LICENSE

168       Copyright 2011, 2012, 2013, 2014 Kevin Ryde
169
170       Math-NumSeq is free software; you can redistribute it and/or modify it
171       under the terms of the GNU General Public License as published by the
172       Free Software Foundation; either version 3, or (at your option) any
173       later version.
174
175       Math-NumSeq is distributed in the hope that it will be useful, but
176       WITHOUT ANY WARRANTY; without even the implied warranty of
177       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
178       General Public License for more details.
179
180       You should have received a copy of the GNU General Public License along
181       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
182
183
184
185perl v5.28.0                      2014-06-29    Math::NumSeq::SternDiatomic(3)
Impressum