2007-01-27 by
qntm

The author of xkcd has asked in his blag which is bigger: the "clarkkkkson", an exotic number defined on this page, or what he calls the "xkcd number", which is defined in panel three of this xkcd comic.

My calculations have led me to conclude that the clarkkkkson is the larger of the two.

`X` is the Ackermann function with Graham's number as both its arguments. In terms of hyper operators, this is:

X = hyper(2,G_{64},G_{64}+3)-3

where

G_{1}= hyper(3,6,3) G_{n+1}= hyper(3,G_{n}+2,3).

(Full version here)

Define the "multifactorial" function (denoted by multiple exclamation marks) recursively as:

k=a a! = Π k k=1 k=a a!!!...! = Π k!!!...! \_____/ k=1 \_____/ b b-1

Now define the "hyperfactorial" function `hypf` as

hypf(a,b,c) = c!!!...! ↑↑↑...↑ (c-1)!!!...! ↑↑↑...↑ ... ↑↑↑...↑ 2!!!...! ↑↑↑...↑ 1!!!...! \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ a b-2 a b-2 b-2 a b-2 a

where the up-arrows work as in Knuth's up-arrow notation.

Define the Clarkkkkson function `ck` as

ck(a,b,c,1) = hypf(a,b,c) ck(a,b,c,d) = hypf(a,b,ck(a,b,c,d-1))

Then finally define the Alpha function `A` (my own creation to simplify the working) as

A(a) = ck(a,a,a,a)

Then the clarkkkkson is equal to

C = A^{K}(K)

where `K` is a variable which increases rapidly in real time. `K` was equal to one googolplex (10^{10100}) at 6:34:15am on August 9th, 1999 and squares every 24 hours. At the time of writing it has squared 2728 times since then, making it equal to roughly 10^{10921}.

First note that `A`, `ck`, `hypf` and `hyper` are all strictly increasing in all their arguments.

Proof that the clarkkkkson exceeds the xkcd number first involves establishing a relation between the somewhat nonstandard "hyperfactorial" function and the more conventional `hyper` function, as follows:

hypf(a,b,c) = c!!!...! ↑↑↑...↑ (c-1)!!!...! ↑↑↑...↑ ... ↑↑↑...↑ 2!!!...! ↑↑↑...↑ 1!!!...! \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ \_____/ a b-2 a b-2 b-2 a b-2 a > c ↑↑↑...↑ (c-1) ↑↑↑...↑ ... ↑↑↑...↑ 2 ↑↑↑...↑ 1 \_____/ \_____/ \_____/ \_____/ b-2 b-2 b-2 b-2 > c ↑↑↑...↑ (c-1) \_____/ b-2 = hyper(c,b,c-1)

Now consider `A`(6).

A(6) = ck(6,6,6,6) = hypf(6,6,ck(6,6,6,5)) > hyper(ck(6,6,6,5),6,ck(6,6,6,5)-1) > hyper(3,6,3) = G_{1}

Now inductively, suppose `A`^{k}(6) > `G`_{n}. Then

A^{k+2}(6) = A(A(A^{k}(6))) > A(A(G_{n})) = A(ck(G_{n},G_{n},G_{n},G_{n})) = A(hypf(G_{n},G_{n},ck(G_{n},G_{n},G_{n},G_{n}-1))) > A(hyper(ck(G_{n},G_{n},G_{n},G_{n}-1),G_{n},ck(G_{n},G_{n},G_{n},G_{n}-1)-1)) > A(hyper(3,G_{n},3)) = ck(hyper(3,G_{n},3),hyper(3,G_{n},3),hyper(3,G_{n},3),hyper(3,G_{n},3)) > ck(3,hyper(3,G_{n},3),3,3) = hypf(3,hyper(3,G_{n},3),ck(3,hyper(3,G_{n},3),3,2)) > hypf(3,hyper(3,G_{n},3),4) > hyper(4,hyper(3,G_{n},3),3) > hyper(3,G_{n}+2,3) = G_{n+1}

Thus `A`^{2n-1}(6) > `G`_{n} for all `n`, and specifically `A`^{127}(6) > `G`_{64} = Graham's number.

Likewise,

A^{128}(6) = A(A^{127}(6)) > A(G_{64}) = ck(G_{64},G_{64},G_{64},G_{64}) = hypf(G_{64},G_{64},ck(G_{64},G_{64},G_{64},G_{64}-1)) > hyper(ck(G_{64},G_{64},G_{64},G_{64}-1),G_{64},ck(G_{64},G_{64},G_{64},G_{64}-1)-1) > hyper(2,G_{64},G_{64}+3) > hyper(2,G_{64},G_{64}+3)-3 = X

Finally:

C = A^{K}(K) > A^{128}(K) > A^{128}(6) > X

QED.

`K` is actually an increasing function of time, `K`(`t`). Likewise, the clarkkkkson, `C` = `A`^{K}(`K`) is also an increasing function of time,

C(t) = A^{K(t)}(K(t))

This naturally leads to the question: was there ever a time `t` when `C`(`t`) was *less* than `X`? If so, what was the value of `K`(`t`) at this time?

Initially (at `t`=0) `K` was equal to 100 and it doubled every 24 hours from that point onwards. As `K` represents a number of "lynz" it must always be an integer, so we have

K(t) = round(100 * 2^{t})

From the calculations above, we already know that

A^{128}(128) > X

so we know that `C`(`t`) exceeded `X` some time before `K`(`t`) exceeded 128, that is, less than 8 hours, 32 minutes and 51 seconds after the lynz were set. This provides a nominal upper bound.

As for lower bounds, we have

A^{1}(1) = ck(1,1,1,1) = hypf(1,1,1) = 1! = 1 A^{2}(2) = A(ck(2,2,2,2)) = A(hypf(2,2,ck(2,2,2,1))) = A(hypf(2,2,hypf(2,2,2))) = A(hypf(2,2,2)) = A(2) = ck(2,2,2,2) = hypf(2,2,ck(2,2,2,1)) = hypf(2,2,hypf(2,2,2)) = hypf(2,2,2) = 2 A^{3}(3) = A^{2}(ck(3,3,3,3)) = A^{2}(hypf(3,3,ck(3,3,3,2))) = A^{2}(hypf(3,3,hypf(3,3,ck(3,3,3,1)))) = A^{2}(hypf(3,3,hypf(3,3,hypf(3,3,3)))) = A^{2}(hypf(3,3,hypf(3,3,576))) = ...

However, at this point the calculations become unwieldy, which is unfortunate, since the lowest value that `C` ever took was `A`^{100}(100).

It is quite likely that `A`^{100}(100) exceeds `X`, meaning that the clarkkkkson was ALWAYS greater than the xkcd number, but right now all we can say with certainty is that 2 < `K`* < 128 where `K`* is the critical value of `K`(`t`).