Golf a number bigger than TREE(3)



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?


Posted 2017-08-16T18:25:43.997

Reputation: 6 547

@AdmBorkBork TREE(3) is much harder to beat than Graham's number. None of the answers you list are valid here. – PyRulez – 2017-08-16T18:29:40.000

Separately from whether it's a duplicate or not, what's the winning criterion? – AdmBorkBork – 2017-08-16T18:41:28.273

@PyRulez none of those answers work, but unless I'm mistaken, they could be trivially lengthened to work. – Stephen – 2017-08-16T18:46:12.473

9@StepHen not trivally. Getting to Tree(3) requires a whole new paradigm. – PyRulez – 2017-08-16T18:58:12.750

@StepHen whoops, I always forget that. – PyRulez – 2017-08-16T19:00:25.133

@PyRulez from the (now deleted) comment about Ackermann, couldn't I just run a really big Ackermann? (and Ackermann is a builtin in several langs) – Stephen – 2017-08-16T19:01:47.880

@StepHen your input would need to be significantly bigger than Graham's number. – PyRulez – 2017-08-16T19:02:53.543

@PyRulez How will we know if we've done it? Say I define f(x) : f(2) = 2 and f(x>2) = f(x-1)^f(x-1). Is f(1000000) > TREE(3)? – benzene – 2017-08-16T19:04:26.280

@benzene you will need to use math. It doesn't look like your answer works though. I added a link describing the size of Tree(3). – PyRulez – 2017-08-16T19:05:33.927

@PyRulez It looks as though we only have weak lower bounds on Tree(3), not the actual value or upper bound expressions. What math can we use to determine if some number is larger than it? – benzene – 2017-08-16T19:12:07.170

@benzene the third note has some upper bounds. We don't have tight upper bounds, but we do have upper bounds. I listed some, in fact. – PyRulez – 2017-08-16T19:13:34.470

This paper by Friedman lends itself to very short and simple programs, but apparently the resulting function, though enormous, can't compete with TREE(3) even for very large inputs.

– Alon Amit – 2017-08-17T07:02:18.640

"It can be an integer, float, or any other number type that language supports. This number must be bigger than what is known as TREE(3)." Normally for this kind of question we assume that big integers are unbounded (despite the practical bounds imposed by implementation), but I don't recall any previous similar question which allowed floats and I'm not sure how to interpret this permission. – Peter Taylor – 2017-08-17T07:22:42.570

@PeterTaylor you can assume that are unbounded as well. (Just no infinity.) I was just trying to be open in what I allow. – PyRulez – 2017-08-17T13:26:24.560

Possible duplicate:

– KSmarts – 2017-08-18T13:37:51.240

@KSmarts that's not [tag:code-golf] – PyRulez – 2017-08-18T14:41:29.290

@fejfo I would, but I can't vote again, since I voted to reopen it once already. – PyRulez – 2017-10-14T18:24:12.733

11TREE(3)+1 there I win – HyperNeutrino – 2017-10-14T23:44:38.020

@HyperNeutrino in what programming language is that valid? – PyRulez – 2017-10-14T23:56:46.147

None; it's just theoretical, and I'm being facetious :P – HyperNeutrino – 2017-10-15T00:07:40.680

1@KSmarts You do realize none of the answers there come close to TREE(3)? – Simply Beautiful Art – 2017-10-19T23:53:34.803

Couldn’t I just output strings? In output, they’re identical to integers/floats... etc. – Stan Strum – 2017-10-20T17:09:21.873

@StanStrum why not just take the length of the string, which is basically the same thing? – PyRulez – 2017-10-20T17:41:37.373

@PyRulez I don’t like using numbers > 2 ^ 31 - 1 – Stan Strum – 2017-10-20T17:42:22.027

@StanStrum but your fine with strings that big? If you want, you could output a string of 9s, and that would count as outputting a number. – PyRulez – 2017-10-20T17:53:28.073

@StanStrum this question has already been closed and reopened twice, so I don't really want to change it – PyRulez – 2017-10-20T18:03:24.670

@PyRulez That’s alright. First, I’ll need to procrastinate my work to satisfy myself. Then, I’ll head off to my bash prompt and marker board. – Stan Strum – 2017-10-20T18:04:36.097

