44
\$\begingroup\$

Graham's number G is defined in this way:

u(3,n,1) = 3^n
u(3,1,m) = 3
u(3,n,m) = u(3,u(3,n-1,m),m-1)
[Knuth's up-arrow notation]
[Conway chained arrow notation]

THEN

g1 = u(3,3,4)
g2 = u(3,3,g1)
g3 = u(3,3,g2)
...
G = u(3,3,g63)

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\$
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ – Leaky Nun Jun 27 '16 at 7:30
  • 7
    \$\begingroup\$ Is randomness allowed? If I just output random values, eventually Graham's number must be produced. \$\endgroup\$ – miles Jun 27 '16 at 7:33
  • 15
    \$\begingroup\$ @miles Why on earth isn't it already a standard loophole? Clarified. \$\endgroup\$ – Leaky Nun Jun 27 '16 at 7:35
  • 18
    \$\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\$ – Anders Kaseorg Jun 27 '16 at 10:09
  • 2
    \$\begingroup\$ Graham's number? \$\endgroup\$ – Beta Decay Aug 9 '16 at 10:47

19 Answers 19

48
+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\$
  • \$\begingroup\$ Where could one find an interpreter for this language? \$\endgroup\$ – Dennis Jun 28 '16 at 0:30
  • 4
    \$\begingroup\$ @Dennis tromp.github.io/cl/cl.html has a couple of them. \$\endgroup\$ – Anders Kaseorg Jun 28 '16 at 0:32
  • 1
    \$\begingroup\$ This is awesome. this deserves a sizeable bounty \$\endgroup\$ – cat Jun 28 '16 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 Jun 28 '16 at 19:05
  • 1
    \$\begingroup\$ @Dan I fixed the leader board snippet, I think. \$\endgroup\$ – Anders Kaseorg Jun 28 '16 at 19:43
40
\$\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\$
16
\$\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\$
  • \$\begingroup\$ Can you use another function which has precedence lower than + so as to remove the parentheses between m-1? \$\endgroup\$ – Leaky Nun Jun 27 '16 at 9:46
  • \$\begingroup\$ I count 44 bytes, and what happened to 4 and 64? \$\endgroup\$ – Leaky Nun Jun 27 '16 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 Jun 27 '16 at 9:53
  • \$\begingroup\$ I mean, I count 44 bytes after you change it back to 64. \$\endgroup\$ – Leaky Nun Jun 27 '16 at 9:54
  • \$\begingroup\$ I think you mean (`g`3), not (3`g`). \$\endgroup\$ – Anders Kaseorg Jun 27 '16 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\$
  • \$\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\$ – Anders Kaseorg Jun 29 '16 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\$ – Anders Kaseorg Jun 29 '16 at 9:43
  • \$\begingroup\$ An alternate way to save that second byte is *G]3ShG. \$\endgroup\$ – Anders Kaseorg Jun 29 '16 at 9:54
8
+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\$
  • \$\begingroup\$ You can replace [-] with , since EOF is 0. \$\endgroup\$ – mbomb007 Jul 22 '16 at 13:37
6
\$\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\$
  • \$\begingroup\$ @AndersKaseorg Ugh, in that case I might as well revert that change. \$\endgroup\$ – Neil Jun 29 '16 at 8:29
  • \$\begingroup\$ This causes a stack overflow, might need to recheck your reccursion pattern. \$\endgroup\$ – Frederic Charette Oct 19 '17 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 Jan 13 '18 at 18:58
