/ 
Math-NumSeq-74
River stage zero No dependents
/ Math::NumSeq::ReRound

NAME

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

SYNOPSIS

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

DESCRIPTION

This is the sequence of values formed by repeatedly rounding up to a multiple of i-1, i-2, ..., 2, 1.

1, 2, 4, 6, 10, 12, 18, 22, 30, 34, 42, 48, 58, 60, 78, ...
starting i=1

For example i=5 start at 5, round up to a multiple of 4 to give 8, then round up to a multiple of 3 to give 9, then round up to a multiple of 2 to give 10, and finally round up to a multiple of 1 is no change value=10 at i=5.

When rounding up if a value is already a suitable multiple then it's unchanged. That always happens for the final round up to a multiple of 1, but it can happen in intermediate places too. For example i=4 start at 4, round up to a multiple of 3 to give 6, then 6 round up to a multiple of 2 is 6 unchanged since it's already a multiple of 2.

For i>=3 the last step is always a round up to a multiple of 2 so the values are all even. They're also always increasing and end up approximately

value ~= i^2 / pi

though there's values both bigger and smaller than this approximation.

Extra Multiples

The extra_multiples option can round up by extra multiples at each step. For example,

# extra_multiples => 2
1, 4, 10, 18, 30, 42, 58, 78, 102, 118, 150, 174, ...

At i=5 start 5, round up to a multiple of 4 which is 8, and then two extra multiples of 4 to give 16, then round up to a multiple of 3 is 18 and two extra multiples of 3 to give 24, then round up to a multiple of 2 is 24 already and two extra multiples of 2 gives 28, then round up to a multiple of 1 is 28 already and two extra multiples of 1 gives finally value=30 at i=5.

When extra_multiples is 0 the final round up to a multiple of 1 can be ignored, but with extra multiples there's a fixed extra amount to add there.

Sieve

The sequence can also be constructed as a sieve. Start with the integers,

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...

Delete every 2nd, starting counting from the 2nd. So at 2 keep that 2, drop value 3, keep value 4, drop value 5, etc, which leaves the even integers.

1,2,4,6,8,10,12,14,16,18,20,22,24,26,28...

Then delete every 3rd starting counting from the 3rd. So starting at value 4 keep 4,6, drop 8, keep 10,12, drop 14, etc.

1,2,4,6,10,12,16,18,22,24,28,...

Then delete every 4th starting counting from the 4th. So starting at 6 keep 6,10,12, drop 16, keep 18,22,24, drop 28, etc.

1,2,4,6,10,12,18,22,24,...

And so on deleting every increasing multiples. At the "delete every k-th" stage the first 2*k-1 values are unchanged, so the procedure can stop when the stage is past the desired number of values.

This sieve process makes it clear the values always increase, which is not quite obvious from the repeated rounding-up.

Flavius Josephus Sieve

When extra_multiples => 1 the sequence is the sieve of Flavius Josephus,

# extra_multiples => 1
1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, ...

This sieve again begins with the integers

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...

Drop every 2nd number,

1,3,5,7,9,11,13,15,17,19,...

Drop every 3rd from the remaining, so

1,3,7,9,13,15,19,...

Drop every 4th from the remaining, so

1,3,7,13,15,19,...

And so on, dropping an every increasing multiple. Unlike the sieve for the default case above the start point for the drop counting is the start of the remaining values.

This case can also be calculated by working downwards from the square i^2

value = i^2
for m = i-1 down to 1
  value = next smaller multiple of m < value

The next smaller multiple is strictly less than value, so if value is already a multiple of m then it changes to value-m, the next lower multiple. The last step is m=1. In that case value is always a multiple of 1 and the next lower multiple always means value-1.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::ReRound->new ()
$seq = Math::NumSeq::ReRound->new (extra_multiples => $integer)

Create and return a new sequence object.

Random Access

$value = $seq->ith($i)

Return $i rounded up to multiples of i-1,...,2.

$bool = $seq->pred($value)

Return true if $value is a ReRound value.

$i = $seq->value_to_i_estimate($value)

Return an estimate of the i corresponding to $value. See "Value to i Estimate" below.

FORMULAS

Predicate

The rounding procedure can be reversed to test for a ReRound value.

for i=2,3,4,etc
  value -= extra_multiples*i
  if value < 0 then not a ReRound

  remainder = value mod i
  if remainder==i-1 then not a ReRound

  value -= remainder    # round down to multiple of i

stop when value <= i
is a ReRound if value==i, and i is its index

For example to test 28, it's a multiple of 2, so ok for the final rounding step. It's predecessor in the rounding steps was a multiple of 3, so round down to a multiple of 3 which is 27. The predecessor of 27 was a multiple of 4 so round down to 24. But at that point there's a contradiction because if 24 was the value then it's already a multiple of 3 and so wouldn't have gone up to 27. This case where a round-down gives a multiple of both i and i-1 is identified by the remainder = value % i == i-1. If value is already a multiple of i-1 then subtracting an i-1 would leave it still so.

Value to i Estimate

For the default sequence as noted above the values grow roughly as

value ~= i^2 / pi

so can be estimated as

i ~= sqrt(value) * sqrt(pi)

There's no need for high accuracy in pi. The current code uses an approximation sqrt(pi)~=296/167 for faster calculation if the value is a Math::BigInt or Math::BigRat.

i ~= sqrt(value) * 296/167

extra_multiples => m adds a fixed amount i*m at each step, for a total

value_EM = m + 2*m + 3*m + 4*m + ... + i*m
         = m * i*(i+1)/2

As m becomes large this part of the value dominates, so

value =~ m * i*(i+1)/2     for large m

i =~ sqrt(value*2/m)

As m increases the factor sqrt(pi) progressively morphs towards sqrt(2/m). For m even it might be sqrt(pi)/2, 3/8*sqrt(pi), 5/16*sqrt(pi), 35/128*sqrt(pi), etc, and for m odd it might be 2*sqrt(1/pi), 4/3*sqrt(1/pi), 16/15*sqrt(1/pi), 32/35*sqrt(1/pi), 256/315*sqrt(1/pi), etc. What's the pattern?

The current code uses the "large m" formula for any m>0, which is no more than roughly a factor 1.25 too big.

SEE ALSO

Math::NumSeq, Math::NumSeq::ReReplace

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2011, 2012, 2013, 2014, 2016, 2019 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.