45
\$\begingroup\$

Graham's number \$G\$ is defined in this way:

\begin{align*} u(3,n,1) & = 3^n \\ u(3,1,m) & = 3 \\ u(3,n,m) & = u(3,u(3,n-1,m),m-1) \end{align*}

Then,

\begin{align*} g_1 & = u(3,3,4) \\ g_2 & = u(3,3,g_1) \\ g_3 & = u(3,3,g_2) \\ & \vdots \\ G & = u(3,3,g_{63}) \end{align*}

You are given that \$u(3,3,2)=7625597484987\$ to check your code.

Your task is to write a program/function that will output the value of \$G\$ deterministically, given enough integer size and enough time.

References

Leaderboard

var QUESTION_ID=83873,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
26
  • 2
    \$\begingroup\$ Related. \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 7:30
  • 8
    \$\begingroup\$ Is randomness allowed? If I just output random values, eventually Graham's number must be produced. \$\endgroup\$
    – miles
    Commented Jun 27, 2016 at 7:33
  • 17
    \$\begingroup\$ @miles Why on earth isn't it already a standard loophole? Clarified. \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 7:35
  • 19
    \$\begingroup\$ Warning: u(3, 3, 2) = u(3, 2, 3) = 7625597484987, so you’ll also want to test on other values such as u(3, 5, 1) = 243 to make sure you got the argument order right. \$\endgroup\$ Commented Jun 27, 2016 at 10:09
  • 2
    \$\begingroup\$ Graham's number? \$\endgroup\$
    – Beta Decay
    Commented Aug 9, 2016 at 10:47

20 Answers 20

50
+250
\$\begingroup\$

Binary lambda calculus, 114 bits = 14.25 bytes

Hexdump:

00000000: 4457 42b0 2d88 1f9d 740e 5ed0 39ce 80    DWB.-...t.^.9..

Binary:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Explanation

01 00                                           (λx.
│    01 00                                        (λy.
│    │    01 01 01 110                              x
│    │    │  │  └─ 10                               y
│    │    │  └─ 00                                  (λm.
│    │    │       01 01 01 10                         m
│    │    │       │  │  └─ 00                         (λg.
│    │    │       │  │       00                         λn.
│    │    │       │  │         01 01 10                  n
│    │    │       │  │         │  └─ 110                 g
│    │    │       │  │         └─ 00                     (λz.
│    │    │       │  │              10                     z))
│    │    │       │  └─ 00                            (λn.
│    │    │       │       00                            λf.
│    │    │       │         01 111110                    x
│    │    │       │         └─ 01 110                    (n
│    │    │       │            └─ 10                      f))
│    │    │       └─ 1110                             x)
│    │    └─ 10                                     y)
│    └─ 00                                        (λf.
│         00                                        λz.
│           01 110                                   f
│           └─ 01 01 1110                            (x
│              │  └─ 110                              f
│              └─ 10                                  z)))
└─ 00                                           (λf.
     00                                           λz.
       01 110                                      f
       └─ 01 110                                   (f
          └─ 01 110                                 (f
             └─ 10                                   z)))

This is (λx. (λy. x ym. mg. λn. n g 1) (λn. λf. x (n f)) x) y) (λf. λz. f (x f z))) 3, where all numbers are represented as Church numerals. Church numerals are the standard lambda calculus representation of natural numbers, and they are well suited to this problem because a Church number is defined by function iteration: n g is the nth iterate of the function g.

For example, if g is the function λn. λf. 3 (n f) that multiplies 3 by a Church numeral, then λn. n g 1 is the function that takes 3 to the power of a Church numeral. Iterating this operation m times gives

mg. λn. n g 1) (λn. λf. 3 (n f)) n = u(3, n, m).

(We use multiplication u(–, –, 0) rather than exponentiation u(–, –, 1) as the base case, because subtracting 1 from a Church numeral is unpleasant.)

Substitute n = 3:

mg. λn. n g 1) (λn. λf. 3 (n f)) 3 = u(3, 3, m).

Iterating that operation 64 times, starting at m = 4, gives

64 (λm. mg. λn. n g 1) (λn. λf. 3 (n f)) 3) 4 = G.

To optimize this expression, substitute 64 = 4^3 = 3 4:

