# Golf a number bigger than Loader's number

As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge.

Loader's number is a very large number, that is kind of hard to explain (since it was itself the result of a code golfing exercise with a flexible goal). There is a definition and explanation here, but for the purposes of self-containment, I will attempt to explain it later in this post as well.

The algorithm Ralph Loader used produces one of the largest numbers of any (computable) algorithm ever written! Indeed, Loader's number is the largest "computable" number on the Googology Wiki. (By "computable" number, they mean a number defined in terms of a computation.) That means that if answer produces a number larger than Loader's number in an interesting way (i.e. not just Loader's number+1), you could go down in Googology history! That being said, programs that produce something like Loader's number+1 are definitely valid answers and contenders to this question; just don't expect any fame.

Your job is to create a terminating program that produces a number larger than Loader's number. This is , so the shortest program wins!

• You aren't allowed to take input.
• Your program must eventually terminate deterministically but you can assume the machine has infinite memory.
• You may assume your language's number type can hold any finite value but need to explain how this exactly works in your language (ex: does a float have infinite precision?)
• Infinities are not allowed as output.
• Underflow of a number type throws an exception. It does not wrap around.
• You need to provide an explanation of why your number is so big and an ungolfed version of your code to check if your solution is valid (since there is no computer with enough memory to store Loader's number).

So here is an explanation of Loader's number. See http://googology.wikia.com/wiki/Loader%27s_number and the links therein for more precise details. In particular, it contains a program that produces Loader's number exactly (by definition).

The calculus of constructions is essentially a programming language with very particular properties.

First of all, every syntactically valid program terminates. There are no infinite loops. This will be very useful, because it means that if we run an arbitrary calculus of constructions program, our program will not get stuck. The problem is that this implies the calculus of constructions is not Turing complete.

Second of all, among non-Turing complete languages, it is one of the most powerful. Essentially, if you can prove that a Turing machine will halt on every input, you can program a function in the calculus of constructions that will simulate it. (This does not make it turing complete, because there are halting turing machines that you can not prove are halting.)

Loader's number is essentially a busy beaver number for the calculus of constructions, which is possible to compute since all coc programs terminate.

In particular, loader.c defines a function called D. Approximately, D(x) iterates over all bit-strings less than x, interprets them as a coc programs, runs the syntactically valid ones, and concatenates the results (which will also be bitstrings). It returns this concatenation.

Loader's number is D(D(D(D(D(99))))).

A more readable copy of the code from the googolology wiki

int r, a;

P(y,x){return y- ~y<<x;}

Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}

L(x){return x/2 >> Z(x);}

S(v,y,c,t){
int f = L(t);
int x = r;
return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}

A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}

D(x)
{
int f;
int d;
int c=0;
int t=7;
int u=14;
while(x&&D(x-1),(x/=2)%2&&(1)){
d = L(L(D(x))),
f = L(r),
x = L(r),
c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
}
return a = P( P( t, P( u, P( x, c)) ),a);
}

main(){return D(D(D(D(D(99)))));}

• I would advise against downvoting this for similarity to the TREE(3) question: Loader's number is so much larger than TREE(3) that new and interesting approaches are required. – lirtosiast Dec 4 '18 at 1:00
• @fəˈnɛtɪk Well, printing Loader's number + 1 is still interesting from a code golf perspective (for example, can you beat the original 512 bytes?) There are also some natural generalizations of loader's number that might be easier to implement (for example, using ZFC instead of CoC). Also, Greedy clique sequences or finite promise games could be used. – PyRulez Dec 4 '18 at 3:24
• Unfortunately, as I don't understand the construction of Loader's number and there does not seem to be known upper bounds in terms of the fast growing hierarchy, I cannot give any good answers here. I believe that most answers will be either extensions of Loader's number or things such as the greedy clique sequences and finite promise games... – Simply Beautiful Art Dec 4 '18 at 12:33
• @SimplyBeautifulArt Oh boy, if you don't understand it, that doesn't bode well for this challenge. :P I could try explaining it in more detail to you in chat, but I also do not know any hierarchy upper bounds. – PyRulez Dec 4 '18 at 16:36
• @SimplyBeautifulArt In particular, since Loader's constant was specifically chosen to try to be the biggest number generated by a certain amount of code (where as Graham's number and TREE(3) at just mathematically interesting numbers that just so happen to be large), I think most answers will just be Loader's number + 1. – PyRulez Dec 4 '18 at 16:38

