Rounding Up To PI
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^2/f(n)
approaches pi (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.
x w y x w y x w y x w y
100 1 100 75 26 1950 50 51 2550 25 122 3050
99 2 198 74 27 1998 49 53 2597 24 128 3072
98 3 294 73 28 2044 48 55 2640 23 134 3082
97 4 388 72 29 2088 47 57 2679 22 141 3102
96 5 480 71 30 2130 46 59 2714 21 148 3108
95 6 570 70 31 2170 45 61 2745 20 156 3120
94 7 658 69 32 2208 44 63 2772 19 165 3135
93 8 744 68 33 2244 43 65 2795 18 175 3150
92 9 828 67 34 2278 42 67 2814 17 186 3162
91 10 910 66 35 2310 41 69 2829 16 198 3168
90 11 990 65 36 2340 40 71 2840 15 212 3180
89 12 1068 64 37 2368 39 73 2847 14 228 3192
88 13 1144 63 38 2394 38 75 2850 13 246 3198
87 14 1218 62 39 2418 37 78 2886 12 267 3204
86 15 1290 61 40 2440 36 81 2916 11 292 3212
85 16 1360 60 41 2460 35 84 2940 10 322 3220
84 17 1428 59 42 2478 34 87 2958 9 358 3222
83 18 1494 58 43 2494 33 90 2970 8 403 3224
82 19 1558 57 44 2508 32 93 2976 7 461 3227
81 20 1620 56 45 2520 31 96 2976 6 538 3228
80 21 1680 55 46 2530 30 100 3000 5 646 3230
79 22 1738 54 47 2538 29 104 3016 4 808 3232
78 23 1794 53 48 2544 28 108 3024 3 1078 3234
77 24 1848 52 49 2548 27 112 3024 2 1617 3234
76 25 1900 51 50 2550 26 117 3042 1 3234 3234
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
y = (101 - x) x (1)
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
y = (151 - 2x) x
which we can ride up to its maximum of [151/(2*2)] = 38. At that point
the process shifts to the intersecting parabola
y = (189 - 3x) x
and so on. In general, the equation for the kth parabola is of the
form
y = (A_k - kx) x
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:
A_k
x_k = ----- y_k = k (x_k)^2
2k
Also, the value of A_k can be inferred from from the coordinates of
the intersection of the kth parabola with the maximum point of the
previous parabola, which gives
y_(k-1) + k(x_(k-1))^2
A_k = -----------------------
x_(k-1)
Substituting (k-1)(x_(k-1))^2 for y_(k-1) into this expression and
then putting this A_k into the expression for x_k gives
/ 2k - 1 \
x_k = ( ------- ) x_(k-1)
\ 2k /
with the exception that we have x_1 = (x_0 + 1)/2 instead of
(x_0)/2, because we have the initial condition y_0 = x_0 rather
than y_0 = k(x_0)^2. Thus, beginning with x_0 = y_0 = n, the
"rounding up" algorithm in continuous form yields the following
convergent product for x_k
k 2j - 1
x_k = (n+1) PROD --------
j=1 2j
from which it follows that
/ k 2j-1 \2
y_k = k(x_k)^2 = k (n+1)^2 ( PROD ------ )
\ j=1 2j /
Since y_k approximates f(n) in the limit as k goes to infinity,
this relation implies
(n+1)^2 1 / k 2j \2
--------- = lim --- ( PROD ------ )
f(n) k->inf k \ j=1 2j-1 /
which is equivalent to Wallis's infinite product for PI.
Here's a plot showing 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 seive method similar to the seive of Eratosthenes. Starting
with a list of the natural numbers, delete every 2nd element beginning
with the 3rd. This leaves the sequence
1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 ...
From this, delete every 3rd element beginning with the 5th, which
leaves
1 2 4 6 10 12 16 18 22 24 28 30 34 ...
From this, delete every 4th element beginning with the 7th, which
leaves
1 2 4 6 10 12 18 22 24 30 34 ...
From this, delete every 5th element beginning with the 9th, which
leaves
1 2 4 6 10 12 18 22 30 34 ...
In general, from the kth sequence delete every (k+1)th element
beginning with the (2k+1)th element. Notice that this yields the
same sequence f(1),f(2),f(3),... as was produced by the "rounding
up" algorithm. (Is this equivalence obvious?)
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 that Jabotinski and Erdos
proved that
f(n) = n^2/pi + O(n^(4/3))
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 seive method.
No one seems to have noticed the simple "rounding up" algorithm.
By the way, notice how easy it would be to mistake the sequence f(n)
for the cumulative sums of the Euler totient function phi(n):
1 2 4 6 10 12 18 22 28 32 ...
Is this similarity significant?
Return to MathPages Main Menu
Сайт управляется системой
uCoz