The last few months have been a little crazy with consulting work and hence tweeting, blogging, comic, and general recreational math have taken a back seat. Last week, I finally had a “normal” week and I wandered over to Ben Vitale’s blog, where I got to read about this puzzle.
The rules are simple: using the factorial symbol, square root function, ceiling function, and floor function, find compositions that will lead to a fixed point solution for a given positive integer \(n\). For example, \(n = 3\) we have this as one solution:
$$\lceil \sqrt{3!} \rceil = 3$$
Notice that \(3! = 6\) whose square root is between 2 and 3, which when rounded up is 3, as desired. Also, notice that since we have solved this for \(n = 3\), we have also solved it for \(n = 6\) since 6 was an integer produced through the sequence of function compositions. Namely,
$$\lceil \sqrt{6} \rceil ! = 6$$
as all I did was shift the order of the function compositions. (Generally, we’d have to take care since we want to avoid taking the factorial of a non-integer. And yes, we could still do this with the use of the gamma function, but this article is about dumb programs and I want to stay in the realm of stupid.) You’ll notice that Ben used the double factorial and thus produced a different, minimal version for \(n = 6\). By “minimal” I mean number of function compositions required. Here’s a solution posted by Ben for \(n = 6\) utilizing double factorial (the factorial symbol is allowed, thus factorial, double factorial, and sub factorial are allowable functions):
$$\lfloor \sqrt{6!!} \rfloor$$
Since, 6!! = 48 whose square root is between 6 and 7, which when rounded down is 6, gives the desired solution. This means that we don’t necessarily have unique minimal representations for a given \(n\).
I putzed around with these by hand just to get a feel for how tricky this would be and to see if I could come up with some simple heuristics for stumbling into a solution — I didn’t really care if the solution was minimal. A few things were immediately apparent: I don’t want a sequence of function compositions to get me to 2 or lower as I would be stuck (unless if \(n \leq 2\)). If I get to 3 or 4, I need to use the factorial symbol next. If I get to a number between 2 and 3, I need to use the ceiling function. There were also some numerical headaches — \(k!\) can get out of hand pretty quickly and taking square roots then becomes a pain. I wasn’t terribly worried about the factorial since that would be integer computation and Python is pretty good about integer based computation. For example, \(80!\) is not an issue:
>>> factorial(80)
71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
Even \(1000!\) won’t be a problem to compute (displaying it is another matter). It’s just that at some point, Python’s built-in square root method is going to either get hit with a numerical overflow or I’ll lose all sorts of precision because of the floating point nature of the computation. Truth be told, I just turned a blind eye to numerical precision issues and just ensured that I wouldn’t get numerical overflow. I suppose I could have gone with the decimal module.
So with a little bit of Python and a little bit of \(\LaTeX\) here are some fun solutions that I found for various \(n\). The code is at the end of this article — and you’ll see why it is rather dumb.
$$\Bigg\lfloor \sqrt{\sqrt{\sqrt{\sqrt{42!!}}}} \Bigg\rfloor = 42$$
$$\lfloor \sqrt{48} \rfloor !! = 48$$
\(n = 48\) can actually be solved by hand since \(6!! = 48\) and luckily enough \(6 < \sqrt{48} < 7\), which means it’s just a matter of rounding down the square root so we can take its double factorial. Recall, Ben’s solution for \(n = 6\).
But then, I found some “crazy” minimal or near-minimal solutions that are a pain to typeset. \(n = 30\) isn’t so bad, other than the consecutive factorials have to not be confused notationally with double factorial.
$$\Bigg\lfloor \sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil \sqrt{\Bigg\lfloor \sqrt{30} \Bigg\rfloor!!}\Bigg\rceil!\Bigg)!}}}} \Bigg\rfloor = 30$$
\(n = 55\) was a horrid mess to type and probably just as atrocious (yet beautiful) to look at.
$$ \Bigg\lceil \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg\lfloor \sqrt{\sqrt{
\Bigg\lceil \sqrt{\sqrt{\sqrt{\Bigg\lfloor \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{55!}}}}}} \Bigg\rfloor!}}} \Bigg\rceil !!}}\Bigg\rfloor !}}}}}} \Bigg\rceil = 55$$
I suppose I could have written more code to generate the correct \(\LaTeX\), but I don’t have that much free time — also, it’s just a good exercise to see how well my eyes are doing.
$$ \Bigg\lceil \sqrt{\sqrt{\sqrt{\sqrt{\Bigg\lceil \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg\lfloor \sqrt{\sqrt{\Bigg\lfloor \sqrt{\Bigg\lfloor \sqrt{60}\Bigg\rfloor!!}\Bigg\rfloor!}}\Bigg\rfloor!}}}}}\Bigg\rceil!!}}}} \Bigg\rceil = 60$$
But, wait, I lied! If I sacrifice a little sleep, then I do have enough free time for this. Here’s 20 to 48 with the \(\LaTeX\) autogenerated (and so, hopefully, it’s correct.). I went a little nuts with parentheses mostly because I didn’t care to deal with sequential factorials and double factorials — not like it actually changes readability of this gorgeous mess.
$$\Bigg\lceil\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{20}\Bigg\rfloor!!\Bigg)!!\Bigg)}\Bigg\rceil = 20$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{21}\Bigg\rceil!\Bigg)}\Bigg\rfloor!!\Bigg)}\Bigg\rfloor!!\Bigg)}}}}}\Bigg\rceil = 21$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{22}\Bigg\rceil!!\Bigg)!!\Bigg)}}\Bigg\rfloor!\Bigg)}}}}}\Bigg\rfloor = 22$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{23}\Bigg\rfloor!!\Bigg)!\Bigg)}}\Bigg\rfloor!\Bigg)}}}\Bigg\rfloor = 23$$
$$\Bigg(\Bigg\lfloor\sqrt{24}\Bigg\rfloor!\Bigg) = 24$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(25!\Bigg)}}}}\Bigg\rceil!\Bigg)}}}}}\Bigg\rceil = 25$$
$$\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{26}\Bigg\rceil!\Bigg)}\Bigg\rfloor = 26$$
$$\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{27}\Bigg\rceil!\Bigg)}\Bigg\rceil = 27$$
$$\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lfloor\sqrt{28}\Bigg\rfloor!!\Bigg)}\Bigg\rceil!!\Bigg)!\Bigg)}}\Bigg\rfloor!!\Bigg)}}\Bigg\rfloor = 28$$
$$\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lfloor\sqrt{29}\Bigg\rfloor!!\Bigg)}\Bigg\rceil!!\Bigg)!\Bigg)}}\Bigg\rfloor!!\Bigg)}}\Bigg\rceil = 29$$
$$\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{30}\Bigg\rceil!!\Bigg)}\Bigg\rceil!\Bigg)}}\Bigg\rceil!!\Bigg)}\Bigg\rfloor = 30$$
$$\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{31}\Bigg\rceil!!\Bigg)}\Bigg\rceil!\Bigg)}}\Bigg\rceil!!\Bigg)}\Bigg\rceil = 31$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{32}\Bigg\rfloor!!\Bigg)!\Bigg)}}}\Bigg\rfloor = 32$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{33}\Bigg\rfloor!!\Bigg)!\Bigg)}}}\Bigg\rceil = 33$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lfloor\sqrt{34}\Bigg\rfloor!!\Bigg)}\Bigg\rceil!\Bigg)!!\Bigg)}}}\Bigg\rfloor = 34$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lfloor\sqrt{35}\Bigg\rfloor!!\Bigg)}\Bigg\rceil!\Bigg)!!\Bigg)}}}\Bigg\rceil = 35$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\sqrt{36}!\Bigg)}}\Bigg\rfloor!\Bigg)!!\Bigg)}}}}}}\Bigg\rfloor = 36$$
$$\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{37}\Bigg\rfloor!\Bigg)}}\Bigg\rfloor!!\Bigg)!!\Bigg)}}\Bigg\rfloor = 37$$
$$\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{38}\Bigg\rfloor!\Bigg)}}\Bigg\rfloor!!\Bigg)!!\Bigg)}}\Bigg\rceil = 38$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{39}\Bigg\rceil!\Bigg)}\Bigg\rceil!\Bigg)}}}}}}\Bigg\rfloor = 39$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{40}\Bigg\rceil!\Bigg)}\Bigg\rceil!!\Bigg)}}}}}\Bigg\rfloor = 40$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{41}\Bigg\rceil!\Bigg)}\Bigg\rceil!!\Bigg)}}}}}\Bigg\rceil = 41$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(42!!\Bigg)}}}}\Bigg\rfloor = 42$$
$$\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{43}\Bigg\rceil!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rfloor = 43$$
$$\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{44}\Bigg\rceil!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rceil = 44$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lceil\sqrt{45}\Bigg\rceil!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rfloor!\Bigg)}}}}}\Bigg\rceil = 45$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{46}\Bigg\rfloor!\Bigg)}\Bigg\rfloor!\Bigg)}}}}\Bigg\rfloor = 46$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{47}\Bigg\rfloor!\Bigg)}\Bigg\rfloor!\Bigg)}}}}\Bigg\rceil = 47$$
$$\Bigg(\Bigg\lfloor\sqrt{48}\Bigg\rfloor!!\Bigg) = 48$$
I got tired of waiting for \(n = 49\) to finish so I aborted the simulations at around 2300 trials and observed this as the smallest.
And we would say it like this
The floor of the square root of the square root of the square root of the square root of the square root of the double factorial of the floor of the square root of the square root of the square root of the square root of the square root of the double factorial of the ceiling of the square root of the square root of the square root of the square root of the square root of the double factorial of the floor of the square root of the square root of the square root of the square root of the square root of the factorial of the double factorial of the ceiling of the square root of the square root of the factorial of the factorial of the ceiling of the square root of the square root of the square root of the factorial of the square root of forty-nine equals forty-nine.
(Don’t worry that phrase was autogenerated.)
There was one case for \(n = 49\) where the function composition chain was around 163887 long, but that’s what I get with dumb programs.
The Code
How dumb is the code? It’s this dumb.
>>> def fp(n): def identity(x): return x def doublefactorial(x): s = 1 if x%2 == 0: for i in range(2,x,2): s *= i s *= x else: for i in range(1,x,2): s *= i s *= x return s funcs = [math.factorial, math.sqrt, doublefactorial, math.ceil, math.floor] fseq = [random.choice(funcs[:3])] v = fseq[0](n) f0 = None f = None while v != n: if math.ceil(v) == n: f = math.ceil elif math.floor(v) == n: f = math.floor elif v > 150: f = math.sqrt elif v < 3: f = math.ceil elif int(v) == v: f = random.choice(funcs[:3]) else: f = random.choice(funcs) if (f == math.factorial or f == doublefactorial) and int(v) != v: f0 = random.choice(funcs[3:]) else: f0 = identity try: f(f0(v)) except Exception as e: continue finally: pass if f(f0(v)) <= 2: continue if f0 != identity: fseq.append(f0) fseq.append(f) v = f(f0(v)) return fseq
And that just generates one random solution. For any given number, I can get a good guess as to what a minimal solution is with this wrapper code --- the highlight is that I get to use Python's for-else.
>>> for i in range(10000):
if len(s) == 10000:
s = []
s.append(fp(60))
else:
m = min(len(j) for j in s)
for j in s:
if len(j) == m:
print(j)
break
And this generates the \(\LaTeX\)
>>> def functotex(funclist,v):
ftexmap = {"floor": ["\\Bigg\\lfloor","\\Bigg\\rfloor"],"ceil": ["\\Bigg\\lceil","\\Bigg\\rceil"],"sqrt":["\\sqrt{","}"],"factorial":["\\Bigg(","!\\Bigg)"],"doublefactorial":["\\Bigg(","!!\\Bigg)"]}
texlist = []
cursor = 0
n = len(texlist)
for f in reversed(funclist):
if "floor" in str(f):
texlist.insert(cursor,ftexmap["floor"][0])
cursor += 1
texlist.insert(cursor,ftexmap["floor"][1])
n += 2
if "ceil" in str(f):
texlist.insert(cursor,ftexmap["ceil"][0])
cursor += 1
texlist.insert(cursor,ftexmap["ceil"][1])
n += 2
if "sqrt" in str(f):
texlist.insert(cursor,ftexmap["sqrt"][0])
cursor += 1
texlist.insert(cursor,ftexmap["sqrt"][1])
n += 2
if "factorial" in str(f) and "doublefactorial" not in str(f):
texlist.insert(cursor,ftexmap["factorial"][0])
cursor += 1
texlist.insert(cursor,ftexmap["factorial"][1])
n += 2
if "doublefactorial" in str(f):
texlist.insert(cursor,ftexmap["doublefactorial"][0])
cursor += 1
texlist.insert(cursor,ftexmap["doublefactorial"][1])
n += 2
texlist.insert(cursor,str(v))
return texlist, "".join(texlist)
Musings
I didn't really make too big of a study of this. If we look at successive solutions long enough, it feels that there is some general principle at play to recursively generate solutions, but that's a magic in and of itself.
A basic observation is that the sequence of function compositions produces a sequence of numbers that oscillate to the solution. In general, we overshoot with factorials and steadily come down with square roots.
Another basic observation is that hacking together a programmatic solution is fun and even a dumb program can give good solutions, though it did get stuck for \(n = 49\).
Of course, one simple improvement would be that as soon as a solution is found, I should have my program check for a shorter path within the sequence of compositions by tracking the sequence of values that result at each composition step. If I were to find a duplicate value, then I can clearly shorten the sequence. For example, if I observe the following collection of \(x_{i} \in \mathbb{R}\) where the \(x_{i}\) are unique in the following sample sequence:
$$n, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{3}, x_{6}, n$$
then, rather than continue from \(x_{3}\) to \(x_{4}\) it is shorter to branch to \(x_{6}\) to \(n\) since there is a valid sequence of function compositions that allows this. But I'm writing a dumb program. 🙂
Anyhow, here are a few last ones for the road:
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{50}\Bigg\rfloor!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rceil!\Bigg)}}}}}\Bigg\rfloor = 50$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\sqrt{51}}\Bigg\rceil!\Bigg)!\Bigg)}\Bigg\rfloor!!\Bigg)}}}\Bigg\rfloor = 51$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg(\Bigg\lceil\sqrt{\sqrt{52}}\Bigg\rceil!\Bigg)!\Bigg)}\Bigg\rfloor!!\Bigg)}}}\Bigg\rceil = 52$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{53}\Bigg\rfloor!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rceil!!\Bigg)}}}}\Bigg\rfloor = 53$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\Bigg(\Bigg\lfloor\sqrt{54}\Bigg\rfloor!!\Bigg)}\Bigg\rfloor!\Bigg)}}\Bigg\rceil!!\Bigg)}}}}\Bigg\rceil = 54$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{55}\Bigg\rfloor!\Bigg)}}\Bigg\rceil!!\Bigg)}\Bigg\rceil!\Bigg)}}}}\Bigg\rfloor!\Bigg)}}}}}}}\Bigg\rceil = 55$$
$$\Bigg\lfloor\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(56!!\Bigg)}}}}}\Bigg\rceil!!\Bigg)}}\Bigg\rfloor = 56$$
$$\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(57!!\Bigg)}}}}}\Bigg\rfloor!!\Bigg)}}\Bigg\rceil = 57$$
$$\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(58!!\Bigg)}}}}}\Bigg\rfloor!!\Bigg)}}\Bigg\rceil!\Bigg)}}}}}}\Bigg\rfloor = 58$$
$$\Bigg\lceil\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(\Bigg\lceil\sqrt{\sqrt{\Bigg(\Bigg\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\Bigg(59!\Bigg)}}}}}}\Bigg\rfloor!!\Bigg)}}\Bigg\rceil!\Bigg)}}}}}}\Bigg\rceil = 59$$