# JavaScript, D^6(9) (508501495492487485 481 bytes)

_='r=a=0,PN,yEx-~x<<y,ZNEr=x%2?0:1+ZC>>1@LNEx/2>>ZC@S=Bt,f=Ht@x=rEf-2?f>2?f-v?t-(f>v)*c:y:Ff,FSO(v+2,t8y@c,ZCMM:A(AOBZC)GAN,yELC)-1?5<<PC,y):Iy,4,Z(rGDN,f,dQ=0,t=7,u=14Eeval("whileC&&DC-1@61Md=HHDC)Gf=Hr@x=Hr@c-r||(Hu)||Hr)-f||6u=Id,4,r@t=A(t,dGfJdQ@t8t@u8u)Gc&&6t=F~u&2|6u=1<<FHc@uGFHc@tGc=r@uJtQ@u8t@t=9);a=FFt,Fu,PCQ)Ga)"@KKK9MMM6C>>=1)%2&&(8=I13,-4,G)@@),B(v,yQ,N=COBLCGSC(xE)=>J/2&6c=FFP(HL(IS(4,KD(D(M))Q,c';for(Y of $='QMKIHFJECONB@G86')with(_.split(Y))_=join(pop());eval(_)  This is an encoded code. _='r=a=0,PN,yEx-~x<<y,ZNEr=x%2?0:1+ZC>>1@LNEx/2>>ZC@S=Bt,f=Ht@x=rEf-2?f>2?f-v?t-(f>v)*c:y:Ff,FSO(v+2,t8y@c,ZCMM:A(AOBZC)GAN,yELC)-1?5<<PC,y):Iy,4,Z(rGDN,f,dQ=0,t=7,u=14Eeval("whileC&&DC-1@61Md=HHDC)Gf=Hr@x=Hr@c-r||(Hu)||Hr)-f||6u=Id,4,r@t=A(t,dGfJdQ@t8t@u8u)Gc&&6t=F~u&2|6u=1<<FHc@uGFHc@tGc=r@uJtQ@u8t@t=9);a=FFt,Fu,PCQ)Ga)"@KKK9MMM6C>>=1)%2&&(8=I13,-4,G)@@),B(v,yQ,N=COBLCGSC(xE)=>J/2&6c=FFP(HL(IS(4,KD(D(M))Q,c'; //encoded code for(Y of$='QMKIHFJECONB@G86')with(_.split(Y))_=join(pop()); //decoding algorithm
eval(_) //Evaluation of the string


Decoded code:

r=a=0,P=(x,y)=>x-~x<<y,Z=(x)=>r=x%2?0:1+Z(x>>1),L=(x)=>x/2>>Z(x),S=(v,y,c,t,f=L(t),x=r)=>f-2?f>2?f-v?t-(f>v)*c:y:P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x)))):A(A(v,y,c,L(x)),S(v,y,c,Z(x))),A=(x,y)=>L(x)-1?5<<P(x,y):S(4,y,4,Z(r)),D=(x,f,d,c=0,t=7,u=14)=>eval("while(x&&D(x-1),(x>>=1)%2&&(1))d=L(L(D(x))),f=L(r),x=L(r),c-r||(L(u)||L(r)-f||(x>>=1)%2&&(u=S(4,d,4,r),t=A(t,d)),f/2&(x>>=1)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),c&&(x>>=1)%2&&(t=P(~u&2|(x>>=1)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r),u/2&(x>>=1)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);a=P(P(t,P(u,P(x,c))),a)"),D(D(D(D(D(D(9))))))