3 4 (λm. mg. λn. n g 1) (λn. λf. 3 (n f)) 3) 4 = G.

Remember 4 = succ 3 = λf. λz. f (3 f z) as a lambda argument:

y. 3 ym. mg. λn. n g 1) (λn. λf. 3 (n f)) 3) y) (λf. λz. f (3 f z)) = G.

Finally, remember 3 = λf. λz. f (f (f z)) as a lambda argument:

x. (λy. x ym. mg. λn. n g 1) (λn. λf. x (n f)) x) y) (λf. λz. f (x f z))) 3 = G.

\$\endgroup\$
6
  • \$\begingroup\$ Where could one find an interpreter for this language? \$\endgroup\$
    – Dennis
    Commented Jun 28, 2016 at 0:30
  • 4
    \$\begingroup\$ @Dennis tromp.github.io/cl/cl.html has a couple of them. \$\endgroup\$ Commented Jun 28, 2016 at 0:32
  • 1
    \$\begingroup\$ This is awesome. this deserves a sizeable bounty \$\endgroup\$
    – cat
    Commented Jun 28, 2016 at 18:19
  • 1
    \$\begingroup\$ 14.25 bytes seems to be messing up the leaderboard. It is parsed as 25 bytes, and you are therefore placed as second. \$\endgroup\$
    – Dan
    Commented Jun 28, 2016 at 19:05
  • 1
    \$\begingroup\$ @Dan I fixed the leader board snippet, I think. \$\endgroup\$ Commented Jun 28, 2016 at 19:43
41
\$\begingroup\$

Haskell, 41 bytes

i=((!!).).iterate
i(($3).i(`i`1)(*3))4 64

Explanation:

(`i`1)f n = i f 1 n computes the nth iterate of the function f starting at 1. In particular, (`i`1)(*3)n = 3^n, and iterating this construction m times gives i(`i`1)(*3)m n = u(3, n, m). We can rewrite that as (($n).i(`i`1)(*3))m = u(3, n, m), and iterate this construction k times to get i(($3).i(`i`1)(*3))4 k = g_k.

\$\endgroup\$
17
\$\begingroup\$

Haskell, 43 bytes

q=((!!).).iterate
g=q(`q`1)(3*)
q(`g`3)4$64

There has be a better way to flip g inline.

46 bytes:

i=iterate
n%0=3*n
n%m=i(%(m-1))1!!n
i(3%)4!!64

48 bytes:

n%1=3^n
1%m=3
n%m=(n-1)%m%(m-1)
iterate(3%)4!!64

Just writing down the definitions.

The base cases are a bit cleaner backed up to 0, though it saves no bytes. Perhaps it will make it easier to write an alternate definition.

n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1
\$\endgroup\$
6
  • \$\begingroup\$ Can you use another function which has precedence lower than + so as to remove the parentheses between m-1? \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 9:46
  • \$\begingroup\$ I count 44 bytes, and what happened to 4 and 64? \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 9:49
  • \$\begingroup\$ Oops, I copied in my smaller-parameter test. I don't think I can change the operator precedence because I'm defining a new function and those have a default precedence. I can't overwrite an existing function. \$\endgroup\$
    – xnor
    Commented Jun 27, 2016 at 9:53
  • \$\begingroup\$ I mean, I count 44 bytes after you change it back to 64. \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 9:54
  • \$\begingroup\$ I think you mean (`g`3), not (3`g`). \$\endgroup\$ Commented Jun 27, 2016 at 10:47
10
\$\begingroup\$

Pyth, 25 bytes

M?H.UgbtH*G]3^3Gug3tG64 4

The first part M?H.UgbtH*G]3^3G defines a method g(G,H) = u(3,G,H+1).

To test the first part, check that 7625597484987=u(3,3,2)=g(3,1): g3 1.

The second part ug3tG64 4 starts from r0 = 4 and then compute rn = u(3,3,r(n-1)) = g(3,r(n-1)) 64 times, outputting the final value (r is chosen instead of g to avoid confusion).

To test this part, start from r0=2 and then compute r1: ug3tG1 2.

