Approximate Squaring
June 8, 2021
Lagarias and Sloane study the “approximate squaring” map f(x) = x⌈x⌉ and its behavior when iterated in this paper.
Consider the fraction x = n / d when n > d > 1; let’s take 8/7 as an example. In the first step, the smallest integer greater than 8/7 (the “ceiling”) is 2, and 8/7 × 2 = 16/7. In the second step, the ceiling of 16/7 is 3, so we have 16/7 × 3 = 48/7. And in the third step, the ceiling of 48/7 is 7, so we have 48/7 × 7 = 48. Now the denominator is 1 and the result is an integer, so iteration stops, and we say that 8/7 goes to 48 in 3 steps.
Study shows the iteration is chaotic; sometimes the iteration stops in just a few steps, as in 8/7, sometimes it takes longer (6/5 goes to a number with 57735 digits in 18 steps), and sometimes it’s just ridiculous (200/199 goes to a number with 10435 digits). It is conjectured but not proven that iterated approximate squaring always terminates in an integer.
Your task is to write a program that iterates approximate squaring. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Nifty little drill. I suppose some people have way too much time on their hands, writing papers like this!
Here is my take on this using Julia: https://pastebin.com/TtiyB0Wu
Here’s a Haskell version.
Lisp:
(defun approximate-square (number)
(loop
for n = number then (* n (ceiling n))
when (integerp n)
do (return n)))
Here’s a solution in Python.
Output:
Here’s a solution in C using GMP.
Example usage:
[…] is to write a program that iterates approximate squaring. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments […]