37
\$\begingroup\$

Write the shortest possible program (length measured in bytes) satisfying the following requirements:

  • no input
  • output is to stdout
  • execution eventually terminates
  • total number of output bytes exceeds Graham's number

Assume that programs run until "normal" termination on an ideal computer1 able to access unlimited resources, and that the common programming languages are modified if necessary (without changing the syntax) to allow this. Because of these assumptions, we might call this a kind of Gedankenexperiment.

To get things started, here's a 73-byte Ruby program that computes fω+1(99) in the fast-growing hierarchy:

f=proc{|k,n|k>0?n.times{n=f[k-1,n]}:n+=1;n};n=99;n.times{n=f[n,n]};puts n

1 EDIT: More precisely, suppose we're taking an existing system and modifying it only to have no upper limit on storage size (but it is always finite). The execution-times of instructions are not supposed to be modified, but the machine is assumed to be ideal in that it will have no upper limit on its operating lifetime.

\$\endgroup\$
  • \$\begingroup\$ This takes my tetration question to a whole new level! \$\endgroup\$ – MrZander Jun 25 '12 at 3:47
  • 1
    \$\begingroup\$ There was once a similar programming contest called the Bignum Bakeoff. Some of the entries are quite interesting; the results are here: djm.cc/bignum-results.txt \$\endgroup\$ – Danny Chia Jun 9 '13 at 19:01
11
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ f_(ω^ω)(2) is about as large as g_(f_8(8)), so not as overkill as that expression would imply. \$\endgroup\$ – Simply Beautiful Art Dec 3 '17 at 20:47
21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ When I test this with print$((flip((%3)%(3*))3)%2)1, there's a run-time error - can you say why? It succeeds when the 2 is changed to 1 (output is 81). \$\endgroup\$ – r.e.s. Jun 25 '12 at 12:33
  • \$\begingroup\$ Oh... ideone seems to run a 32-bit version, so it gets to an overflow of Int quickly. On a 64-bit system, that consumes too much memory to reproduce, but of course it still won't allow to reach G. I need the (big-int) Integer type, so I can't use !!; wait... \$\endgroup\$ – ceased to turn counterclockwis Jun 25 '12 at 12:44
  • \$\begingroup\$ Fixed it now, had to use explicit recursion to implement %. \$\endgroup\$ – ceased to turn counterclockwis Jun 25 '12 at 12:51
  • \$\begingroup\$ I find ((%3)%(3*))2 n actually grows faster than you say (a good thing), but my Haskell-fu is inadequate to understand why. For n = 0, 1, 2, ..., instead of giving 3, 3^3, 3^(3^3), ..., it gives 3, 3^(3+1), 3^((3^(3+1))+1), .... \$\endgroup\$ – r.e.s. Jun 29 '12 at 14:15
  • \$\begingroup\$ As I said: "((%3)%(3*))n 3 is larger than 3 ↑ⁿ 3". Or do you mean something else? Anyway, I changed the definition so that it's all equalities (at least I think so, to lazy to check now...) rather than larger-thans. And if you change 66 to 65, it actually produces G itself, ain't that nice? \$\endgroup\$ – ceased to turn counterclockwis Jun 29 '12 at 21:43
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Python (111+n), n=length(x)

Although this one is not as short as the answerer's Ruby program, I'll post it anyway, to rule this possibility out.

It uses the Ackermann function, and calls the Ackermann function with m and n being the values from another call to the Ackermann function, and recurses 1000 times.

This is probably bigger than Graham's number, but I'm not sure, because nobody knows the exact length of it. It can be easily extended, if it's not bigger.