1@Stephen In order to reach TREE(3) using Ack(k,k), k will need to be on nearly the same order of magnitude as TREE(3). In particular, k needs to be on the level of f_ϑ(Ωω ω)+1(n), which is practically speaking TREE(3). – Simply Beautiful Art – 2017-10-20T20:50:32.070

@benzene See the previous comment. – Simply Beautiful Art – 2017-10-20T20:52:07.943

Does anyone know how many digits are in TREE(3)? I've looked around and all I've found is that it's too big to easily describe. Is it more or less than 2E15? – Engineer Toast – 2017-10-23T15:22:16.983

@EngineerToast about log(TREE(3)), which is much larger than tree(7) (note TREE and tree are different functions). – PyRulez – 2017-10-23T18:44:35.663

@PyRulez I couldn't find much on that but I did find something about Graham's number: "Writing out the number of digits it has would take more atoms that can be found on the planet, and that wouldn't even be remotely close!" Since TREE(3) is insanely larger than that, I'm going to say it's longer than 2E15 digits. Printing 9s for the next 7,000 years is not a valid solution, then. – Engineer Toast – 2017-10-23T19:14:36.573

@EngineerToast See this comment. It more or less transcribes into "the amount of digits of TREE(3) are so large, that it's on the same magnitude of TREE(3)." Generally, once numbers reach the scale of 1E(1E(1E(1E(1E(1E(...)))))) we say "the amount of digits" looks practically the same as the number itself. (hopefully that makes sense)

– Simply Beautiful Art – 2017-10-24T14:12:32.310

Is a solution like while (i++ < INT_MAX) while (j++ < INT_MAX) while (k++ < INT_MAX) while (l++ < INT_MAX) while (m++ < INT_MAX) printf("999"); allowed? – MD XF – 2017-10-26T03:25:51.890

2@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. – PyRulez – 2017-10-26T07:30:53.957

1@MDXF also, pretty sure you won't reach TREE(3) anytime soon like that. – Simply Beautiful Art – 2017-10-26T13:57:15.990

@HyperNeutrino Okay, you win. I made an answer with TREE(3)+1. It's needs to be better golfed if its going to win though. – PyRulez – 2017-10-27T23:57:14.453

If I output a string of digits, does that count? And if I print multiple times, will we concatenate the final results? – Simply Beautiful Art – 2017-11-01T14:15:39.973

@SimplyBeautifulArt yeah, that should be fine – PyRulez – 2017-11-01T21:04:51.460

You don't fix the number of k color... If that number is fixed I in the place of color use label {1..k+1} and my TREE(k+1) is bigger than your TREE(k) – RosLuP – 2017-11-05T13:31:42.493

1@RosLuP uhm, $k=3$. If you want to do $TREE(4)$, that's fine. (You have to write a program to output it though.) – PyRulez – 2017-11-05T15:41:47.920

@ØrjanJohansen Thanks for the generosity. – Simply Beautiful Art – 2017-11-09T17:22:26.770

Public service announcement: I'm opening a Discord server dedicated to explaining ordinals and the fast growing hierarchy. The end goal will be to reach an understanding of the magnitude of TREE(3) and larger things using only recursion, and lots of it.

– Simply Beautiful Art – 2017-11-10T11:57:14.193

Add the tag ([tag:tree-traversal])? – Simply Beautiful Art – 2017-11-14T16:29:16.837

@ØrjanJohansen Whoops sorry, wrong question. :P – PyRulez – 2017-11-15T04:54:10.957

See also: Ridiculously Huge numbers Part 20

– Simply Beautiful Art – 2018-03-20T23:51:18.800

@SimplyBeautifulArt I'm not sure. Answers do not need to do anything with trees, and most of them do not. TREE(3) is just a number that just so happens to be defined in terms of trees. Many number of similar magnitude are not defined in terms of trees. – PyRulez – 2018-12-03T18:36:34.060



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)

Simply Beautiful Art

Posted 2017-08-16T18:25:43.997

Reputation: 2 140

1I could only test my program for very few values, so do excuse me if I've made a mistake somewhere. – Simply Beautiful Art – 2017-10-20T20:19:49.997

1Bleh, slowly but surely trying to think my way through and fixing anything I see wrong. :-( So tedious. – Simply Beautiful Art – 2017-10-20T22:26:26.677

1Hmm... 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)$ – Secret – 2017-10-21T08:54:07.493

1@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. – Simply Beautiful Art – 2017-10-21T12:14:17.337

@SimplyBeautifulArt I'm trying to understand this but I just don't. – fejfo – 2017-10-21T18:03:57.380