Decoded, ungolfed code(conditions and stuff are kept from loader.c):

var r=a=0;
function P(y,x){
return y-~y<<x;
}
function Z(x){
return r=x%2?0:1+Z(x>>1);
}
function L(x){
return x/2>>Z(x);
}
function S(v,y,c,t){
var f=L(t),x=r;
return f-2?
f>2?
f-v?
t-(f>v)*c
:y
:P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x))))
:A(S(v,y,c,L(x)),S(v,y,c,Z(x)))
}
function A(y,x){
return L(y)-1?
5<<P(y,x):
S(4,x,4,Z(r));
}
function D(x){
var f,
d,
c=0,
t=7,
u=14;
while(x&&D(x-1),(x>>=1)%2&&(1))
d=L(L(D(x))),
f=L(r),
x=L(r),
c-r||(
L(u)||L(r)-f||
(x>>=1)%2&&(
u=S(4,d,4,r),t=A(t,d)
),
f/2&(x>>=1)%2&&(
c=P(d,c),
t=S(4,13,-4,t),
u=S(4,13,-4,u)
)
),
c&&(x>>=1)%2&&(
t=P(
~u&2|(x>>=1)%2&&(
u=1<<P(L(c),u)
),
P(L(c),t)
),
c=r
),
u/2&(x>>=1)%2&&(
c=P(t,c),
u=S(4,13,-4,t),
t=9
);
return a=P(P(t,P(u,P(x,c))),a)
};
D(D(D(D(D(D(9))))))


In this, it is assumed to be:

• Infinite call stack
• Infinite memory
• Infinite precision Number
• Infinite magnitude Number
• Bitshift and bitwise operators works on infinite bit integers instead of 53 bits. Bitwise negation still negates the sign bit.

## Encoding/Decoding algorithm:

The encoding is done as follows:

• Take a repeated string, call it S.
• Replace all S in the code to a key K.
• Put K and S at the end.
• Make a list of keys, and also put decoding algorithm so the code actually runs.

The decoding algorithm:

• Take list of keys.
• Take the earliest key K.
• Split the string for each K.
• Since last of the array is what to replace K S, pop it, and replace all K by joining the array with the popped value S.

The compression was done with this code, check only the last box. Since this will encode the largest save first, it is not the most efficient compression, but I don't know how to make it smaller either so meh.

## JavaScript, (339 chars)

eval("_㴧爽愽〬偍ⱹ䕸⵾砼㱹ⱚ䵅爽砥㈿〺ㄫ婃㸾ㅀ䱍䕸⼲㸾婃䁓㵂琬昽䡴䁸㵲䕦ⴲ㽦㸲㽦⵶㽴⴨显瘩⩣㩹㩆昬䙓丨瘫㈬琸祀挬婃䭋㩁⡁乂婃⥇䅍ⱹ䕌䌩ⴱ㼵㰼偃ⱹ⤺匨㐬礬㐬娨片䑍ⱦⱤⱣ㴰ⱴ㴷Ⱶ㴱㑅敶慬⠢睨楬敃☦䑃ⴱ䀶ㅋ搽䡈䑃⥇昽䡲䁸㵈牀挭牼簨䡵⥼籈爩ⵦ籼㙵㵓⠴ⱤⰴⱲ䁴㵁⡴Ɽ䝦䥤Ᵽ䁴㡴䁵㡵⥇挦☶琽䙾甦㉼㙵㴱㰼䙈捀畇䙈捀瑇挽牀畉琬捀甸瑀琽㤩㭡㵆䙴ⱆ甬偃Ᵽ⥇愩≀䩊䨹䭋䬶䌾㸽ㄩ┲☦⠸㵓⠴ⰱ㌬ⴴⱇ⥀䀩ⱂ⡶ⱹⱣⱍ㵃乂䱃䝓䌨硅⤽㹉⼲☶挽䙆倨䡌⡊䐨䐨䬩⤧㭦潲⡙⁯映␽❋䩈䙉䕃乍䉀䜸㘧⥷楴栨弮獰汩琨天⥟㵪潩渨灯瀨⤩㭥癡氨弩".split.map(a=>(d=String.fromCharCode)((c=a.charCodeAt())>>8)+d(c&255)).join.slice(1))


