Rounding Up To π

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 n²/f(n) approaches π (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 A_k is a constant. Setting the derivative of this expression to zero gives the coordinates [x_k, y_k] of the maximum point on the kth parabola:

The value of A_k 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)(x_k–1)² for y_k–1 into this expression and then putting this A_k into the expression for x_k gives

with the exception that we have x₁ = (x₀ + 1)/2 instead of (x₀)/2, because we have the initial condition y₀ = x₀ rather than y₀ = k(x₀)². Thus, beginning with x₀ = y₀ = n, the "rounding up" algorithm in continuous form yields the following convergent product for x_k :

from which it follows that

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

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

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 ϕ(n):

Is this similarity significant?

Return to MathPages Main Menu