The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti has at most i vertices, and no tree is a minor of any tree following it in the sequence.

TREE(1) = 1, with e.g. T1 = (1).

TREE(2) = 3: e.g. T1 = (1); T2 = (2)--(2); T3 = (2).

TREE(3) is a big big number. Even bigger than Graham's number. Your job is to output a number even bigger than it!

This is a so the goal is to write the shortest program in any language that deterministically outputs a number bigger than or equal to TREE(3) (to the stdout).

  • You aren't allowed to take input.
  • Your program must eventually terminate but you can assume the machine has infinite memory.
  • You might 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.
  • Because TREE(3) is such a complex number you can use the fast growing hierarchy approximation fϑ(Ωω ω)+1(3) as the number to beat.
  • 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 TREE(3))

Note: None of the answers currently found here work.

Why is TREE(3) so big?

  • 10
    \$\begingroup\$ @StepHen not trivally. Getting to Tree(3) requires a whole new paradigm. \$\endgroup\$ Commented Aug 16, 2017 at 18:58
  • 1
    \$\begingroup\$ relevant: codegolf.meta.stackexchange.com/questions/14057/… \$\endgroup\$
    – fejfo
    Commented Oct 14, 2017 at 6:08
  • 16
    \$\begingroup\$ TREE(3)+1 there I win \$\endgroup\$
    – hyper-neutrino
    Commented Oct 14, 2017 at 23:44
  • 1
    \$\begingroup\$ @KSmarts You do realize none of the answers there come close to TREE(3)? \$\endgroup\$ Commented Oct 19, 2017 at 23:53
  • 2
    \$\begingroup\$ @MDXF I'm gonna say no, because using INT_MAX is kinda a cheating (otherwise, print INT_MAX would insta win). In general, your output needs to be the same for any sufficiently large system. \$\endgroup\$ Commented Oct 26, 2017 at 7:30

11 Answers 11


New Ruby, 135 bytes, >> Hψ(φ3(Ω+1))(9)

where H is the Hardy hierarchy, ψ is an extended version of Madore's OCF (will explain below) and φ is the Veblen function.

Try it online!

f=->a,n,b=a{c,d,e=a;a==c ?a-1:e ?a==a-[0]?[[c,d,f[e,n,b]],d-1,c]:c:[n<1||c==0?n:[f[c||b,n-1]],n,n]};h=[],k=9,k;h=f[h,p(k*=k)]while h!=0

Ungolfed: (using functions, not lambdas)

def f(a,n,b)
  c,d,e = a
  if a == c
    return a-1
  elsif e
    if a == a-[0]
      return [[c,d,f(e,n,b)],d-1,c]
      return c
    x = c || b
    if n < 1 || c == 0
      return [n,n,n]
      return [f(x,n-1,x),n,n]

k = 9
h = [[],k,k]
while (h != 0) do
  k *= k
  p k
  h = f(h,k,h)

Madore's extended OCF:

enter image description here

And (crudely) Veblen's phi function:

enter image description here

Explanation without ordinals:

f(a,n,b) reduces an array recursively. (if no third argument given, it takes the first argument twice.)
f(k,n,b) = k-1, k is a positive int.
f([c,d,0],n,b) = f([c,0,e],n,b) = c
f([c,d,e],n,b) = [[c,d,f(e,n,b)],d-1,c], d ≠ -1 and c ≠ 0

f([a],0,b) = [0,0,0]
f([0],n,b) = [n,n,n]
f([],n,b) = f([b],n,b)
f([a],n,b) = [f[a,n-1,a],n,n]

My program initiates k = 9, h = [[],9,9]. It then applies k = k*k and h = f(h,k) until h == 0 and outputs k.

Explanation with ordinals:

Ordinals follow the following representation: n, [], [a], [a,b,c], where n,d is a natural number and a,c are all ordinals.
x = Ord(y) if y is the syntactic version of x.
a[n,b] = Ord(f(a,n))
ω = Ord([0]) = Ord(f([a],-1,b))
n = Ord(n)
Ω = Ord([])
ψ'(a) = Ord([a])
ψ'(a)[n] = Ord(f([a],n))
φ(b,c) ≈ Ord([[0],b,c])
a(↓b)c = Ord([a,b,c]) (down-arrows/backwards associative hyper operators I designed just for ordinals)

