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 10⁴³⁵ 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.

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “Approximate Squaring”

Zack said
June 8, 2021 at 1:04 PM
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

Globules said

June 10, 2021 at 6:53 AM

Here’s a Haskell version.

import Data.Ratio (denominator, numerator)
import System.Environment (getArgs)

approxSq :: Rational -> Rational
approxSq x = x * toRational (ceiling x :: Integer)

iterApproxSq :: Rational -> Integer
iterApproxSq = numerator . head . iterateUntil isInteger approxSq
  where isInteger = (== 1) . denominator
        iterateUntil p f = dropWhile (not . p) . drop 1 . iterate f

main :: IO ()
main = do
  rs <- getArgs
  mapM_ (print . iterApproxSq . read) rs

$ ./approxsq 8%7 3%2 5%2 7%2 9%2 11%2 13%2 15%2 17%2 19%2 3%3 4%3 5%3
48
3
60
14
268065
33
2093
60
1204154941925628
95
1
8
1484710602474311520

Jared said

June 13, 2021 at 8:13 PM

Lisp:
(defun approximate-square (number)
(loop
for n = number then (* n (ceiling n))
when (integerp n)
do (return n)))

> (mapcar #'approximate-square '(8/7 3/2 5/2 7/2 9/2 11/2 13/2 15/2 17/2 19/2 3/3 4/3 5/3))
(48 3 60 14 268065 33 2093 60 1204154941925628 95 1 8 1484710602474311520)

Programming Praxis