1Math::NumSeq::ReRound(3U)ser Contributed Perl DocumentatiMoanth::NumSeq::ReRound(3)
2
3
4

NAME

6       Math::NumSeq::ReRound -- sequence from repeated rounding up
7

SYNOPSIS

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

DESCRIPTION

14       This is the sequence of values formed by repeatedly rounding up to a
15       multiple of i-1, i-2, ..., 2, 1.
16
17           1, 2, 4, 6, 10, 12, 18, 22, 30, 34, 42, 48, 58, 60, 78, ...
18           starting i=1
19
20       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
25       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
31       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
35           value ~= i^2 / pi
36
37       though there's values both bigger and smaller than this approximation.
38
39   Extra Multiples
40       The "extra_multiples" option can round up by extra multiples at each
41       step.  For example,
42
43           # extra_multiples => 2
44           1, 4, 10, 18, 30, 42, 58, 78, 102, 118, 150, 174, ...
45
46       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
53       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
57   Sieve
58       The sequence can also be constructed as a sieve.  Start with the
59       integers,
60
61           1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
62
63       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
67           1,2,4,6,8,10,12,14,16,18,20,22,24,26,28...
68
69       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
72           1,2,4,6,10,12,16,18,22,24,28,...
73
74       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
77           1,2,4,6,10,12,18,22,24,...
78
79       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
83       This sieve process makes it clear the values always increase, which is
84       not quite obvious from the repeated rounding-up.
85
86   Flavius Josephus Sieve
87       When "extra_multiples => 1" the sequence is the sieve of Flavius
88       Josephus,
89
90           # extra_multiples => 1
91           1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, ...
92
93       This sieve again begins with the integers
94
95           1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
96
97       Drop every 2nd number,
98
99           1,3,5,7,9,11,13,15,17,19,...
100
101       Drop every 3rd from the remaining, so
102
103           1,3,7,9,13,15,19,...
104
105       Drop every 4th from the remaining, so
106
107           1,3,7,13,15,19,...
108
109       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
113       This case can also be calculated by working downwards from the square
114       i^2
115
116           value = i^2
117           for m = i-1 down to 1
118             value = next smaller multiple of m < value
119
120       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

FUNCTIONS

126       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
127       classes.
128
129       "$seq = Math::NumSeq::ReRound->new ()"
130       "$seq = Math::NumSeq::ReRound->new (extra_multiples => $integer)"
131           Create and return a new sequence object.
132
133   Random Access
134       "$value = $seq->ith($i)"
135           Return $i rounded up to multiples of i-1,...,2.
136
137       "$bool = $seq->pred($value)"
138           Return true if $value is a ReRound value.
139
140       "$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

FORMULAS

145   Predicate
146       The rounding procedure can be reversed to test for a ReRound value.
147
148           for i=2,3,4,etc
149             value -= extra_multiples*i
150             if value < 0 then not a ReRound
151
152             remainder = value mod i
153             if remainder==i-1 then not a ReRound
154
155             value -= remainder    # round down to multiple of i
156
157           stop when value <= i
158           is a ReRound if value==i, and i is its index
159
160       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
170   Value to i Estimate
171       For the default sequence as noted above the values grow roughly as
172
173           value ~= i^2 / pi
174
175       so can be estimated as
176
177           i ~= sqrt(value) * sqrt(pi)
178
179       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
183           i ~= sqrt(value) * 296/167
184
185       "extra_multiples => m" adds a fixed amount i*m at each step, for a
186       total
187
188           value_EM = m + 2*m + 3*m + 4*m + ... + i*m
189                    = m * i*(i+1)/2
190
191       As m becomes large this part of the value dominates, so
192
193           value =~ m * i*(i+1)/2     for large m
194
195           i =~ sqrt(value*2/m)
196
197       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
203       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

SEE ALSO

207       Math::NumSeq, Math::NumSeq::ReReplace
208

HOME PAGE

210       <http://user42.tuxfamily.org/math-numseq/index.html>
211

LICENSE

213       Copyright 2011, 2012, 2013, 2014, 2016, 2019 Kevin Ryde
214
215       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
220       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
225       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/>.
227
228
229
230perl v5.32.0                      2020-07-28          Math::NumSeq::ReRound(3)
Impressum