0

I'm reading Don Knuth's "Selected Papers on Fun & Games" and early on there's a paper called "Representing numbers using only one 4".

He does 64 and then starts to verify it like this

$$64=\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}\lfloor\sqrt{}\lfloor\sqrt{}\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}(4!)!\rfloor!\rfloor!\rfloor!\rfloor!\rfloor!\rfloor!\rfloor!\rfloor$$ (In this representation, the notation $\sqrt{}x!$ stands for $\sqrt{}(x!)$, not $ (\sqrt{}x)!$. Parentheses have been placed in the subformula '$(4!)!$' because the unparenthesized expression '$4!!$' traditionally means $4\cdot2$.) To verify this formula we will compute successively the quantities inside each of the nested brackets. The innermost floor brackets represent the number $5$, since$$5^{32} = 232\,83064\,36538\,69628\,90625\\24! = 6204\,48401\,73323\,94393\,60000\\6^{32} = 79586\,61109\,94640\,08843\,91936$$ and hence $\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}24!\rfloor = 5$.

I understand why $24!$ being between $5^{32}$ and $6^{32}$ is relevant and eventually I'll understand how the floors and the square roots crunch that to a $5$. But why are we raising it to $^{32}$? How could I tell in future when looking at that inner $\lfloor\sqrt{}\sqrt{}\sqrt{}\sqrt{}\sqrt{}24!\rfloor$ that I need to compare this to $5$ and $6$ raised to the $^{32}$nd power?

Stan Vest
  • 3
  • It's not that there's anything particular about $32$. Knuth just wants to square root $24!$ down to a manageable number, and so the only possible roots are powers of $2$; that is, he can take a square root, a fourth root, an eighth root, a sixteenth root, a thirty-second root, etc. – Brian Tung May 27 '19 at 16:23

3 Answers3

2

$$\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{ x}}}}} = ((((x^{1/2})^{1/2})^{1/2})^{1/2})^{1/2} = x^{1/2^{5}} = x^{1/32}$$

So if $5^{32} < 24! < 6^{32}$, then $5 < (24!)^{1/32} < 6$, and $\lfloor (24!)^{1/32}\rfloor = 5$

eyeballfrog
  • 22,485
1

$$ \left\lfloor\sqrt {\sqrt{\sqrt{\sqrt{\sqrt{24!}}}}}\right\rfloor=5$$ is equivalent to $$ 5\le \sqrt {\sqrt{\sqrt{\sqrt{\sqrt{24!}}}}}<6$$ is equivalent to $$ 5^2\le {\sqrt{\sqrt{\sqrt{\sqrt{24!}}}}}<6^2$$ is equivalent to $$ 5^4\le {{\sqrt{\sqrt{\sqrt{24!}}}}}<6^4$$ is equivalent to $$ 5^8\le {{{\sqrt{\sqrt{24!}}}}}<6^4$$ is equivalent to $$ 5^{16}\le {{{{\sqrt{24!}}}}}<6^{16}$$ is equivalent to $$ 5^{32}\le {{{{{24!}}}}}<6^{32}$$

Hagen von Eitzen
  • 374,180
0

The motivation here is that taking five square roots is the same as taking a number to the power of $\frac{1}{32}$. Powering numbers to $32$ to remove this is now the obvious next step, and proving that $24!$ is between $5^{32}$ and $6^{32}$ gives the answer of $5$.

auscrypt
  • 8,186
  • Perfect, I was so close to figuring this out before I posted but my line of thinking was off. When I saw the 5 $\sqrt{}$, I thought 1, 2, 4, 8, 16 when I should have been thinking 2, 4, 8, 16, 32. Thanks. – Stan Vest May 27 '19 at 16:38