5
\$\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\$
5
\$\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\$
  • \$\begingroup\$ (n f->3 (n f)) shouldn't it read n-1? \$\endgroup\$ – Leaky Nun Jun 27 '16 at 23:14
  • \$\begingroup\$ @LeakyNun No. (n f->3 (n f)) is a function for multiplication by three in Church numerals. \$\endgroup\$ – Anders Kaseorg Jun 27 '16 at 23:26
  • 2
    \$\begingroup\$ This challenge seems excessively simple in lambda calculus. Why? \$\endgroup\$ – cat Jun 28 '16 at 18:22
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\$
  • \$\begingroup\$ How did you manage to do it without having the number 64 anywhere in your code? \$\endgroup\$ – Leaky Nun Jun 28 '16 at 12:34
  • \$\begingroup\$ @LeakyNun I edited to clarify; better? \$\endgroup\$ – SQB Jun 28 '16 at 12:51
  • \$\begingroup\$ Well, then add it into your code as well as your byte-count. \$\endgroup\$ – Leaky Nun Jun 28 '16 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\$
  • 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 Jun 29 '16 at 15:10
  • \$\begingroup\$ @auhmaan oops sorry, I used that number for testing and forgot to change it back. Thanks!! \$\endgroup\$ – thepiercingarrow Jun 29 '16 at 19:46
  • \$\begingroup\$ Your return g(a-1) should be return u(3,g(a-1)). \$\endgroup\$ – Anders Kaseorg Jun 29 '16 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 Jul 16 '16 at 21:16
  • \$\begingroup\$ @algmyr wow amazing! you should go post your own answer XD. \$\endgroup\$ – thepiercingarrow Jul 18 '16 at 3:05
2
\$\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\$
  • 1
    \$\begingroup\$ Since when did Mathematica use ISO 8859-1? \$\endgroup\$ – Leaky Nun Jun 27 '16 at 23:17
  • \$\begingroup\$ n_ ±m_:=Nest[#±(m-1)&,3,n] \$\endgroup\$ – Leaky Nun Jun 27 '16 at 23:23
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\$
  • \$\begingroup\$ g(a){return u(3,a<2?4:g(a-1));} \$\endgroup\$ – Leaky Nun Jul 21 '16 at 13:13
  • \$\begingroup\$ @LeakyNun That's a really good one. Thanks. \$\endgroup\$ – algmyr Jul 21 '16 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\$
  • 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 Jun 29 '16 at 7:21
  • \$\begingroup\$ @Dennis Good catch. I'll fix that. \$\endgroup\$ – Mego Jun 29 '16 at 7:57
  • \$\begingroup\$ Actually the offset between u and v means it should be g(n-1)-1. \$\endgroup\$ – Anders Kaseorg Jun 29 '16 at 8:28
  • \$\begingroup\$ @AndersKaseorg I should not do programming while sleepy. I have to re-learn this every few days. \$\endgroup\$ – Mego Jun 29 '16 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\$ – Mego Jun 29 '16 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\$
  • \$\begingroup\$ You should be able to convert 1=⍺:3⋄1=⍵:3*⍺ to just 1=⍵:3*⍺ (3=3*1) \$\endgroup\$ – Zacharý Jul 31 '17 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\$
  • \$\begingroup\$ A good explanation on why and how this code works would be nice. \$\endgroup\$ – Manish Kundu Nov 16 '18 at 6:36
  • \$\begingroup\$ It is a straightforward application of the definition of Graham's number. \$\endgroup\$ – Simply Beautiful Art Nov 21 '18 at 18:27
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\$
  • \$\begingroup\$ Something like u=:3^[`[:(3$:])/[#<:@]@.*@] (not tested) \$\endgroup\$ – Leaky Nun Jun 28 '16 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\$
  • \$\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\$ – Anders Kaseorg Jul 22 '16 at 2:19
  • \$\begingroup\$ @AndersKaseorg edited that in. Thanks. My previous comment seems to have disappeared. \$\endgroup\$ – asibahi Jul 22 '16 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\$
  • \$\begingroup\$ @LeakyNun Thank you, updated the answer with acknowledgement. \$\endgroup\$ – Andreï Kostyrka Jul 22 '16 at 17:45
  • \$\begingroup\$ Just a sec... Today is my first day of code golfing, there is much to learn! \$\endgroup\$ – Andreï Kostyrka Jul 22 '16 at 17:47
  • \$\begingroup\$ You are invited to join our chat. \$\endgroup\$ – Leaky Nun Jul 22 '16 at 17:48
  • \$\begingroup\$ More golfing, please see the improvement. \$\endgroup\$ – Andreï Kostyrka Jul 22 '16 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\$ – Andreï Kostyrka Jul 22 '16 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\$
  • \$\begingroup\$ wish I knew Sesos or had the time to learn it and translate right now \$\endgroup\$ – Titus Jul 25 '16 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 Jul 25 '16 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 Jul 26 '16 at 3:31

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.