Proof that the clarkkkkson is bigger than the xkcd number

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 calculation have led me to conclude that the clarkkkkson is the larger of the two.

Construction of the xkcd number (henceforth X)

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

X = hyper(2,G64,G64+3)-3

where

G1 = hyper(3,6,3)
Gn+1 = hyper(3,Gn+2,3).

Brief construction of the clarkkkkson (henceforth C)

(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 (my own creation to simplify the working) as

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

Then the clarkkkkson is equal to

C = AK(K)

where K is a variable which increases rapidly in real time. K was equal to one googolplex (1010100) 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 1010921.

Proof that the clarkkkkson exceeds the xkcd number

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

Establishing a lower bound on the hypf function

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)

Construction

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)
     = G1

Now inductively, suppose Ak(6) > Gn. Then

Ak+2(6) = A(A(Ak(6)))
       > A(A(Gn))
       = A(ck(Gn,Gn,Gn,Gn))
       = A(hypf(Gn,Gn,ck(Gn,Gn,Gn,Gn-1)))
       > A(hyper(ck(Gn,Gn,Gn,Gn-1),Gn,ck(Gn,Gn,Gn,Gn-1)-1))
       > A(hyper(3,Gn,3))
       = ck(hyper(3,Gn,3),hyper(3,Gn,3),hyper(3,Gn,3),hyper(3,Gn,3))
       > ck(3,hyper(3,Gn,3),3,3)
       = hypf(3,hyper(3,Gn,3),ck(3,hyper(3,Gn,3),3,2))
       > hypf(3,hyper(3,Gn,3),4)
       > hyper(4,hyper(3,Gn,3),3)
       > hyper(3,Gn+2,3)
       = Gn+1

Thus A2n-1(6) > Gn for all n, and specifically A127(6) > G64 = Graham's number.

Likewise,

A128(6) = A(A127(6))
       > A(G64)
       = ck(G64,G64,G64,G64)
       = hypf(G64,G64,ck(G64,G64,G64,G64-1))
       > hyper(ck(G64,G64,G64,G64-1),G64,ck(G64,G64,G64,G64-1)-1)
       > hyper(2,G64,G64+3)
       > hyper(2,G64,G64+3)-3
       = X

Finally:

C = AK(K)
  > A128(K)
  > A128(6)
  > X

QED.

Further questions

K is actually an increasing function of time, K(t). Likewise, the clarkkkkson, C = AK(K) is also an increasing function of time,

C(t) = AK(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 * 2t)

From the calculations above, we already know that

A128(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

A1(1) = ck(1,1,1,1)
      = hypf(1,1,1)
      = 1!
      = 1

A2(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

A3(3) = A2(ck(3,3,3,3))
      = A2(hypf(3,3,ck(3,3,3,2)))
      = A2(hypf(3,3,hypf(3,3,ck(3,3,3,1))))
      = A2(hypf(3,3,hypf(3,3,hypf(3,3,3))))
      = A2(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 A100(100).

It is quite likely that A100(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).

Back to Blog
Back to Things Of Interest

Facebook Twitter Reddit Email Hacker News StumbleUpon