1Math::NumSeq::ReRound(3U)ser Contributed Perl DocumentatiMoanth::NumSeq::ReRound(3)
2
6 Math::NumSeq::ReRound -- sequence from repeated rounding up
7
9 use Math::NumSeq::ReRound;
10 my $seq = Math::NumSeq::ReRound->new;
11 my ($i, $value) = $seq->next;
12
14 This is the sequence of values formed by repeatedly rounding up to a
15 multiple of i-1, i-2, ..., 2, 1.
16 1, 2, 4, 6, 10, 12, 18, 22, 30, 34, 42, 48, 58, 60, 78, ...
18 starting i=1
19 For example i=5 start at 5, round up to a multiple of 4 to give 8, then
21 round up to a multiple of 3 to give 9, then round up to a multiple of 2
22 to give 10, and finally round up to a multiple of 1 is no change
23 value=10 at i=5.
24 When rounding up if a value is already a suitable multiple then it's
26 unchanged. That always happens for the final round up to a multiple of
27 1, but it can happen in intermediate places too. For example i=4 start
28 at 4, round up to a multiple of 3 to give 6, then 6 round up to a
29 multiple of 2 is 6 unchanged since it's already a multiple of 2.
30 For i>=3 the last step is always a round up to a multiple of 2 so the
32 values are all even. They're also always increasing and end up
33 approximately
34 value ~= i^2 / pi
36 though there's values both bigger and smaller than this approximation.
38 Extra Multiples
40 The "extra_multiples" option can round up by extra multiples at each
41 step. For example,
42 # extra_multiples => 2
44 1, 4, 10, 18, 30, 42, 58, 78, 102, 118, 150, 174, ...
45 At i=5 start 5, round up to a multiple of 4 which is 8, and then two
47 extra multiples of 4 to give 16, then round up to a multiple of 3 is 18
48 and two extra multiples of 3 to give 24, then round up to a multiple of
49 2 is 24 already and two extra multiples of 2 gives 28, then round up to
50 a multiple of 1 is 28 already and two extra multiples of 1 gives
51 finally value=30 at i=5.
52 When "extra_multiples" is 0 the final round up to a multiple of 1 can
54 be ignored, but with extra multiples there's a fixed extra amount to
55 add there.
56 Sieve
58 The sequence can also be constructed as a sieve. Start with the
59 integers,
60 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
62 Delete every 2nd, starting counting from the 2nd. So at 2 keep that 2,
64 drop value 3, keep value 4, drop value 5, etc, which leaves the even
65 integers.
66 1,2,4,6,8,10,12,14,16,18,20,22,24,26,28...
68 Then delete every 3rd starting counting from the 3rd. So starting at
70 value 4 keep 4,6, drop 8, keep 10,12, drop 14, etc.
71 1,2,4,6,10,12,16,18,22,24,28,...
73 Then delete every 4th starting counting from the 4th. So starting at 6
75 keep 6,10,12, drop 16, keep 18,22,24, drop 28, etc.
76 1,2,4,6,10,12,18,22,24,...
78 And so on deleting every increasing multiples. At the "delete every
80 k-th" stage the first 2*k-1 values are unchanged, so the procedure can
81 stop when the stage is past the desired number of values.
82 This sieve process makes it clear the values always increase, which is
84 not quite obvious from the repeated rounding-up.
85 Flavius Josephus Sieve
87 When "extra_multiples => 1" the sequence is the sieve of Flavius
88 Josephus,
89 # extra_multiples => 1
91 1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, ...
92 This sieve again begins with the integers
94 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
96 Drop every 2nd number,
98 1,3,5,7,9,11,13,15,17,19,...
100 Drop every 3rd from the remaining, so
102 1,3,7,9,13,15,19,...
104 Drop every 4th from the remaining, so
106 1,3,7,13,15,19,...
108 And so on, dropping an every increasing multiple. Unlike the sieve for
110 the default case above the start point for the drop counting is the
111 start of the remaining values.
112 This case can also be calculated by working downwards from the square
114 i^2
115 value = i^2
117 for m = i-1 down to 1
118 value = next smaller multiple of m < value
119 The next smaller multiple is strictly less than value, so if value is
121 already a multiple of m then it changes to value-m, the next lower
122 multiple. The last step is m=1. In that case value is always a
123 multiple of 1 and the next lower multiple always means value-1.
124
126 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
127 classes.
128 "$seq = Math::NumSeq::ReRound->new ()"
130 "$seq = Math::NumSeq::ReRound->new (extra_multiples => $integer)"
131 Create and return a new sequence object.
132 Random Access
134 "$value = $seq->ith($i)"
135 Return $i rounded up to multiples of i-1,...,2.
136 "$bool = $seq->pred($value)"
138 Return true if $value is a ReRound value.
139 "$i = $seq->value_to_i_estimate($value)"
141 Return an estimate of the i corresponding to $value. See "Value to
142 i Estimate" below.
143
145 Predicate
146 The rounding procedure can be reversed to test for a ReRound value.
147 for i=2,3,4,etc
149 value -= extra_multiples*i
150 if value < 0 then not a ReRound
151 remainder = value mod i
153 if remainder==i-1 then not a ReRound
154 value -= remainder # round down to multiple of i
156 stop when value <= i
158 is a ReRound if value==i, and i is its index
159 For example to test 28, it's a multiple of 2, so ok for the final
161 rounding step. It's predecessor in the rounding steps was a multiple
162 of 3, so round down to a multiple of 3 which is 27. The predecessor of
163 27 was a multiple of 4 so round down to 24. But at that point there's
164 a contradiction because if 24 was the value then it's already a
165 multiple of 3 and so wouldn't have gone up to 27. This case where a
166 round-down gives a multiple of both i and i-1 is identified by the
167 remainder = value % i == i-1. If value is already a multiple of i-1
168 then subtracting an i-1 would leave it still so.
169 Value to i Estimate
171 For the default sequence as noted above the values grow roughly as
172 value ~= i^2 / pi
174 so can be estimated as
176 i ~= sqrt(value) * sqrt(pi)
178 There's no need for high accuracy in pi. The current code uses an
180 approximation sqrt(pi)~=296/167 for faster calculation if the value is
181 a "Math::BigInt" or "Math::BigRat".
182 i ~= sqrt(value) * 296/167
184 "extra_multiples => m" adds a fixed amount i*m at each step, for a
186 total
187 value_EM = m + 2*m + 3*m + 4*m + ... + i*m
189 = m * i*(i+1)/2
190 As m becomes large this part of the value dominates, so
192 value =~ m * i*(i+1)/2 for large m
194 i =~ sqrt(value*2/m)
196 As m increases the factor sqrt(pi) progressively morphs towards
198 sqrt(2/m). For m even it might be sqrt(pi)/2, 3/8*sqrt(pi),
199 5/16*sqrt(pi), 35/128*sqrt(pi), etc, and for m odd it might be
200 2*sqrt(1/pi), 4/3*sqrt(1/pi), 16/15*sqrt(1/pi), 32/35*sqrt(1/pi),
201 256/315*sqrt(1/pi), etc. What's the pattern?
202 The current code uses the "large m" formula for any m>0, which is no
204 more than roughly a factor 1.25 too big.
205
207 Math::NumSeq, Math::NumSeq::ReReplace
208
210 <http://user42.tuxfamily.org/math-numseq/index.html>
211
213 Copyright 2011, 2012, 2013, 2014, 2016 Kevin Ryde
214 Math-NumSeq is free software; you can redistribute it and/or modify it
216 under the terms of the GNU General Public License as published by the
217 Free Software Foundation; either version 3, or (at your option) any
218 later version.
219 Math-NumSeq is distributed in the hope that it will be useful, but
221 WITHOUT ANY WARRANTY; without even the implied warranty of
222 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
223 General Public License for more details.
224 You should have received a copy of the GNU General Public License along
226 with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
227perl v5.30.1 2020-01-30 Math::NumSeq::ReRound(3)