1Math::NumSeq::SternDiatUosmeirc(C3o)ntributed Perl DocumMeanttha:t:iNounmSeq::SternDiatomic(3)
2
6 Math::NumSeq::SternDiatomic -- Stern's diatomic sequence
7
9 use Math::NumSeq::SternDiatomic;
10 my $seq = Math::NumSeq::SternDiatomic->new;
11 my ($i, $value) = $seq->next;
12
14 This is Moritz Stern's diatomic sequence
15 0, 1, 1, 2, 1, 3, 2, 3, ...
17 starting i=0
18 It's constructed by successive levels with a recurrence
20 D(0) = 0
22 D(1) = 1
23 D(2*i) = D(i)
24 D(2*i+1) = D(i) + D(i+1)
25 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 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 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 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 Odd and Even
45 The sequence makes a repeating pattern even,odd,odd,
46 0, 1, 1, 2, 1, 3, 2, 3
48 E O O E O O E ...
49 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 O . E . O . O . E . O . O . E . spread
54 O O E O O E O O sum adjacent
55 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
61 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
62 classes.
63 "$seq = Math::NumSeq::SternDiatomic->new ()"
65 Create and return a new sequence object.
66 Random Access
68 "$value = $seq->ith($i)"
69 Return the $i'th value of the sequence.
70 "($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 "$bool = $seq->pred($value)"
77 Return true if $value occurs in the sequence, which means simply
78 integer "$value>=0".
79
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 "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 Two successive sequence values are maintained and are advanced by a
93 simple operation.
94 maintain p = seq[i], q = seq[i+1]
96 start p = seq[0] = 0
97 q = seq[1] = 1
98 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 Newman gives a form using a floor operation. That suits expressing the
105 iteration in terms of a rational x[i]=p/q.
106 p_next 1
108 ------ = ----------------------
109 q_next 1 + 2*floor(p/q) - p/q
110 A little rearrangement gives the separate p,q above
112 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 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 "seek_to_i()" is implemented by calculating a pair of new p,q values
127 with an "ith_pair()" per below.
128 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 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 For example i=6 is binary "110" so
141 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 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 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
161 Math::NumSeq
162 Math::PlanePath::RationalsTree
164
166 <http://user42.tuxfamily.org/math-numseq/index.html>
167
169 Copyright 2011, 2012, 2013, 2014, 2016, 2017, 2019 Kevin Ryde
170 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 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 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/>.
183perl v5.34.0 2021-07-22 Math::NumSeq::SternDiatomic(3)