@fejfo It's supposed to be that complicated ;) You can also visit my profile page for some chat rooms where you can try and get more explanation (which I may add into my answer) – Simply Beautiful Art – 2017-10-21T18:07:29.093

I'm pretty sure that before this mathematics didn't know an upper bound for TREE(3) (source: Numberphile video), well done! – Okx – 2017-10-21T21:17:23.283

@Okx See PyRulez's comment.

– Simply Beautiful Art – 2017-10-21T22:02:49.257

@SimplyBeautifulArt the upperbounds I listed where removed from the question, unfortunately. – PyRulez – 2017-10-23T04:45:44.183

Unfortunately, the fundamental sequence rules for ordinals up to this level are not so simple. You can see a definition of fundamental sequences at

– Deedlit – 2017-10-23T08:59:19.730

@Deedlit If I am not mistaken, ψ'_0(Ω_2) is the Bachmann-Howard ordinal? – Simply Beautiful Art – 2017-10-23T11:14:46.050

@PyRulez =P Feel free to add them in. Anyways, the second bullet point from the bottom says that I can aim to beat the fgh approximation of TREE(3) instead. – Simply Beautiful Art – 2017-10-23T13:58:39.133

Well, I'm not quite sure how ψ'_a(b) is defined, as it seems to be different from ψ_a(b). It looks like ψ'_a(n) for n finite is just going to be n, as the recursive process decrements the n each time. Also, it looks like when you reach a natural number in the recursive process, you decrement the number until it reaches 1, but when it is when you bump it back up to n again. This problem is avoided when b is just a number, but if say b = [c,d], then d will get decremented down to 1 and then bumped back up repeatedly. My biggest issue though is that the fundamental sequences are incorrect. – Deedlit – 2017-10-23T15:42:11.413

@Deedlit The main change is ψ'_a(b+1) = ψ'_a(b) + ψ'_a(b) – Simply Beautiful Art – 2017-10-23T15:43:46.017

@Deedlit I think I fixed the loop problem with 1 being bounced up to n. – Simply Beautiful Art – 2017-10-23T15:54:51.013

@Deedlit I realize the FS I've laid out above are not the norm, but they seem to align pretty well with Buchholz's function. In any case, what do you think is the supremum of this notation then? – Simply Beautiful Art – 2017-10-23T16:03:44.780

It looks to me like you get a primitive recursive function. The subscripts aren't really being used, so the recursive process comes down to a nesting of ψ's. We have ψ'_a(b+1) = ψ'_a(b)*2, so each inner nesting gets you an exponential. So, tetrational growth? I may be wrong about that, but you definitely aren't getting OCF power here. – Deedlit – 2017-10-23T16:19:04.860

@Deedlit At the bottom of this answer, I added some evaluations which I think to be true. Could you look them over? – Simply Beautiful Art – 2017-10-23T16:37:14.783

@Deedlit What do you mean by "the subscripts aren't really being used"? Are you talking about the subscripts on the Ω's or the ψ's? If you are talking about the Ω's, perhaps you missed the step i(n,Ω_c,b) = ψ'_(c-1)(b)[n-1], and if you are talking about the ψ's, then I'm not sure what you mean. – Simply Beautiful Art – 2017-10-23T16:40:54.120

@Deedlit Hm, I suppose the problem is, say, constructing (Ω_1)^2 in my notation... this might be a challenge... – Simply Beautiful Art – 2017-10-23T19:53:57.450

@Deedlit Think I can fix this by allowing nested subscripts e.g. Ω(Ω_1))? – Simply Beautiful Art – 2017-10-23T19:58:17.003

@Deedlit Should be fine now... more or less using my ordinal hyperoperator in an ordinal collapsing function. – Simply Beautiful Art – 2017-10-24T14:02:00.110

In your explanation: f(a) returns false if a is an array and false otherwise. So, it always returns false? I don't think that's right. – KSmarts – 2017-10-24T14:46:37.917

@KSmarts Typo in my explanation, thanks! – Simply Beautiful Art – 2017-10-24T14:53:06.570

1Golf 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. – histocrat – 2017-10-24T16:05:15.030

@histocrat Thanks for the tips! – Simply Beautiful Art – 2017-10-24T16:15:55.490

@histocrat Unfortunately, I myself am poorly versed in the language of lambdas. =P Should probably read up on them more sometime. – Simply Beautiful Art – 2017-10-24T16:23:05.793

@histocrat Hopefully I did the lambdas correctly. No idea as to how one would rewrite all of this by seeing them as first-class objects though – Simply Beautiful Art – 2017-10-27T21:10:22.933

Your only one byte away from

– PyRulez – 2017-10-28T00:04:49.013

@PyRulez Yup... working on it ;) – Simply Beautiful Art – 2017-10-28T01:12:12.040

@SimplyBeautifulArt I'm gaining in you as well. ;) – PyRulez – 2017-10-28T01:18:26.757

1@PyRulez D= Guess I'll get working on some super golfing ordinals then. – Simply Beautiful Art – 2017-10-28T01:20:54.913

@PyRulez =P I did it! x'D – Simply Beautiful Art – 2017-10-30T20:57:51.430

@SimplyBeautifulArt congratz! – Deedlit – 2017-10-31T03:41:07.977

=D try beating me again @Deedlit – Simply Beautiful Art – 2017-11-07T03:07:23.043

You may be interested in this challenge.

– PyRulez – 2018-12-04T02:01:09.487


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.


Posted 2017-08-16T18:25:43.997

Reputation: 6 547


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).


Posted 2017-08-16T18:25:43.997

Reputation: 371

Not so golfy my friend :-) – Simply Beautiful Art – 2017-10-25T11:53:45.100

I know. I don't know how to reduce it further, at least not in Python. Maybe I can try to learn some Ruby. – Deedlit – 2017-10-25T12:05:17.350

Is it possible to put R(T) all on one line? – Simply Beautiful Art – 2017-10-25T20:47:58.633

@SimplyBeautifulArt Most likely yes (TIO link), though untested.

– Jonathan Frech – 2017-10-27T14:57:15.863

@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. – Deedlit – 2017-10-31T03:40:04.943

@Deedlit The mistake I made involves the statement B=[B,T][T[-1]==0];, as the list tries to evaluate B, even though it is not yet defined. I wrote a three bytes longer, though hopefully working version, which uses string multiplication instead of an if/else statement (the global keyword should only be necessary when setting B, not when reading).

– Jonathan Frech – 2017-10-31T14:16:11.260

Wouldn't it be better to increment c before decrimenting A? – Simply Beautiful Art – 2017-11-01T11:09:39.457


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).


Posted 2017-08-16T18:25:43.997

Reputation: 371

Dang it you and your 149 bytes. – Simply Beautiful Art – 2017-11-01T22:59:06.853

But Ruby for the win :P – Simply Beautiful Art – 2017-11-01T23:04:10.933

Golf nitpick: Rather than writing u==0?v:u==[]?v you could write u==0?||u[0]?v, which saves two bytes. – Simply Beautiful Art – 2017-11-07T11:43:08.707

@SimplyBeautifulArt Thanks for the help! Balls back in your court. :D – Deedlit – 2017-11-07T13:11:05.353

:| Now we're tied. – Simply Beautiful Art – 2017-11-07T13:42:37.727

.... this is.... fun ... – Simply Beautiful Art – 2017-11-07T15:20:29.930

Save a byte: v+[s[$b]] can be changed to v<<s[$b]. – Simply Beautiful Art – 2017-11-08T17:20:19.217

I think your latest edit accidentally cut off some stuff. – Simply Beautiful Art – 2017-11-08T23:35:13.647

2D:< that 1 byte difference between us is the most frustrating thing ever. – Simply Beautiful Art – 2017-11-09T12:24:38.067

Okay, should be your turn. – Simply Beautiful Art – 2017-11-09T14:55:58.783

Ah, never mind, we're tied now... – Simply Beautiful Art – 2017-11-09T17:28:16.000

You should be able to reduce (...)while ... down to ... while ... – Simply Beautiful Art – 2017-11-22T00:25:33.967

-4 bytes. – Simply Beautiful Art – 2017-12-02T22:27:39.590


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.


Posted 2017-08-16T18:25:43.997

Reputation: 577

1Oh dear. 1 more addition to this madness of a place. – Simply Beautiful Art – 2017-11-10T02:09:07.160

1Also, 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. – Simply Beautiful Art – 2017-11-10T02:11:53.113

1If 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. – eaglgenes101 – 2017-12-04T03:32:28.110


JavaScript, 190B, 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


Posted 2017-08-16T18:25:43.997

Reputation: 459