This code will take the 16bit string as a, converts it to 8bit string with same binary(BE), and eval it.

The decoded code is the encoded code above.

## Proof that D^6(9)>D^5(99)

For this, we would compare D(9) and 99.

By manually running the code, D(9) is found equal to (15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), and even D(0) is equal to 8646911284551352321.

So, D(9)>>>99, and because D is strictly increasing, D^6(9)>D^5(99).

• 508B->501B, -7B
• -1B for... I don't know why. I did change D(D(D(D(D(99))))) to D(D(D(D(D(D(9)))))). Also that shuffled the letters.
• -6B for re-adding &&(1) for D(x)'s loop condition.
• 501B->495B, -6B
• Fixed most /2s to >>1s because Number
• 6 byte save from somewhere
• You can see my attempt in this update here
• 495->492B, -3B
• By changing the decoder from for...in to for...of.
• 492->487B, -5B
• Removing unnecessary assignments
• Changing argument names
• 487->485B, -2B
• 1 byte from using eval for D, removing return.
• 1 byte compression combining the closing parentheses to a comma.
• 485->481B, -4B
• By compressing different substrings.
• Or easily pass it with equal length by replaceing 99 with M9, which makes the value D^6(9). – Naruyoko Apr 26 '19 at 13:53

# Python 3, D^6(9) (608600 599 bytes)

_='r=a=0?CM:#y-~y<<x?H6@r=0.EB1+HI)#r?Fx):#xI>>H)?8t6@TtNr#A(U8HG).f==2BCf,CUS(v+2,/yNc,HGG.f<2Bt-(f>v)*c.f-vBy?A(M:#5<<CM.Fy)-1BOx,4,Z(rG?Jx6,a@f=d=c=0@VW7,14@while 1:@.x:Jx-1)X~E:breakKd,TFJxGNFrNFr)@.c-r:K.not(Fu)or(Fr)-fGQ.E:WOd,4,rRA(Vd)K.fIQ.Yd,cR/t);W/u)@.c:@!.EQ q=~u&2|EK .q:W1<<CFuNu)K  Vc=Cq and u,CFcNtG,rXuI&YVc);W/tR9@a=CCVCu,Cx,cGNa)#a\nprint(JJJJJJ9GGG)X\n!if !  x=xIK#@return . if /O13,-4,6):@global r8S(v,y,c,?\ndef Q:K! K@ @\n B else CP(YE:c=CEx%2Tf,x=FFL(U8FxG,G))HZ(xI>>1JD(My,x)N),OS(4,R);t=Vt,Wu='
for Y in 'WVRONMJIHGUFTEYCB@KQ?86/.#!X':_=_.split(Y);_=_.pop().join(_)
exec(_)


This is an encoded code. Extracted:

r=a=0
def P(y,x):
return y-~y<<x
def Z(x):
global r
r=0 if x%2 else 1+Z(x>>1)
return r
def L(x):
return x>>1>>Z(x)
def S(v,y,c,t):
global r
f,x=L(t),r
return A(S(v,y,c,L(x)),S(v,y,c,Z(x))) if f==2 else P(f,P(S(v,y,c,L(x)),S(v+2,S(4,13,-4,y),c,Z(x)))) if f<2 else t-(f>v)*c if f-v else y
def A(y,x):
return 5<<P(y,x) if L(y)-1 else S(4,x,4,Z(r))
def D(x):
global r,a
f=d=c=0
t,u=7,14
while 1:
if x:D(x-1)
x=x>>1
if ~x%2:break
d,f,x=L(L(D(x))),L(r),L(r)
if c-r:
if not(L(u)or(L(r)-f)):
x=x>>1
if x%2:u=S(4,d,4,r);t=A(t,d)
if f>>1:
x=x>>1
if x%2:c=P(d,c);t=S(4,13,-4,t);u=S(4,13,-4,u)
if c:
x=x>>1
if x%2:
x=x>>1
q=~u&2|x%2
if q:u=1<<P(L(u),u)
t,c=P(q and u,P(L(c),t)),r
x=x>>1
if u>>1&x%2:c=P(t,c);u=S(4,13,-4,t);t=9
a=P(P(t,P(u,P(x,c))),a)
return a
print(D(D(D(D(D(D(9)))))))


