Skip to main content
Forgot parenthesis.
Source Link
Cel Skeggs
  • 921
  • 6
  • 10

The number expressed in the program above is A(0,1,2,3,4,...,123,124,125).

The number expressed in the program above is A(0,1,2,3,4,...,123,124,125.

The number expressed in the program above is A(0,1,2,3,4,...,123,124,125).

Source Link
Cel Skeggs
  • 921
  • 6
  • 10

Python 3 - 99 chars - (most likely) significantly larger than Graham's number

I've come up with a more quickly increasing function based on an extension of the Ackermann function.

A=lambda a,b,*c:A(~-a,A(a,~-b,*c)if b else a,*c)if a else(A(b,*c)if c else-~b);A(*range(ord('~')))

http://fora.xkcd.com/viewtopic.php?f=17&t=31598 inspired me, but you don't need to look there to understand my number.

Here is the modified version of the ackermann function that I'll be using in my analysis:

A(b)=b+1
A(0,b,...)=A(b,...)
A(a,0,...)=A(a-1,1,...)
A(a,b,...)=A(a-1,A(a,b-1,...),...)

My function A in the code above is technically not the same, but it is actually stronger, with the following statement to replace the third line of the above definition:

A(a,0,...)=A(a-1,a,...)

(a has to be at least 1, so it has to be stronger)

But for my purposes I will assume that it is the same as the simpler one, because the analysis is already partially done for Ackermann's function, and therefore for this function when it has two arguments.

My function is guaranteed to eventually stop recursing because it always either: removes an argument, decrements the first argument, or keeps the same first argument and decrements the second argument.

Analysis of size

Graham's number, AFAIK, can be represented as G(64) using:

G(n) = g^n(4)
g(n) = 3 ↑^(n) 3

Where a ↑^(n) b is knuth's up-arrow notation.

As well:

A(a,b) = 2 ↑^(a-2) (b+3) - 3
A(a,0) ≈ 2 ↑^(a-2) 3
g(n) ≈ A(n+2,0) // although it will be somewhat smaller due to using 2 instead of 3. Using a number larger than 0 should resolve this.
g(n) ≈ A(n+2,100) // this should be good enough for my purposes.

g(g(n)) ≈ A(A(n+2,100),100)

A(1,a+1,100) ≈ A(0,A(1,a,100),100) = A(A(1,a,100),100)

g^k(n) ≈ A(A(A(A(...(A(n+2,100)+2)...,100)+2,100)+2,100)+2,100) // where there are k instances of A(_,100)
A(1,a,100) ≈ A(A(A(A(...(A(100+2),100)...,100),100),100),100)

g^k(100) ≈ A(1,k,100)
g^k(4) < A(1,k,100) // in general
g^64(4) < A(1,64,100)

The number expressed in the program above is A(0,1,2,3,4,...,123,124,125.

Since g^64(4) is Graham's number, and assuming my math is correct then it is less than A(1,64,100), my number is significantly larger than Graham's number.

Please point out any mistakes in my math - although if there aren't any, this should be the largest number computed so far to answer this question.