\$\endgroup\$
3
  • \$\begingroup\$ If g(G, H) = u(3, G, H + 1), you should have r(n) = u(3, 3, r(n − 1)) = g(3, r(n − 1) − 1), not g(3, r(n − 1)). I think your code is right but your explanation is missing the − 1. \$\endgroup\$ Commented Jun 29, 2016 at 9:25
  • \$\begingroup\$ You can save a byte by using unoffsetted u arguments (^3*3, tGG), and another byte with .UgbtH*G]3e.ugNtHG1. \$\endgroup\$ Commented Jun 29, 2016 at 9:43
  • \$\begingroup\$ An alternate way to save that second byte is *G]3ShG. \$\endgroup\$ Commented Jun 29, 2016 at 9:54
7
\$\begingroup\$

JavaScript (ES7), 63 bytes

u=(n,m)=>n>1&m>1?u(u(n-1,m),m-1):3**n
g=n=>n?u(3,g(n-1)):4
g(64)
\$\endgroup\$
3
  • \$\begingroup\$ @AndersKaseorg Ugh, in that case I might as well revert that change. \$\endgroup\$
    – Neil
    Commented Jun 29, 2016 at 8:29
  • \$\begingroup\$ This causes a stack overflow, might need to recheck your reccursion pattern. \$\endgroup\$ Commented Oct 19, 2017 at 15:07
  • \$\begingroup\$ This isn't simple ES7. This is unbounded ES7 (an imaginary variant of ES7 but with bignum, able to oracle infinitely, and is using decimal with /#xE^ as shorthand). \$\endgroup\$
    – user75200
    Commented Jan 13, 2018 at 18:58
7
+200
\$\begingroup\$

Sesos, 30 bytes

0000000: 286997 2449f0 6f5d10 07f83a 06fffa f941bb ee1f33  (i.$I.o]...:....A...3
0000015: 065333 07dd3e 769c7b                              .S3..>v.{

Disassembled

set numout
add 4
rwd 2
add 64
jmp
    sub 1
    fwd 3
    add 3
    rwd 1
    add 1
    jmp
        sub 1
        jmp
            fwd 1
            jmp
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                rwd 1
                jmp
                    sub 1
                    fwd 3
                    add 1
                    rwd 3
                jnz
                fwd 3
                jmp
                    sub 1
                    rwd 2
                    add 1
                    rwd 1
                    add 1
                    fwd 3
                jnz
                rwd 1
                sub 1
            jnz
            rwd 1
            jmp
                sub 1
            jnz
            add 1
            rwd 1
            sub 1
        jnz
        fwd 1
        jmp
            sub 1
            rwd 1
            add 3
            fwd 1
        jnz
        rwd 2
    jnz
    rwd 1
jnz
fwd 2
put

Or in Brainfuck notation:

++++<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[->>>+++<+[-[>[[->+<]<[->>>+<<<]>>>[-<<+<+>>>]<-]<[-]+<-]>[-<+++>]<<]<]>>.

Testing

To compute u(3, n, u(3, n, … u(3, n, m) … )) with k nested calls to u, replace the first three add instructions add 4, add 64, add 3 with add m, add k, add n, respectively. Because Sesos can’t build numbers faster than in linear time, you’re practically limited to small values like u(3, 2, 2) = 27, u(3, 5, 1) = 243, and u(3, 1, u(3, 1, … u(3, 1, m) … )) = 3.

\$\endgroup\$
1
  • \$\begingroup\$ You can replace [-] with , since EOF is 0. \$\endgroup\$
    – mbomb007
    Commented Jul 22, 2016 at 13:37
6
\$\begingroup\$

Brachylog, 57 bytes

4:64:1iw
:3{[1:N],3:N^.|t1,3.|hM:1-X,?t:1-:Mr:2&:Xr:2&.}.

Expects no Input nor Output and writes the result to STDOUT. This will produce a stack overflow at one point.

To check that this works for small values (e.g u(3,3,2)) you can replace the 4 with the value of m and 64 with 1.

Explanation

This is basically a straightforward implementation of the explained way of computing the number.

  • Main predicate:

    4:64:1i                    Call Predicate 1 64 times with 4 as initial input (the second
                               call takes the output of the first as input, etc. 64 times).
           w                   Write the final output to STDOUT
    
  • Predicate 1:

    :3{...}.                   Call predicate 2 with input [Input, 3]. Its output is the 
                               output of predicate 1.
    
  • Predicate 2:

    [1:N],                     M = 1
          3:N^.                Output = 3^N
    |                          Or
    t1,                        N = 1
       3.                      Output = 3
    |                          Or
    hM:1-X,                    X is M - 1
           ?t:1-:Mr:2&         Unify an implicit variable with u(3,N-1,M)
                      :Xr:2&.  Unify Output with u(3,u(3,N-1,M),X)
    
\$\endgroup\$
6
\$\begingroup\$

Caramel, 38 bytes

(64 ((f->(f,1)),(n f->(3 (n f))),3) 4)

This is syntactic sugar for the lambda calculus expression 64 (λm. mf. λn. n f 1) (λn. λf. 3 (n f)) 3) 4, where all numbers are represented as Church numerals.

