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 below ("Ith Pair") two values can be calculated with the
74 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 method by Moshe Newman in
83 "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 Two successive sequence values are maintained and are advanced by a
90 simple operation.
91 maintaining p = seq[i], q = seq[i+1]
93 initial p = seq[0] = 0
94 q = seq[1] = 1
95 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 The form by Newman uses a floor operation. That suits expressing the
102 iteration in terms of a rational x[i]=p/q.
103 p_next 1
105 ------ = ----------------------
106 q_next 1 + 2*floor(p/q) - p/q
107 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 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 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 "seek_to_i()" is implemented by calculating a pair of new p,q values
126 with an "ith_pair()" per below.
127 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 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 For example i=6 is binary "110" so
140 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 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 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
160 Math::NumSeq
161 Math::PlanePath::RationalsTree
163
165 <http://user42.tuxfamily.org/math-numseq/index.html>
166
168 Copyright 2011, 2012, 2013, 2014 Kevin Ryde
169 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 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 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/>.
182perl v5.28.0 2014-06-29 Math::NumSeq::SternDiatomic(3)