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

SEE ALSO

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

HOME PAGE

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

LICENSE

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