\$\endgroup\$
3
  • \$\begingroup\$ (n f->3 (n f)) shouldn't it read n-1? \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 23:14
  • \$\begingroup\$ @LeakyNun No. (n f->3 (n f)) is a function for multiplication by three in Church numerals. \$\endgroup\$ Commented Jun 27, 2016 at 23:26
  • 2
    \$\begingroup\$ This challenge seems excessively simple in lambda calculus. Why? \$\endgroup\$
    – cat
    Commented Jun 28, 2016 at 18:22
3
\$\begingroup\$

Mathematica, 59 bytes

n_ ±1:=3^n
1 ±m_:=3
n_ ±m_:=((n-1)±m)±(m-1)
Nest[3±#&,4,64]

Uses an undefined infix operator ± which requires only 1 byte when encoded in ISO 8859-1. See @Martin's post for more info. Mathematica functions support pattern matching for their arguments, such that the two base cases can be defined separately.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Since when did Mathematica use ISO 8859-1? \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 23:17
  • \$\begingroup\$ n_ ±m_:=Nest[#±(m-1)&,3,n] \$\endgroup\$
    – Leaky Nun
    Commented Jun 27, 2016 at 23:23
3
\$\begingroup\$

Prolog (SWIPL), 129 / 137 bytes

g(1,R):-u(3,4,R).
g(L,R):-M is L-1,g(M,P),u(3,P,R).
u(N,1,R):-R is 3**N.
u(1,_,3).
u(N,M,R):-K is N-1,L is M-1,u(K,M,Y),u(Y,L,R).

To output Graham's number, query for g(64,G). (if the 8 bytes of this query are to be counted, the length is 137 bytes):

?- g(64, G).
ERROR: Out of local stack

But as can be expected, this runs out of stack.

Test

?- u(3, 2, X).
X = 7625597484987

Backtracking causes it to run out of stack:

?- u(3, 2, X).
X = 7625597484987 ;
ERROR: Out of local stack

Ungolfed

The ungolfed version adds the general up-arrow notation, not just for 3, and uses cuts and checks to avoid backtracking and undefined situations.

% up-arrow notation
u(X, 1, _M, X) :- !.
u(X, N, 1, R) :-
    R is X**N, !.
u(X, N, M, R) :-
    N > 1,
    M > 1,
    N1 is N - 1,
    M1 is M - 1,
    u(X, N1, M, R1),
    u(X, R1, M1, R).

% graham's number
g(1,R) :- u(3, 3, 4, R), !.
g(L,R) :-
    L > 1,
    L1 is L - 1,
    g(L1,G1),
    u(3, G1, R).
\$\endgroup\$
3
  • \$\begingroup\$ How did you manage to do it without having the number 64 anywhere in your code? \$\endgroup\$
    – Leaky Nun
    Commented Jun 28, 2016 at 12:34
  • \$\begingroup\$ @LeakyNun I edited to clarify; better? \$\endgroup\$
    – SQB
    Commented Jun 28, 2016 at 12:51
  • \$\begingroup\$ Well, then add it into your code as well as your byte-count. \$\endgroup\$
    – Leaky Nun
    Commented Jun 28, 2016 at 12:52
3
\$\begingroup\$

C, 161 bytes

u(int a, int b){if(a==1)return 3;if(b==1)return pow(3,a);return u(u(a-1,b),b-1);}
g(int a){if(a==1)return u(3,4);return u(3,g(a-1));}
main(){printf("%d",g(64));}

EDIT: saved 11 bytes by removing tabs and newlines. EDIT: thx auhmann saved another byte and fixed my program

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You could remove g(int a){if(a==1)return u(3,4);return g(a-1);} since it's not being used at all... Or are you forgetting something? \$\endgroup\$
    – auhmaan
    Commented Jun 29, 2016 at 15:10
  • \$\begingroup\$ @auhmaan oops sorry, I used that number for testing and forgot to change it back. Thanks!! \$\endgroup\$ Commented Jun 29, 2016 at 19:46
  • \$\begingroup\$ Your return g(a-1) should be return u(3,g(a-1)). \$\endgroup\$ Commented Jun 29, 2016 at 23:40
  • 1
    \$\begingroup\$ I don't know if I should make a proper answer or just comment on this, but you can get this solution down to 114 bytes quite easily by realizing: Newlines between functions can be omitted. Omitting types for all argumens default them to int (think K&R). If statements like these can be written with nested ternary ops. Code: u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}g(a){return a<2?u(3,4):u(3,g(a-1));}main(){printf("%d",g(64));} \$\endgroup\$
    – algmyr
    Commented Jul 16, 2016 at 21:16
  • \$\begingroup\$ @algmyr wow amazing! you should go post your own answer XD. \$\endgroup\$ Commented Jul 18, 2016 at 3:05
2
\$\begingroup\$

C, 114 109 bytes

Based on the answer by @thepiercingarrow (link) I golfed the answer down quite a bit. Most savings are due to the abuse of default typing of arguments when doing K&R style functions and replacement of if statements with ternary operators. Added optional newlines between functions for readability.

Improved to 109 thanks to @LeakyNun.

u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}
g(a){return u(3,a<2?4:g(a-1));}
main(){printf("%d",g(64));}
\$\endgroup\$
2
  • \$\begingroup\$ g(a){return u(3,a<2?4:g(a-1));} \$\endgroup\$
    – Leaky Nun
    Commented Jul 21, 2016 at 13:13
  • \$\begingroup\$ @LeakyNun That's a really good one. Thanks. \$\endgroup\$
    – algmyr
    Commented Jul 21, 2016 at 13:17
1
\$\begingroup\$

Python, 85 bytes

v=lambda n,m:n*m and v(v(n-1,m)-1,m-1)or 3**-~n
g=lambda n=63:v(2,n and g(n-1)-1or 3)

The v function defines the same function as the one found in Dennis's answer: v(n,m) = u(3,n+1,m+1). The g function is a zero-indexed version of the traditional iteration: g(0) = v(2,3), g(n) = v(2,g(n-1)). Thus, g(63) is Graham's number. By setting the default value of the n parameter of the g function to 63, the required output can be obtained by calling g() (with no parameters), thus meeting our requirements for a function submission which takes no input.

Verify the v(2,1) = u(3,3,2) and v(4,0) = u(3,5,1) test cases online: Python 2, Python 3

\$\endgroup\$
6
  • 1
    \$\begingroup\$ It's kinda hard to verify, but your function g seems off. Shouldn't v(2,n-1) be g(n-1) or something similar? \$\endgroup\$
    – Dennis
    Commented Jun 29, 2016 at 7:21
  • \$\begingroup\$ @Dennis Good catch. I'll fix that. \$\endgroup\$
    – user45941
    Commented Jun 29, 2016 at 7:57
  • \$\begingroup\$ Actually the offset between u and v means it should be g(n-1)-1. \$\endgroup\$ Commented Jun 29, 2016 at 8:28
  • \$\begingroup\$ @AndersKaseorg I should not do programming while sleepy. I have to re-learn this every few days. \$\endgroup\$
    – user45941
    Commented Jun 29, 2016 at 8:29
  • \$\begingroup\$ @AndersKaseorg In the future, please do not edit other people's submissions, even if it is to fix a mistake in an improvement/bugfix that you suggested. \$\endgroup\$
    – user45941
    Commented Jun 29, 2016 at 8:40
1
\$\begingroup\$

Dyalog APL, 41 bytes

u←{1=⍺:3⋄1=⍵:3*⍺⋄(⍵∇⍨⍺-1)∇⍵-1}
3u 3u⍣64⊣4

Test case:

      3u 2
7625597484987
\$\endgroup\$
1
  • \$\begingroup\$ You should be able to convert 1=⍺:3⋄1=⍵:3*⍺ to just 1=⍵:3*⍺ (3=3*1) \$\endgroup\$
    – Adalynn
    Commented Jul 31, 2017 at 22:01
1
\$\begingroup\$

Ruby, 64 bytes

Borrowing from Theoretical algorithm to compute Graham's number.

def f(a,b=3)b<2?3:a<1?3*b:f(a-1,f(a,b-1))end;a=4;64.times{a=f a};p a

Simply put, f a = u(3,3,a) and it applies this 64 times.

\$\endgroup\$
2
  • \$\begingroup\$ A good explanation on why and how this code works would be nice. \$\endgroup\$ Commented Nov 16, 2018 at 6:36
  • \$\begingroup\$ It is a straightforward application of the definition of Graham's number. \$\endgroup\$ Commented Nov 21, 2018 at 18:27
1
\$\begingroup\$

Jelly, 22 bytes

’ß’ß’}ð‘3*ða?
4’2çƊ64¡

