Rounding Up To p


Beginning with any positive integer n, round up to the nearest multiple of n-1, then up to the nearest multiple of n-2, and so on, up to the nearest multiple of 1. Let f(n) denote the result. For example, f(10) = 34. Interestingly, the ratio n2/f(n) approaches p (i.e., 3.14159...) as n increases.


To derive this limit it's useful to examine the sequence of numbers that are produced as we "round up" from, say, 100. In the following table, x is the "rounding modulus" and y is the resulting rounded value for each step of the algorithm in the computation of f(100). The value of w is just y/x.



The rounding algorithm essentially states that, on each step, y must be the least integer that equals or exceeds the previous y and is divisible by x. Notice that initially the ratio w increases by 1 on each step, so y can be expressed as



This is a parabola, and the value of y increases as x decreases until y reaches a maximum of y = 2550 at x = 50. As x continues to decrease we must now increase the ratio w by 2 on each step in order for the values of y to keep increasing. In other words, after riding the parabola (1) to its maximum we have to shift to the intersecting parabola



which we can ride up to its maximum of 151/[(2)(2)] = 38. At that point the process shifts to the intersecting parabola



and so on. In general, the equation for the kth parabola is of the form



where Ak is a constant. Setting the derivative of this expression to zero gives the coordinates [xk, yk] of the maximum point on the kth parabola:



The value of Ak can be inferred from the coordinates of the intersection of the kth parabola with the maximum point of the previous parabola, which gives



Substituting (k-1)(xk-1)2 for yk-1 into this expression and then putting this Ak into the expression for xk gives



with the exception that we have x1 = (x0 + 1)/2 instead of (x0)/2, because we have the initial condition y0 = x0 rather than y0 = k(x0)2. Thus, beginning with x0 = y0 = n, the "rounding up" algorithm in continuous form yields the following convergent product for xk :



from which it follows that



Since yk approximates f(n) in the limit as k goes to infinity, this relation implies



which is equivalent to Wallis's infinite product for p.


The plot below shows the first four parabolas that appear in the algorithm for f(100).



Incidentally, the sequence f(1), f(2), f(3)... can also be derived using a sieve method similar to the sieve of Eratosthenes. Starting with a list of the natural numbers, delete every 2nd element beginning with the 3rd. This leaves the sequence



From this, delete every 3rd element beginning with the 5th, which leaves



From this, delete every 4th element beginning with the 7th, which leaves



From this, delete every 5th element beginning with the 9th, which leaves



In general, from the kth sequence delete every (k+1)th element beginning with the (2k+1)th element. This yields the same sequence f(1),f(2),f(3),... as produced by the "rounding up" algorithm.


This sequence appears as sequence #377 in Sloane's Handbook of Integer Functions, which refers to a paper by Yosef David in vol 11 of Riveon Lematematika (1957). This paper says Jabotinski and Erdos proved that



consistent with our observation on the rounding sequence. There are also some relevant references in Richard Guy's "Unsolved Problems in Number Theory" under the heading of "lucky numbers". In all of these references the authors derive this sequence using the sieve method. No one seems to have noticed the simple "rounding up" algorithm.


By the way, it would be easy to mistake the sequence f(n) for the cumulative sums of the Euler totient function phi(n):



Is this similarity significant?


Return to MathPages Main Menu