x=999
b='A('*x+'5,5'+')'*x
def A(m,n):n+1 if m==0 else A(m-1,A(m,n-1)if n>0 else 1)
exec('print A('%s,%s')'%(b,b))
\$\endgroup\$
  • \$\begingroup\$ output to stdout? also, you need a return statement or a lambda. \$\endgroup\$ – boothby Jun 22 '12 at 5:43
  • 7
    \$\begingroup\$ Also if A(m,n) returns a single value, then isn't A(A(5,5)) missing an argument? ... This is the problem with a challenge like this: it encourages people not to test their code, because a complete run is purely theoretical. \$\endgroup\$ – breadbox Jun 22 '12 at 6:19
  • \$\begingroup\$ If you replace your last line with exec'x=A(x,x);'*x;print x, then the program is ok and the output is approximately f_(ω+1)(x) (assumimg the Ackermann function code is correct), which has more than G bytes even for x=99, say. (In my Ruby program, f[m,n] is a version of A(m,n).) \$\endgroup\$ – r.e.s. Jun 22 '12 at 12:18
  • \$\begingroup\$ @breadbox - Good point ... Theoretical questions like this require us to make sure a program is ok for small-parameter (i.e. non-theoretical) test-cases that clearly generalize to give a correct answer. \$\endgroup\$ – r.e.s. Jun 22 '12 at 12:46
  • 1
    \$\begingroup\$ Its's longer, but if you want to use eval instead of exec, your last line could be f=lambda x:A(x,x);print eval('f('*x+'x'+')'*x). Also, your def of A(m,n) needs to be corrected per boothby's comment. \$\endgroup\$ – r.e.s. Jun 22 '12 at 13:51
2
\$\begingroup\$

Ruby, 54 52 50 bytes

f=->b{a*=a;eval"f[b-1];"*b*a};eval"f[a];"*a=99;p a

Ruby, 85 81 76 71 68 64 63 59 57 bytes

f=->a,b=-a{eval"a*=b<0?f[a,a]:b<1?a:f[a,b-1];"*a};p f[99]

Pretty much fast growing hierarchy with f(a+1) > fω+1(a).


Ruby, 61 bytes

f=->a,b=-a{a<0?9:b==0?a*a:f[f[a-1,b],b>0?b-1:f[a,b+1]]};f[99]

Basically an Ackermann function with a twist.


Ruby, 63 59 bytes

n=99;(H=->a{b,*c=a;n.times{b ?H[[b-1]*n*b+c]:n+=n}})[n];p n

Another Ruby, 74 71 bytes

def f(a,b=a)a<0?b:b<0?f(a-1):f(a-1,f(a,b-1))end;n=99;n.times{n=f n};p n

Basically Ackermann function to itself 99 times.

\$\endgroup\$
0
\$\begingroup\$

Python: 85

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*99
exec'f('*64+'3'+',3)'*64

Which maybe could be shortened to 74 + length(X):

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*int('9'*X)
f(3,3)

Where X is an appropriate big number such that the resultant hyperoperation on 3, 3 is bigger than Grahams number(if this number is less than 99999999999 then some byte is saved).


Note: I assume the python code is executed on the interactive interpreter hence the result is printed to stdout, otherwise add 9 bytes to each solution for the call to print.

\$\endgroup\$
  • 2
    \$\begingroup\$ Your 74ish byte solution does not produce an output nearly large enough. \$\endgroup\$ – lirtosiast Dec 5 '15 at 2:08
0
\$\begingroup\$

Javascript, 83 bytes

Another Ackermann function solution.

(function a(m,n,x){return x?a(a(m,n,x-1),n,0):(m?a(m-1,n?a(m,n-1):1):n+1)})(9,9,99)
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 68 bytes, however uncompeting for using ES6

a=(x,y)=>y?x?a(a(x-1,y)*9,y-1):a(9,y-1):x;b=x=>x?a(9,b(x-1)):9;b(99)

a function is similar to up-arrow notation with base 9.

       /a(a(x-1,y)*9,y-1)  x>0, y>0
a(x,y)=|a(9,y-1)           x=0, y>0
       \x                  y=0

b function is: b(x)=bx(9).

b(99) is ~fω+1(99), compared to Graham's number<fω+1(64).

\$\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.