Try it online!

I believe this is close to identical to Dennis' deleted Jelly answer but was developed independently and uses a language feature that wasn't available at the time of his answer.

The first line defines a function \$v(n, m) = u(3, n+1, m+1)\$ and the TIO footer demonstrates this for \$u(3, 3, 2)\$, \$u(3, 5, 1)\$ and \$u(3, 1, 5)\$.

With our defined \$v\$, we then have the recurrence relation

\begin{align*} g_1 & = v(2, 3) \\ g_{i+1} & = v(2, g_i - 1) \\ G = g_{64} & = v(2, g_{63} - 1) \end{align*}

A more standard approach, which defines \$w(n, m) = u(3, n, m)\$ and then uses

\begin{align*} g_1 & = w(3, 4) \\ g_{i+1} & = w(3, g_i) \\ G = g_{64} & = w(3, g_{63}) \end{align*}

comes out at 23 bytes:

3*ð’ßṛß’}ð«Ị¥?
4 3ç$64¡

Try it online!

How they work

\$v(n, m)\$

’ß’ß’}ð‘3*ða? - Helper link, v(n, m). Takes n on left, m on right
            ? - If:
           a  -   n and m are both non-zero
      ð       - Then:
’             -   n-1
 ß            -   v(n-1, m)
  ’           -   v(n-1, m)-1
    ’}        -   m-1
   ß          -   v(v(n-1, m)-1, m)
          ð   - Else:
       ‘      -   n+1
        3*    -   3^(n+1)

