7
$\begingroup$

The other day I was asked how to represent really big numbers. I half-jokingly replied to just take the logarithm repeatedly:

$$\log \log \log N$$ makes almost any number $N$ handy. (Assume base 10).

But applying this to Graham's Number probably does zip to make it handy (a handy number is defined as a number less than my or your age in years.) Then just keep applying logarithms. Can anyone estimate or even calculate how often to apply a $\log$ (of base 10, or 3 or $e$ or any handy base) to arrive at a handy number?

$\endgroup$
  • $\begingroup$ So, you want $log^*$ of Graham's number? $\endgroup$ – Dennis Meng Oct 31 '13 at 19:42
  • $\begingroup$ @DennisMeng I'm unfamiliar with that notation; if it means $\log\log\log ...(k \ times) N$ = handy number, then yes, I'm interested in $k$. $\endgroup$ – Jens Oct 31 '13 at 19:46
  • $\begingroup$ I'm used to $log^*$ being defined colloquially as "the number of times you need to take the log", so the little mini-example there would have $log^* N = k$. $\endgroup$ – Dennis Meng Oct 31 '13 at 19:48
  • 1
    $\begingroup$ Is this handy number concept your own creation? I like it. $\endgroup$ – Patrick Oct 31 '13 at 19:55
  • 2
    $\begingroup$ @Patrick Yes, as far as I know. I made it up myself but as so often in science, I may just have reinvented something. A minute ago I asked a search engine. This was futile because "handy number" in German is "cell phone number". :-) $\endgroup$ – Jens Oct 31 '13 at 20:05
10
$\begingroup$

Just getting $3 \uparrow\uparrow\uparrow 3$, which is a power tower of $3 \uparrow 3 \uparrow 3=3^{27}\ \ =7625597484987\ \ 3$'s to be a handy number takes $7625597484985$ applications of the $\log$ to get to $3^3=27$. The logarithm is woefully inadequate for this purpose.

The concept of $\log^*$ is a step in the right direction, but still not enough. We have $\log^* 3 \uparrow\uparrow\uparrow 3=7625597484985$, which isn't handy, but $\log \log^* 3 \uparrow\uparrow\uparrow 3=27$ is. Unfortunately we have a lot more uparrows to go. We probably need to define $\log^{**}$ as the number of times you apply $\log^*$ to get handy, then $\log^{***}$, etc. I suspect we need another (several) layers-define $\log^\&$ as the number of stars you have to put on $\log$ to get a handy number in one go. I have no idea how to do the computation, or even what sort of data structure is appropriate.

$\endgroup$
  • 3
    $\begingroup$ +1 That makes sense. To make such numbers handy a more powerful tool is required. What about an operation that cancels an arrow... a down arrow $\downarrow$ could be the symbol and the operation could be called logarrowthm. I shouldn't drink and post. :-) $\endgroup$ – Jens Oct 31 '13 at 20:58
  • $\begingroup$ $\log^{\&}(n)$ grows about as fast as the inverse Ackermann function $\alpha(n)$. We have $\log^{\&}(G_1)=3$, since $$\log^{**} G_1 = \log^{**} 3 \uparrow^4 3 =\log^{**} 3 \uparrow^3 (3 \uparrow^3 3) \approx 3 \uparrow^3 3$$, which is still too large. On the other hand, $\log^{***} (G_1 )=2$ (or 3, I'm not entirely sure). But $\log^{\&}(G_2)\approx G_1$, which isn't handy. $\log^{\&}(\log^{\&}(G_2))$ is handy, on the other hand. In general, we need to apply $\log^{\&}$ $n$ times to get $G_n$ handy. (This can be proven using induction. It's not difficult). Note: $ \uparrow^k$ is $k$ arrows. $\endgroup$ – wythagoras Dec 4 '16 at 14:24
  • $\begingroup$ If we define $\log^{\&*}$ as the number of times that $\log^{\&}$ has to be applied, then $\log^{\&*}(G_{64})=64$. $\endgroup$ – wythagoras Dec 4 '16 at 14:26
  • $\begingroup$ I absolutely love it! Logarrowthm. $\endgroup$ – return true Mar 12 at 23:17
2
$\begingroup$

Can anyone estimate or even calculate how often to apply a log (of base 10, or 3 or e or any handy base) to arrive at a handy number?

Graham's number $G$ can be written as an exteremely tall exponential tower of $3$s:

$$G \ =\ 3\uparrow\uparrow height $$

With $3$ as the base of the logarithms, you're asking for the $height$ of this tower (or rather $height - 2$, for a handy number of $27$). Now, a formula for the exact height can be found using the following property of Knuth arrows:

$$3\uparrow^x y = 3\uparrow^{x-1}(3\uparrow^x(y-1)) \ \ \ \ (x \ge 2, y \ge 2)$$

Applying this repeatedly gives

$$3\uparrow^x 3 \\ =3\uparrow^{x-1}(3\uparrow^{x}2) \\ =3\uparrow^{x-2}(3\uparrow^{x-1}(3\uparrow^{x}2 - 1))\\ =3\uparrow^{x-3}(3\uparrow^{x-2}(3\uparrow^{x-1}(3\uparrow^{x}2 - 1) - 1)) \\ \cdot\\ \cdot\\ =3\uparrow^2( 3\uparrow^3 (3\uparrow^4 ( \ \cdots \ (3\uparrow^{x-1}(3\uparrow^{x}2 - 1) - 1) \cdots -1 ) ) ) $$

Thus, the handy number 27 is the result of starting with $G$ and applying the base-3 $\log$ exactly $height-2$ times, where $$height = 3\uparrow^3 (3\uparrow^4 ( \ \cdots \ (3\uparrow^{g_{63}-1}(3\uparrow^{g_{63}}2 - 1) - 1) \cdots -1 )) $$

NB: A very crude lower bound on $height$ is given by
$$3\uparrow^{g_{63}} 3 \ = \ 3\uparrow^{g_{63}-1}(3\uparrow^{g_{63}-1}3) \ \ggg \ 3\uparrow^{2}(3\uparrow^{g_{63}-1}3)$$

namely,

$$height \ \ggg \ 3\uparrow^{g_{63}-1}3 $$

which has only one less arrow than $G$ itself!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.