current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 1 down vote favorite
1

Graham's number G is defined in that way:

3^n = 3*..n times ...*3
3^^n = 3^(3^n)
3^^^n = 3^^(3^^n)
3^^^^n = 3^^^(3^^^n)
g1 = 3^^^^3
g2 = 3^^...g1 times^^3
g3 = 3^^...g2 times^^3
...
G = 3^^...g63 times^^3

Write down the shortest valid algorithm in the language of your choice, which uses a theoretically unbounded integers structure which computes Graham's number. Of course any algorithm will stack overflow, but suppose you have an infinite machine and infinite time.

The winner will have the lowest score based on the following:

(number of calls to functions + number of assignments) ^^ (size of the program)
share|improve this question
2  
Apparently the size of the program matters a lot. If you have one call to functions and one assignment, and the size of the program is 5, the score for the program is a 19729 digit number. –  Quincunx Feb 12 at 18:22
    
Well, it asked yesterday and no answers. So don't be afraid to post code which doesn't give an actual result because it is damn large number, somewhere I heard that in the Universe there is less amount of atoms then Grahams number, so not afraid to post not working code :) –  ST3 Feb 14 at 9:12
add comment

4 Answers

up vote 3 down vote

Haskell

arrow 0= \x y -> x^y
arrow n= \x y -> foldr1 (arrow (n-1)) (replicate y x)
gram= let f x=arrow x 3 3 in (iterate f 4) !! 65

The score would not fit in this answer window.

DANGER: You can load this into an interactive session to see if it type checks, but do NOT type gram. The laziness means that you check types and even test simple arrow calculations, but calculating gram is a no-no. It is a pure computation, so if you aren't careful, it will take control of your CPU. It almost took down my machine. BE CAREFUL

share|improve this answer
    
Sorry for augmenting your score from 314 to 324, PyRulez. But your code looks nicer than mine. –  Mikaël Mayer Feb 25 at 22:53
add comment
up vote 2 down vote

// C# solution with incrementation and recursion

    static void Main(string[] args) { int G = GrahamSeries(3, 64, 3); }
    static int Hyper(int a, int n, int b) { return n == 0 ? b + 1 : b == 0 ? (n == 1 ? a : n == 2 ? 0 : 1) : Hyper(a, n - 1, Hyper(a, n, b - 1)); }
    static int GrahamSeries(int a, int n, int b) { return Hyper(a, n == 1 ? 7 : GrahamSeries(a, n - 1, b), b);
share|improve this answer
add comment
up vote 0 down vote

Scala (224 201 193 bytes):

import scala.{BigInt=>I}
def pow(i:I,j:I):I=if(j==1)i else i*pow(i,j-1)
def a(n:I)(i:I,j:I):I=if(n==1)pow(i,j)else a(n-1)(i,a(n-1)(i,j))
def g(n:I):I= if(n==1)a(4)(3,3)else a(g(n-1))(3,3)
g(64)

Score:

Number of function calls: 8
Number of operator calls: 5 
number of definitions:    3

Score: 16^^193
share|improve this answer
add comment
up vote 0 down vote

J 3^^13

^&3^:4^:64]3x

Keep Jbreak ready when executing! Of course, what is a function call and what not? I will call the ^,^: function calls, the rest is basically glueing arguments (&) and separating them (]) which do not do anything ... functional. Let me know who opposes why.

  • 0 assignments
  • 3 function calls
  • length = 13

So final score is 3 ^^ 13

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.