4’2çƊ64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    Ɗ    - Last 3 links as a monad f(x):
 ’       -   x-1
  2ç     -   v(2, x-1)
     64¡ - Starting with x = 4, iterate f(x) 64 times

\$w(n, m)\$

3*ð’ßṛß’}ð«Ị¥? - Helper link, w(n, m). Takes n on left, m on right
            ¥? - If:
          «    -   min(n, m)
           Ị   -   is insignificant (abs(x) ≤ 1)
  ð            - Then:
3*             -   3^n
         ð     - Else:
   ’           -   n-1
     ṛ         -   m
    ß          -   w(n-1, m)
       ’}      -   m-1
      ß        -   w(w(n-1, m), m-1)

4 3ç$64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    $    - Last two links as a monad g(x):
  3ç     -  w(3, x)
     64¡ - Starting with x = 4, iterate g(x) 64 times
\$\endgroup\$
0
\$\begingroup\$

J, 107 bytes

u=:4 :0
if.y=1 do.3^x
elseif.x=1 do.3
elseif.1 do.x:(y u~<:x)u<:y
end.
)
(g=:(3 u 4[[)`(3 u$:@<:)@.(1&<))64

I'm working on converting u to an agenda, but for now it'll do.

\$\endgroup\$
1
  • \$\begingroup\$ Something like u=:3^[`[:(3$:])/[#<:@]@.*@] (not tested) \$\endgroup\$
    – Leaky Nun
    Commented Jun 28, 2016 at 22:18
0
\$\begingroup\$

F#, 111 108 bytes

Edit

This is using the function below to calulcate Graham's number

let rec u=function|b,1->int<|3I**b|1,c->3|b,c->u(u(b-1,c),c-1)
and g=function|1->u(3.,4.)|a->u(3.,g (a-1))
g 63

Here's my previous answer which, well, didnt:

Pretty straightforward. Just a definition of the u function.

let rec u=function|a,b,1->a**b|a,1.,c->a|a,b,c->u(a,u(a,b-1.,c),c-1)

Usage:

u(3.,3.,2)
val it : float = 7.625597485e+12

If I assumed 3 as the value for a, I could cut it to 60:

let rec u=function|b,1->3.**b|1.,c->3.|b,c->u(u(b-1.,c),c-1)

Usage:

u(3.,2)
val it : float = 7.625597485e+12
\$\endgroup\$
2
  • \$\begingroup\$ The challenge is to write Graham’s number, not u. You can of course include any intermediate functions you need, such as u with or without its first argument fixed at 3. \$\endgroup\$ Commented Jul 22, 2016 at 2:19
  • \$\begingroup\$ @AndersKaseorg edited that in. Thanks. My previous comment seems to have disappeared. \$\endgroup\$
    – asibahi
    Commented Jul 22, 2016 at 4:08
0
\$\begingroup\$

R, 154 142 128 126 118 bytes

u=function(n,b)return(if(n&!b)1 else if(n)u(n-1,u(n,b-1))else 3*b)
g=function(x)return(u(if(x-1)g(x-1)else 4,3))
g(64)

I used the Wikipedia definition of this recursive function because for some odd reason the suggested one did not work... or I just suck at R golfing.

UPD: shaved off 12+14=26 bytes thanks to a tip from Leaky Nun. The prior version used the bulky and less efficient

u=function(n,b)if(n==0)return(3*b)else if(n>0&b==0)return(1)else return(u(n-1,u(n,b-1)))
g=function(x)if(x==1)return(u(4,3))else return(u(g(x-1),3))

UPD: shaved off 2+6+2 more bytes (again, kudos to Leaky Nun) owing to an ingenious replacement with “if(x)” instead of “if(x==0)” because x<0 is never fed into the function... right?

\$\endgroup\$
11
  • \$\begingroup\$ @LeakyNun Thank you, updated the answer with acknowledgement. \$\endgroup\$ Commented Jul 22, 2016 at 17:45
  • \$\begingroup\$ Just a sec... Today is my first day of code golfing, there is much to learn! \$\endgroup\$ Commented Jul 22, 2016 at 17:47
  • \$\begingroup\$ You are invited to join our chat. \$\endgroup\$
    – Leaky Nun
    Commented Jul 22, 2016 at 17:48
  • \$\begingroup\$ More golfing, please see the improvement. \$\endgroup\$ Commented Jul 22, 2016 at 17:52
  • \$\begingroup\$ Ta-dam, done, changed the function u in the same key as your g and saved 6 more bytes—awesome! \$\endgroup\$ Commented Jul 22, 2016 at 18:42
0
\$\begingroup\$

PHP, 114 bytes

ignore the line breaks; they are for readability only.

function u($n,$m){return$m>1&$n>1?u(u($n-1,$m),$m-1):3**$n;}
function g($x){return u(3,$x>1?g($x-1):4);}
echo g(63);

It is possible to integrate the second case into the first one: for n=1, 3^n equals 3.
This will save a few bytes on - as far as I can see - all existing answers; saved two bytes on my

previous version, 62+43+11=116 bytes

function u($n,$m){return$m>1?$n>1?u(u($n-1,$m),$m-1):3:3**$n;}

PHP´s left associativity of the ternary requires parentheses ... or a specific order of tests.
This saved two bytes on the parenthesized expression.


There is probably an iterative approach, which may allow further golfing ...
but I can´t take the time for it now.

\$\endgroup\$
3
  • \$\begingroup\$ wish I knew Sesos or had the time to learn it and translate right now \$\endgroup\$
    – Titus
    Commented Jul 25, 2016 at 12:11
  • \$\begingroup\$ @Leaky Nun: I broke it down to only loops and addition. Is there a way in Sesos to add the value of one cell to another? \$\endgroup\$
    – Titus
    Commented Jul 25, 2016 at 13:04
  • \$\begingroup\$ @AndersKaseorg: You´re probably right ... I got blisters on my eyeballs from looking at that algorithm. Will look at it again soon. \$\endgroup\$
    – Titus
    Commented Jul 26, 2016 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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