In this, it is assumed to be:

• Infinite call stack
• Infinite memory

This is basically a port of my JavaScript answer. For more details, check that one.

The compression was done with this.

I am not very knowledgeable in Python, so there are certainly places to save bytes. I think sub-600 is possible. sub-600 has been proven.

• 608->600B, -8B
• Grouped some assignments
• Reversed conditions of S to reduce parenthesis
• 600->599B, -1B
• Changing u/2 in the third last line of the definition of D to u>>1, saving a byte from compressing it to a character with other >>1s.

# Ruby, D^6(9) (553 bytes)

_='F=$a=0TEK#y-~yUx.Z@#F=x%2G1?0R1+Z(x/2).L@#x/2>>Z@.8t)VHt);x=F#fG2?A(8L@C8Z@IRf>2?fGv ?yRt-(f>v ?1R0)*cREf,E8L@CS(v+2,t6yCc,Z@I).A(K#Hy)G1?Mx,4,Z(FIR5UEK.D@;$>UxVd=c=0;t=7;u=14;while[xNOx-1CB>0];d=HHD@IVW;x=W;cGF&&[Hu)G0&&WGf&&![u=Md,4,FCt=A(t,d)],fJd,cCt6tCu6u)]];cNB&&[t=E~u&2|!(u=1UEHcCu)CEHcCt)Cc=F];uJt,cCu6tCt=9]Q#$a=EEt,Eu,Ex,cIC$a)Q;$>UOOOOOO9III!BN#;return .QT6=M13,-4,8S(v,y,c,@(x)B(x/=2)%2C),J/2&![c=EEP(F$rNG0||G==WHF)HL(I))Ky,x)MS(4,OD(Q;endR: T;def U<<V;f=VUTRQOMKIHWGNFEJCB@86.#!'.each_char{|Y|_=_.split(Y);_=_.join(_.pop())};eval(_)


This is an encoded code. Extracted:

$r=$a=0;def P(y,x);return y-~y<<x;end;def Z(x);return $r=x%2==1?0: 1+Z(x/2);end;def L(x);return x/2>>Z(x);end;def S(v,y,c,t);f=L(t);x=$r;return f==2?A(S(v,y,c,L(x)),S(v,y,c,Z(x))): f>2?f==v ?y: t-(f>v ?1: 0)*c: P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x))));end;def A(y,x);return L(y)==1?S(4,x,4,Z($r)): 5<<P(y,x);end;def D(x);$><<x;f=d=c=0;t=7;u=14;while[x==0||D(x-1),(x/=2)%2>0];d=L(L(D(x)));f=L($r);x=L($r);c==$r&&[L(u)==0&&L($r)==f&&(x/=2)%2==0||[u=S(4,d,4,$r),t=A(t,d)],f/2&(x/=2)%2==0||[c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u)]];c==0||(x/=2)%2&&[t=P(~u&2|(x/=2)%2==0||(u=1<<P(L(c),u)),P(L(c),t)),c=$r];u/2&(x/=2)%2==0||[c=P(t,c),u=S(4,13,-4,t),t=9];end;return $a=P(P(t,P(u,P(x,c))),$a);end;\$><<D(D(D(D(D(D(9))))))