We follow the following FS for our ordinals:
k[n,b] = k-1, k < ω
ω[n,b] = n(↓n)n
(a(↓b)0)[n,b] = (a(↓0)c)[n,b] = a
(a(↓b)c)[n,b] = (a(↓b)(c[n,b]))(↓b[n,b])a, b ≥ 0 and c > 0.
ψ'(a)[0,b] = 0(↓0)0
ψ'(a)[n,b] = (ψ'(a[n-1,a]))(↓n)ω, a > 0 and n ≥ 0. (also note that we've changed from [n,b] to [n,a].)
Ω[n,b] = ψ'(b)[n,b]

ψ'(ω∙α) ≈ ψ(α), the ordinal collapsing function described in the image above.

My program more or less initiates k = 9 and h = Ω(↑9)9, then applies k ← k² and h ← h[k,h] until h = 1 and returns k.

And so if I did this right, [[],9,9] is way bigger than the Bachmann-Howard ordinal ψ(ΩΩΩ...), which is way bigger than ϑ(Ωωω)+1.

ψ(Ω(↓9)9) > ψ(Ω(↓4)3) > ψ(ΩΩΩ)+1 > ψ(ΩΩωω)+1 > ϑ(Ωωω)+1

And if my analysis is correct, then we should have ψ'(ΩΩ∙x) ~= ψ*(ΩΩ∙x), where ψ* is the normal Madore's psi function. If this holds, then my ordinal is approximately ψ*(φ3(Ω+ω)).

Old Ruby, 309 bytes, Hψ'09)(9) (see revision history, besides the new one is way better)

  • 1
    \$\begingroup\$ I could only test my program for very few values, so do excuse me if I've made a mistake somewhere. \$\endgroup\$ Commented Oct 20, 2017 at 20:19
  • 1
    \$\begingroup\$ Bleh, slowly but surely trying to think my way through and fixing anything I see wrong. :-( So tedious. \$\endgroup\$ Commented Oct 20, 2017 at 22:26
  • 1
    \$\begingroup\$ Hmm... so $f_{ψ_0(ψ9(9))}(9)$ means we need at least the $ψ_9(9)$ th weakly inaccessible cardinal level of the fast growing hierarchy with base 9 to get larger than $TREE(3)$ \$\endgroup\$
    – Secret
    Commented Oct 21, 2017 at 8:54
  • 1
    \$\begingroup\$ @Secret No, I just wanted to overshoot by a bit, plus working out a closer value to TREE(3) would cost me more bytes to write out. And there are no inaccessible cardinals used here. \$\endgroup\$ Commented Oct 21, 2017 at 12:14
  • 1
    \$\begingroup\$ Golf nitpicks: You can definitely golf a.class!=Array, most idiomatic is !a.is_a? Array but shortest I can think of is a!=[*a]. And the methods can be converted into lambdas: f=->a,n=0,b=a{...}...f[x,y] to save some characters and maybe open up refactoring possibilities using them as first-class objects. \$\endgroup\$
    – histocrat
    Commented Oct 24, 2017 at 16:05

Haskell, 252 Bytes, TREE(3)+1

data T=T[T]Int
l(T n _)=1+sum(l<$>n)
a@(T n c)#T m d=any(a#)m||c==d&&n!m
x!_=null x
a n=do x<-[1..n];T<$>mapM(\_->a$n-1)[2..x]<*>[1..3]
s 0=[[]]
s n=[t:p|p<-s$n-1,t<-a n,(l t<=n)>any(#t)p]
main=print$[x|x<-[0..],null$s x]!!0

Thanks for help from H.PWiz, Laikoni and Ørjan Johansen for help golfing the code!

As suggested by HyperNeutrino, my program outputs TREE(3)+1, exactly (TREE is computable as it turns out).

T n c is a tree with label c and nodes n. c should be 1, 2, or 3.

l t is the number of nodes in a tree t.

t1 # t2 is true if t1 homeomorphically embeds into t2 (based on Definition 4.4 here), and false otherwise.

a n outputs a big list of trees. The exact list isn't important. The important property is that a n contains every tree up to n nodes, with nodes being labelled with 1, 2, or 3, and maybe some more trees as well (but those other trees will also be labelled with 1, 2, or 3). It is also guaranteed to output a finite list.

s n lists all sequences length n of trees, such that the reverse (since we build it backwards) of that sequence is valid. A sequence is valid if the nth element (where we start counting at 1) has at most n nodes, and no tree homeomorphically embeds into a later one.

main prints out the smallest n such that there is no valid sequences of length n.

Since TREE(3) is defined as the length of the longest valid sequence, TREE(3)+1 is the smallest n such that there are no valid sequences of length n, which is what my program outputs.


Python 2, 194 bytes, ~ Hψ(ΩΩΩ)(9)

where H is the Hardy hierarchy, and ψ is the ordinal collapsing function below the Bachmann-Howard ordinal defined by Pohlers.

Thanks to Jonathan Frech for -3 bytes.

def S(T):return 0if T==1else[S(T[0])]+T[1:]
def R(T):U=T[0];V=T[1:];exec"global B;B=T"*(T[-1]==0);return[S(B)]+V if U==1else[R(U)]*c+V if U else V
while A:A=R(A);c*=c
print c

Try it online!

Better spaced version:

def S(T):
  return 0 if T==1 else [S(T[0])]+T[1:]

def R(T):
  global B
  if T[-1]==0:
  if U==1: 
    return [S(B)]+V
  return [R(U)]*c+V if U else V

while A:
print c


This program implements a variant of the Buchholz hydra, using just labels of 0 and 1. Basically, at each step, we look at the first leaf node of the tree, and see if it is labelled with a 0 or a 1.

-If the leaf node is labelled with a 0, then we delete the leaf node, and then copy the tree starting from the parent of the leaf node c times, all of the copies connected to the grandparent of the leaf node.

-If the leaf node is labelled with a 1, then we search back towards the root until we reach an ancestor node labelled with a 0. Let S be the tree starting from that ancestor node. Let S' be S with the leaf node relabelled with 0. Replace the leaf node with S'.

We then repeat the process until we have nothing left but the root node.

This program differs from the normal Buchholz hydra procedure in two ways: First, after we do the above procedure, we recurse back up the tree, and do the label 0 copy procedure described above for each ancestor node of the original leaf node. This increases the size of the tree, so our procedure will take longer than the normal Buchholz hydra, and therefore lead to a bigger number in the end; however, it will still terminate because the ordinal associated with the new tree will still be less the the old tree. The other difference is, rather than start with c = 1 and increasing 1 each time, we start with c = 9 and square it each time, because why not.

The tree [[[1,1],1],0] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω), and so our resulting final number of about Hψ(ΩΩΩ)(9) will definitely exceed TREE(3).

  • \$\begingroup\$ Not so golfy my friend :-) \$\endgroup\$ Commented Oct 25, 2017 at 11:53
  • \$\begingroup\$ I know. I don't know how to reduce it further, at least not in Python. Maybe I can try to learn some Ruby. \$\endgroup\$
    – Deedlit
    Commented Oct 25, 2017 at 12:05
  • \$\begingroup\$ Is it possible to put R(T) all on one line? \$\endgroup\$ Commented Oct 25, 2017 at 20:47
  • \$\begingroup\$ @SimplyBeautifulArt Most likely yes (TIO link), though untested. \$\endgroup\$ Commented Oct 27, 2017 at 14:57
  • \$\begingroup\$ @JonathanFrech Thanks for your help! Unfortunately, when I tried your code it gave an error message "global B is not defined". I have no idea why this gives an error while the original code does not, so I don't know how to fix it. \$\endgroup\$
    – Deedlit
    Commented Oct 31, 2017 at 3:40

Javascript, 111 bytes, ~ \$f_{\psi(\Omega_\omega)}(6)\$

\$f\$ is the Fast-growing Hierarchy. \$ψ\$ is Buchholz's Psi. This entry, despite being 111 bytes, dominates all of the previous entries in both size and the amount of bytes (except for Loader's number).

Here is the code:


Here is the same code expanded out:

function P([y,z]) {
  if (y==0) {
    return z
  } else {
    k = JSON.stringify([P(y),z])
    return JSON.parse(k.replaceAll(JSON.stringify(z),k))


I'm going to explain both the P function and the for loop.

The Predecessor Function

The inputs of the predecessor function are binary trees with zeroes as leaf nodes. Here are some examples of binary trees:

  • 0
  • [0,0]
  • [[0,[0,0]],[0,0]]
  • [[[[[0,0],0],[0,0]],[0,0]],[[0,[0,0]],[0,[0,0]]]]
  • [[[[[[[[[[0,0],0],0],0],0],0],0],0],0],0]

The Predecessor function is defined like this:

  • P([0,z])=z
  • P([x,y])=[P(x),y] but with all instances of y replaced with [P(x),y]
  • P(0) is left undefined

Right away, we can see 0 represents the number \$0\$, and [0,z] represents the structure \$z+1\$. Natural numbers can be represented as [0,[0,[0,...[0,0]...]]] with \$n+1\$ zeroes. For example, \$1 =\$ [0,0], \$2 =\$ [0,[0,0]], \$3 =\$ [0,[0,[0,0]]], and so on.

Now consider the string [1,n] where \$n>1\$.

P([1,n])=[0,n] but replace all instances of \$n\$ with [0,n] \$\to\$ [0,[0,n]]

Therefore, [1,n] corresponds to \$n+3\$, as P(P(P([1,n]))) = n

By this logic, [2,n] corresponds to \$n+7\$, [3,n] corresponds to \$n+15\$, and [n,n] would approximately correspond to \$2^n\$. Maybe [[0,n],n] corresponds to \$2^{n+1}\$?

Not so fast!

Consider the string [[0,n],n]. One would expect this to correspond to \$2^{n+1}\$, but it is much stronger. P([[0,n],n]) \$\to\$ [P([0,n]),n] = [n,n], but then the second step would be to replace all instances of n with the entire tree, or [n,n]. This makes P([[0,n],n])=[[n,n],[n,n]] rather than [n,[n,n]].

One would ask whether this would cause an infinite loop. Let's try P([[n,n],[n,n]]). If we let J = P([n,n]), we will get:

P([[n,n],[n,n]])=[J,[n,n]] but with all instances of [n,n] replaced with [J,[n,n]]

However, there are no instances of [n,n] within J, because J is strictly less than [n,n]. Therefore, P([[n,n],[n,n]])=[J,[J,[n,n]]]. This works for all J less than [n,n].

So this means [[0,n],n] corresponds to \$2^{2^n}\$. [[0,[0,n]],n] corresponds to \$2^{2^{2^{2^n}}}\$. And finally, [[n,n],n] corresponds to \$n \uparrow\uparrow n\$. Now it is time to bring in the Middle Growing Hierarchy.

Middle Growing Hierarchy

The Middle Growing Hierarchy is defined here: https://googology.wikia.org/wiki/Middle-growing_hierarchy

One can make an approximate distinction with the Middle Growing Hierarchy.

  • [0,n] corresponds to \$m(0,n) \sim n+1\$
  • [1,n] corresponds to \$m(2,n) \sim n+3\$
  • [2,n] corresponds to \$m(3,n) \sim n+7\$
  • [n,n] corresponds to \$m(n,n) \sim n+2^n\$ and \$m(ω,n)\$
  • [n,[n,n]] corresponds to \$m(n+1,n) \sim 2^{n+1}\$ (not \$m(ω+1,n)\$)
  • [[0,n],n] corresponds to \$m(ω+1,n) \sim 2^{2^n}\$
  • [[0,[0,n]],n] corresponds to \$m(ω+2,n) \sim 2^{2^{2^{2^n}}}\$
  • [[1,n],n] corresponds to \$m(ω+3,n) \sim 2^{2^{2^{2^{2^{2^{2^{2^n}}}}}}}\$
  • [[n,n],n] corresponds to \$m(ω2,n) \sim n \uparrow\uparrow n\$

One can see a correspondence with the left-hand side of the binary tree and the inner subscript of the Middle Growing Hierarchy. Let's continue the correspondence. I will omit the right hand side of the binary tree and the base of the Middle Growing Hierarchy.

  • [n,n] corresponds to \$ω_2\$
  • [0,[n,n]] corresponds to \$ω_2+1\$
  • [n,[n,n]] corresponds to \$ω_3\$
  • [[0,n],[n,n]] corresponds to \$ω_4\$
  • [[1,n],[n,n]] corresponds to \$ω_6\$
  • [[0,n],n] corresponds to \$ω^2\$

So it seems like there is a jump from [[n,n],n] to [[[0,n],n],n], similar to the jump from [n,n] to [[0,n],n]. But even this doesn't capture the power of this notation.

More Ordinal Comparison

  • [n,[[0,n],n]] corresponds to \$ω^2+ω\$
  • [[n,n],[[0,n],n]] corresponds to \$2\timesω^2\$
  • [[n,[n,n]],[[0,n],n]] corresponds to \$ω^3\$
  • [[[0,n],[n,n]],[[0,n],n]] corresponds to \$ω^4\$
  • [[[0,n],n],[[0,n],n]] corresponds to \$ω^ω\$

We're not even at [[0,[0,n]],n] yet, what is going on?

  • [[[0,n],n],[[[0,n],n],[[0,n],n]]] corresponds to \$2\timesω^ω\$
  • [[n,[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω+1}\$
  • [[[n,n],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_2}\$
  • [[n,[[n,n],[[0,n],n]]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_2+1}\$
  • [[[0,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_3}\$
  • [[[n,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω^2}\$
  • [[[[0,n],[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω^3}\$
  • [[0,[0,n]],n] corresponds to \$ω^{ω^ω}\$

Where does the strength comes from? The strength lies in the fact that the binary tree notation corresponds to performing the Middle Growing Hierarchy on ordinals! Here are some examples:

  • [n,n] corresponds to \$m(ω,n)=n+2^n\$, so [n,n] as an ordinal corresponds to \$ω+2^ω=ω_2\$
  • [[0,n],n] corresponds to \$m(ω+1,n)=2^{n+2^n}\$, so [[0,n],n] as an ordinal corresponds to \$2^{ω+2^ω}=2^{ω_2}=ω^2\$
  • [[[0,n],n],[[0,n],n]] corresponds to \$m(ω,m(ω+1,n))=2^{2^{n+2^n}}\$, so [[[0,n],n],[[0,n],n]] as an ordinal corresponds to \$2^{2^{ω+2^ω}}=ω^ω\$
  • [[0,[0,n]],n] corresponds to \$m(ω+2,n)=2^{2^{2^{n+2^n}}}\$, so [[0,[0,n]],n] as an ordinal corresponds to \$2^{2^{2^{ω+2^ω}}}=ω^{ω^ω}\$

As it turns out, this pattern continues. I'm not going to go through the full analysis, but here are some more ordinal values. Remember that these are ordinals, not functions!

  • [[1,n],n] corresponds to \$ω^{ω^{ω^{ω^{ω^{ω^ω}}}}}\$
  • [[n,n],n] corresponds to \$ε_0\$
  • [[n,[n,n]],n] corresponds to \$ζ_0\$
  • [[[0,n],n],n] corresponds to \$φ(ω,0)\$
  • [[[n,n],n],n] corresponds to the BHO

Speed of Notation

Essentially, if a structure \$K\$ corresponds to \$g_a (n)\$ in the slow-growing hierarchy, then the structure [K,n] corresponds to \$m_a (n)\$ in the middle-growing hierarchy. This makes the limit [[[...,n],n],n], which corresponds to the first SGH-MGH catching point, of \$ψ(Ω_ω)\$. For comparison, \$\text{TREE}(n)\$ only corresponds to the ordinal \$ψ(Ω^{Ω^ω})\$, much much smaller. The premise of this notation is essentially nested Goodstein sequences, except it works!

The Middle Growing Hierarchy corresponds closely to the Fast Growing Hierarchy, this is why I put in \$f_{ψ(Ω_ω)}\$ as it is a catching point.

Actual Value of the program

Now that we have gone through the Predecessor function, and how it corresponds to numbers, functions, and ordinals, it is time to return to the value of this program.

To extract a value from a binary tree, such as [[[0,0],0],0], one would have to repeatedly apply the predecessor function until the value crashes down to 0. As we seen before, one would have to apply the predecessor function a massive amount of time, on the order of \$m(ψ(Ω_ω),x)\$

Just to let you know, [[[...,0],0],0] is not degenerate, unlike stuff like \$2 \uparrow\uparrow...\uparrow\uparrow2 = 4\$ in arrow notation. [[[...,0],0],0] will produce a massive number.

Here is the code again:


First, it sets a and b equal to 0. Then, it starts incrementing b. If b is less than 9, then it sets a to [a,0]. This means at b=9, a would had been already [[[[[[[[[0,0],0],0],0],0],0],0],0],0], which corresponds to a massive number. Then, the predecessor function gets repeatedly applied to a, increasing b by 1 for each application. Eventually, a is going to crash down to 0, but b will be some value far, far greater than \$\text{TREE}(3)\$, or \$\text{TREE}(\text{TREE}(...\text{TREE}(3)...))\$ with \$\text{TREE}(3)\$ nests. Finally, the program returns b.

So what?

One of the best thing about this program is how the notation enumerates the catching points between the SGH and the MGH. This program only reaches the very first catching point, but by a few simple extension, this program is able to formalize a meameamealokkapoowa oompa, surpass Strong Array Notation, and beat every single Ordinal Collapsing Function ever devised. \$ψ(Ω_ω)\$ is still a pathetically small value...

  • \$\begingroup\$ Welcome to the site, and impressive first answer! I've edited in some formatting and Mathjax to make the answer more readable. Feel free to revert or edit anything I've gotten wrong, or that you don't like, and don't hesitate to ping me (using @cairdcoinheringaahing) if you need any help/tips on editing/formatting \$\endgroup\$ Commented Feb 21, 2021 at 18:47
  • \$\begingroup\$ This is amazing, getting way higher than BHO this fast is incredible. \$\endgroup\$
    – nph
    Commented Sep 18, 2021 at 21:34
  • \$\begingroup\$ Also, you claim that with some simple extentions, this can go much higher. What extentions are these? \$\endgroup\$
    – nph
    Commented Sep 18, 2021 at 22:12
  • \$\begingroup\$ @SimplyBeautifulArt looks like you've been dethroned \$\endgroup\$ Commented Dec 2, 2021 at 18:13
  • \$\begingroup\$ Maybe this notation is related to extracting ordinals from "tree ordinals", shown here? log.chez.com/text/logic/ordinal_notations_v2.pdf#page=53 \$\endgroup\$
    – C7X
    Commented May 31, 2022 at 5:51

Julia, 569 bytes, Loader's Number

r,/,a=0,div,0;¬x=x/2;r<s=r?s:0;y\x=y-~y<<x;+x=global r=(x%2!=0)<1+(+¬x);!x=¬x>>+x;√x=S(4,13,-4,x);S(v,y,c,t)=(!t;f=x=r;f!=2?f>2?f!=v?t-(f>v)%2*c:y:f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x)):S(v,y,c,!x)$S(v,y,c,+x));y$x=!y!=1?5<<y\x:S(4,x,4,+r);D(x)=(c=0;t=7;u=14;while(x!=0&&D(x-1);(x=¬x)%2!=0)d=!!D(x);f=!r;x=!r;c==r<((!u!=0||!r!=f||(x=¬x)%2!=0)<(u=S(4,d,4,r);t=t$d);¬f&(x=¬x)%2!=0<(c=d\c;t=√t;u=√u));(c!=0&&(x=¬x)%2!=0)<(t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);c=r);¬u&(x=¬x)%2!=0<(c=t\c;u=√t;t=9)end;global a=(t\(u\(x\c)))\a);D(D(D(D(D(BigInt(99))))))

To save myself a bit of legwork, I decided to port Loader.c to Julia nearly one-for-one and compact it into the block of code above. For those that want to do the comparisons themselves (either to verify my scoring or to help me find mistakes or improve my code), an ungolfed version is below:

+x=global r=(x%2!=0)<1+(+¬x);
    global a=(t\(u\(x\c)))\a

No previous counts because I made way too many byte miscounts in the aggressive golfing I've done.

  • 1
    \$\begingroup\$ Oh dear. 1 more addition to this madness of a place. \$\endgroup\$ Commented Nov 10, 2017 at 2:09
  • 1
    \$\begingroup\$ Also, while I've no proof of this, I think that D(D(D(D(99)))) is large enough. :| Maybe D(D(D(99))) is large enough. \$\endgroup\$ Commented Nov 10, 2017 at 2:11
  • 1
    \$\begingroup\$ If anyone wants to help me here, the next logical plan of attack is to generate a macro to compact "(x=¬x)%2!=0" into a single-letter macro. Can't figure out Julia macros myself, so someone else could be of use here. \$\endgroup\$ Commented Dec 4, 2017 at 3:32

Ruby, 140 bytes, ~ Hψ(ΩΩΩ)(81)

where H is the Hardy hierarchy, and ψ is the standard ordinal collapsing function below the Bachmann-Howard ordinal, as defined here.

($c*=9;a=r[a])while a[0]

Try it online!

Ungolfed version:

def S(a)
  *v, u = a
  if a == 1 
    return []
    return v + [S(u)]

def R(t)
  *v, u = t
  if t[0] == []
    $b = t
  if u == 1
    return v + [S($b)]
  elsif u == []
    return v
    return v + [R(u)]*$c

$c = 9

a = [[],[1,[1,1]]]

while a != [] do
  $c *= 9
  a = R(a)

print $c

This program implements the Buchholz hydra with nodes labelled with []'s and 1's, as described in my Python 2 entry.

The tree [[],[1,[1,1]]] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω) = ψ(ΩΩωω), and so our resulting final number of about Hψ(ΩΩΩ)(81) will exceed TREE(3).

  • \$\begingroup\$ Dang it you and your 149 bytes. \$\endgroup\$ Commented Nov 1, 2017 at 22:59
  • \$\begingroup\$ But Ruby for the win :P \$\endgroup\$ Commented Nov 1, 2017 at 23:04
  • \$\begingroup\$ Golf nitpick: Rather than writing u==0?v:u==[]?v you could write u==0?||u[0]?v, which saves two bytes. \$\endgroup\$ Commented Nov 7, 2017 at 11:43
  • \$\begingroup\$ @SimplyBeautifulArt Thanks for the help! Balls back in your court. :D \$\endgroup\$
    – Deedlit
    Commented Nov 7, 2017 at 13:11
  • 2
    \$\begingroup\$ D:< that 1 byte difference between us is the most frustrating thing ever. \$\endgroup\$ Commented Nov 9, 2017 at 12:24

Javascript, 511 bytes

I am new to code golf (this is my second time), but certainly not to implementing or inventing large numbers. However this programs takes quite a lot of code to beat TREE(3) :( The program results in \$f_{TFBO+1}(3) = f_{TFBO}(f_{TFBO}(f_{TFBO}(3)))\$ in the fast-growing hierarchy, where \${TFBO}\$ is the Takeuti-Feferman-Buchholz Ordinal \$\psi(\Omega_{\omega+1})\$. It uses Buchholz hydras and implements the BH function. Here is my compressed code, which was done with Naruyoko's Javascript compressor:

_="69{%t.length-1D*6m#{%B]}*6s#{t.splice(m#,14*@n=1;*6e#{7==0/s#;if(9>1/$i=0;i<n;i:t'B-1]4}}7>0&&typeof t==\"number\"/$i=98t[i]<m#8i--/}@s;$j5i8j <= 98j:s't[j]4@?5s;?[j]=?[i]-1;?[l(?)]=0;s#;$k508k <= l(?)8k:t'?[k]4}7==A/B]=n+1Dn += 1;%tD*6b(k/i5[\"+\",0];$l508l < k-28l:i'A)}while(l(i)>=0/i=e(i4%nD*Console.log(b(b(b(3))));#(t)$for(let %return '.push(*\n    /){4)D5 = 6function 7if(m#8; 9l#:++/?sa@var A\"w\"Bt[9D;}";for($ of"DBA@?:987654/*'%$#")with(_.split($))_=join(pop());eval(_)

This is basically incomprehensible, with only fragments of the original code revealing themselves, so here is the original code (still somewhat golfed):

function l(t){return t.length-1;}
function m(t){return t[l(t)]}
function s(t){t.splice(m(t),1);}
var n=1;
function e(t){if(m(t)==0){s(t);if(l(t)>1){for(let i=0;i<n;i++){t.push(t[l(t)-1]);}}}if(m(t)>0&&typeof t=="number"){for(let i=l(t); t[i]<m(t); i--){}var s;for(let j = i; j <= l(t); j++){s.push(t[j]);}var sa = s;sa[j]=sa[i]-1;sa[l(sa)]=0;s(t);for(let k = 0; k <= l(sa); k++){t.push(sa[k]);}}if(m(t)=="w"){t[l(t)]=n+1;}n += 1;return t;}
function b(k){i = ["+",0];for(let l = 0; l < k-2; l++){i.push("w")}while(l(i)>=0){i=e(i);}return n;}


This program, as I mentioned earlier implements Buchholz hydras, which are stored as arrays. This is what the code does:

It defines shorthands l(t), the index of the last element of the array, m(t), the last element of the array, and s(t), which chops off the last element of the array (the rightmost head). I also define a counter n which keeps track of how many times the hydra has been expanded.

The biggest block of code is e(t), which expands the hydra. Here is how it works: it checks if the rightmost head (which it will chop off) has label zero. If it does, then it calls s(t), splicing the last item in the array, and checks if l(t)>1, i.e. the rightmost head's parent is not the root. If it is, then it uses a for loop to push n copies of the rightmost head's parent (which is not the root).

Next, if it is not zero, it checks if it is a positive integer. If it is, it uses a for loop to find i such that t[i] has a lower label than the rightmost head. Then it creates a tree s such that everything after (and including) t[i] is in s, i.e. the subtree rooted at t[i]. It also creates sa where the rightmost head is relabeled with sa[i]-1 and the rightmost head of sa is relabeled with 0. It then deletes t's rightmost head and uses a for loop to insert sa into t.

If it is not zero, then it can only be the least limit ordinal omega (represented by the string "w"). If it is, it simply relabels it with n+1. After everything, it increments n by 1 and returns the new version of t.

Next, we have the function b(n), which represents the function BH(n). It sets i to the tree [+,0] and then pushes n-2 copies of omega "w". It then repeatedly applies e to i (expands i) and returns the final output. My large number is then b(b(b(n)))


Why does this produce a large enough number? Well, the original inventor, Wilfried Buchholz, proved that this function eventually dominates (overtakes) any function which is provably total in \$\Pi^1_1\$-comprehension with bar induction (\$\Pi^1_1-CA+BI\$), so the \$BH(n)\$ function is commonly approximated to \$\psi_0(\varepsilon_{\Omega_\omega +1})\$ using the fast-growing hierarchy, so my number is approximately \$f_{ψ(\varepsilon_{\Omega_\omega+1})+1}(3)\$.

The goal is \$\psi_0(\Omega^{\Omega^\omega \omega})\$, which is much less than \$\psi_0(\varepsilon_{\Omega+1})\$, let alone \$\psi_0(\varepsilon_{\Omega_\omega+1})+1\$. In fact, not only does this number defeat TREE(3), it also defeats SCG(13), which is around \$\psi_0(\Omega_\omega)\$, although it still falls massively short of Loader's number.

In terms of size, my entry would come second place, while in terms of length, it would come second-to-last. The latter is what matters more, so this is probably a really bad entry.

  • 1
    \$\begingroup\$ Hello again! I'm noticing that you format most your math in terms of unicode characters. You can use tex here, anything in between \$ and \$ will be rendered as tex. Also if you'd like to chat about googology on this site I've set up a room for it. If you are looking for more challenges about big numbers I suggest looking at the busy-beaver tag. \$\endgroup\$
    – Wheat Wizard
    Commented Nov 20, 2021 at 14:10
  • \$\begingroup\$ Oh, I didn't know you could use TeX, thanks for letting me know. And I will take a look at the busy-beaver tag, thanks for pointing me to it. \$\endgroup\$
    – Binary198
    Commented Nov 20, 2021 at 14:23

JavaScript, 190 bytes, Hψ(εΩ+1)(9)Based off of this analysis


This program is a modified version of this 225B Pair-sequence number translation in JavaScript. For Pair-sequence number and their original code, see here.

The modifications done:

  • It is in JavaScript instead of BASIC.
  • No iteration(fψ(Ωω+1)->fψ(Ωω))
  • The sequence is (0,0)(1,1)(2,2), which corresponds to ordinal ψ(εΩ+1).This is in Hardy-hierarchy ordinal

Python, 359 (184 without whitespace) 224 212 bytes, ~$$H_{ψ(ψ_Ι(0))[7]}(8)$$

while S:
 for a in S[::-1]:
  if d<S[-1]-a:
   r=r or i;d+=S[-1]-a-d>1
   if[k+d for k in S[i:]]<S[r:]:break
 if r:S=S[:p]+[d*i+k for i in range(n)for k in S[p:]]

I'm new to codegolf so I'm not sure if all the whitespace here counts. If not, this entry isn't the shortest entry, but vastly dominates patcail's entry in size. The code here implements Sudden Sequence System (definition here), which is known to have a perfect correspondence to ordinals below $$\psi(\psi_I(0))$$ represented in Extended Weak Buchholz function. The original idea uses sequences lexicographically less than (0,2) to represent ordinals, but to save characters the sequence itself is reversed. There are actually a few open problems here that we don't know the answer to, but strongly suspect they are true:

  1. Does the limit of Extended Weak Buchholz function equal to limit of Extended Buchholz function?
  2. Is Sudden Sequence System terminating?
  3. Does the correspondence between the two systems hold?

Edit 1: It's broken due to a silly mistake. Now S is correctly initialized. Thanks to Naruyoko for a few great optimizations.

Edit 2: Optimized a bit

  • 1
    \$\begingroup\$ Hi, welcome to code golf. Nice answer, looks good (I'm not on the laptop to test it out). Take your time reading the Welcome to Code golf if you haven't done so already. Btw, replace spaces with tabs to get shorter. There is also a Python tips page here, you could read it too, if you're interested. \$\endgroup\$
    – math scat
    Commented Jul 27, 2021 at 8:05

(0,0,0)(1,1,1)(2,2,1)(3,0,0)[1000] (SDO \$\psi(C(1\{\omega\}0))\$), 622 637 bytes

This is my first time on Stack Exchange, but I saw this post some time ago and I finally managed to make this. It implements the Subspecies Pair Sequence System (basically PSS but the second entry works like LPrSS) and outputs (0,0)(1,1000)[1000].

function spss(t,l){if(t.length){if(t[t.length-1][0]){if(t[t.length-1][1]){var e=t.lastIndexOf(t.filter((e,l)=>e[0]<t[t.length-1][0]&&e[1]<t[t.length-1][1]&&!t.slice(l+1,t.length).filter(l=>l[0]<=e[0]).length).pop()),s=t.slice(0,e),n=t.slice(e,-1),r=t[t.length-1][0]-t[e][0],i=t[t.length-1][1]-t[e][1]-1;return spss([...s,...Array(l).fill(n).map((l,t)=>l.map((l,e)=>[l[0]+r*t,!l[1]&&e?0:l[1]+i*t])).flat()],l)}var e=t.lastIndexOf(t.filter(l=>l[0]===t[t.length-1][0]-1).pop()),s=t.slice(0,e),n=t.slice(e,-1);return spss([...s,...Array(l).fill(n).flat()],l)}return spss(t.slice(0,-1),l+1)}return l} console.log(spss([[0,0],[1,1000]],1000));

Try it online!

I definitely lost with the character amount part, but it surpasses all other entries (except the one person who used Loader's program).


Japt, 39 Bytes, fPTO(Z2) (32) or BMS[32]

This is a port of this answer.

T°?UÊ?ßUcUsX=Uo)Ë<XfH ?D:D+UÊ-X:T:ßLÇ%H

I made a few golfing edits compared to my previous ;T°?UÊ?ßUcUsX=Uo)m_<X-X%BÊ?Z:Z+UÊ-X:T:ßBÊo cBÊo. Since I am able to use constants, I used L=100 instead of importing the alphabet and getting its length. I also used H=32, which allowed me to shave a few bytes in creating the BMS array. I also used a few other Japt substitutions.


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.