Solution
First, the problem was conjectured by Donald Knuth some years ago using Floor only (and not Ceiling), so the discussion below will use that setup.
Second, Joseph DeVincentis observed that it can be stated in this form:
Can one start at 3 and reach any integer by iterating factorial, sqrt, and floor?
This is the form Knuth had as well. It suffices because any number can be brought down to 3 or 4 by repeating square roots. And getting from 4 to 3 can be done by
Floor[Sqrt[Sqrt[Floor[Sqrt[Sqrt[Sqrt[Sqrt[Sqrt[(4!)!]]]]]]!]]] = 3
So if we can get from 3 to n, then we can get from n to n.
The computational problem is to start at 3 and start building up a table of what is reachable. Of course, the giant factorials become unwieldy. Dick Hess programmed his own Stirling formula approximation; Mathematica has LogGamma built-in. So that allows one to go quite far.
There are issues of how to store numbers, whether to work with integers or machine reals, whether to store the paths found for every n, and so on. While it seems as if roundoff error would be a killer, in fact the situation is quite stable, so that even working with machine reals seems adequate to get reliable paths (which can be checked after the fact using ultra-high precision).
The current state is as follows.
I obtained paths from 3 to every number up to 131110 (using only floor).
Dick Hess (using floor and ceiling) has gotten up to 40389 by taking 199 generations and keeping track of numbers (i.e., logfactorial numbers, so in fact he is checking up to 48 million factorial) under 48 million. He then dumped Ceiling and confirmed that 3034 is the first unresolved one regarding Knuth's conjecture of 3034.
I have not found much online about whether others have checked this conjecture to these realms. In any case, the evidence is quite strong that all numbers can be reached from 3. My code keeps all the paths, so I could perform a post-processing check of all the paths for integers up to 3033, and the machine-real paths all check out when switched to integers.
For just one example, the following solves 2284, where each number comes from the previous by taking factorial, and then an appropriate number of square roots:
{3, 6, 720, 2576, 5560, 176, 101072, 3344, 111275, 8232, 9931008, 7668, 1698, 43422, 371682, 19139806, 64854116, 13482374, 240194, 34049, 18117, 16920,
8286, 11184919, 25680, 1702067, 50657, 3996997, 753899, 67109721, 24693657, 132069, 52744, 2824}
View online the (large!) text file (19M) of data on the Knuth Conjecture, or download a zipped version (6.6M).
Thanks to Joseph, Al Zimmermann, and Dick Hess for help with this intriguing problem.
[Back to Problem 1171]
© Copyright 2013 Stan Wagon. Reproduced with permission.