Shortest terminating program whose output size exceeds Graham's number
Haskell, 59 57 55 63
(f%s)1=s;(f%s)n=f.(f%s)$n-1
main=print$((flip((%3)%(3^))3)%4)66
How it works: %
simply takes a function and composes it n-1
times on top of s
; i.e. %3
takes a function f
and returns a function of n
that equals applying it f
to 3, n-1
times in a row. If we iterate the application of this higher-order function, we get a fast-growing sequence of functions – starting with exponentiation, it's exactly the sequence of Knuth-arrow-forest sizes:
((%3)%(3^))1 n = (3^)n = 3ⁿ = 3↑n
((%3)%(3^))2 n = ((3^)%3)n = (3↑)ⁿ⁻¹ $ 3 = 3↑↑n
((%3)%(3^))3 n = (((3^)%3)%3)n = (3↑↑)ⁿ⁻¹ $ 3 = 3↑↑↑n
and so on. ((%3)%(3^))n 3
is 3 ↑ⁿ 3
, which is what appears in the calculation to Graham's number. All that's left to do is composing the function (\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3
more than 64 times, on top of 4 (the number of arrows the calculation starts with), to get a number larger than Graham's number. It's obvious that the logarithm (what a lamely slow function that is!) of g₆₅
is still larger than g₆₄=G
, so if we print that number the output length exceeds G
.
⬛
GolfScript (49 47 chars)
4.,{\):i\.0={.0+.({<}+??\((\+.@<i*\+}{(;}if.}do
See Lifetime of a worm for lots of explanation. In short, this prints a number greater than fωω(2).
Pyth, 29 28 bytes
M?*GHgtGtgGtH^ThH=ZTV99=gZTZ
Defines a lambda for hyper-operation and recursively calls it. Like the definition for Graham's number, but with larger values.
This:
M?*GHgtGtgGtH^3hH
Defines a lambda, roughly equal to the python
g = lambda G, H:
g(G-1, g(G, H-1)-1) if G*H else 3^(H+1)
This gives the hyper-operation function, g(G,H) = 3↑G+1(H+1).
So, for example, g(1,2)=3↑23 = 7,625,597,484,987, which you can test here.
V<x><y>
starts a loop that executes the body, y
, x
times.
=gZT
is the body of the loop here, which is equivalent to Z=g(Z,10)
The code:
M?*GHgtGtgGtH^3hH=Z3V64=gZ2)Z
Should recursively call the hyperoperation above 64 times, giving Graham's Number.
In my answer, however, I've replaced the single digits with T
, which is initialized to 10, and increased the depth of recursion to 99. Using Graham Array Notation, Graham's Number is [3,3,4,64], and my program outputs the larger [10,11,11,99]. I've also removed the )
that closes the loop to save one byte, so it prints each successive value in the 99 iterations.