A367433 Number of successive Patcail predecessors of n-th binary tree.

0, 1, 2, 5, 3, 6, 4

Offset

0,3

Comments

A binary tree is either 0 or a pair [s,t] of binary trees. Binary trees are counted by Catalan numbers A000108 and ordered by their binary code as given by A014486. Subtrees s and t correspond to A072771 and A072772.

Patcail defined the predecessor of [0,t] as t, and of [s,t], where s has predecessor s', as the result of replacing with [s',t] each occurrence of t within [s',t].

a(7), corresponding to [[0,[0,0]],0], is too large to show, exceeding an exponential tower of 2^63 2's. a(8), corresponding to [[[0,0],0],0], is much larger still, starting to approach Graham's Number. The next 3 terms are modest again, at a(9)=4, a(10)=7, a(11)=5.

The (A014138 indexed) subsequence for left skewed binary trees 0, [0,0], [[0,0],0], [[[0,0],0],0] ... forms an extremely fast growing sequence, at Buchholz's Ordinal in the Fast Growing Hierarchy.

Initial predecessors of these left skewed trees have sizes a(n) satisfying

a(n+1) = (a(n)+1)*(a(n)+3), which is A056207 counting the number of binary trees of height <= n.

Links

Table of n, a(n) for n=0..6.

Code Golf, Patcail's winning answer to Code Golf challenge "Golf a number bigger than TREE(3)".

Example

a(3)=5, since the 3rd binary tree is [[0,0],0] and its 5 successive Patcail predecessors are [[0,0],[0,0]], [0,[0,[0,0]]], [0,[0,0]], [0,0], and 0:
Index   n         3              6              4          2      1   0
A014486(n)       12             50             42         10      2   0
A063171(n)     1100         110010         101010       1010     10   0
Tree       [[0,0],0]  [[0,0],[0,0]]  [0,[0,[0,0]]]  [0,[0,0]]  [0,0]  0
A367433(n)        5              4              3          2      1   0

Prog

(Haskell)
data T = N | C T T deriving (Eq, Show)
a014486 = [0..] >>= at where
  at 0 = [N]
  at n = [C s t | (ns, s) <- to$n-1, t <- at$n-1-ns]
  to n = (0, N):[(1+ns+nt, C s t)|n>0, (ns, s)<-to$n-1, (nt, t)<-to$n-1-ns]
predT (C N t) = t
predT (C s t) = go u where
  u = [predT s) t
  go v = if v==t then u else case v of
    N     -> N
    C s t -> [go s) (go t)
a367433 = map nPred a014486 where
  nPred N = 0
  nPred t = 1 + nPred (predT t)

Crossrefs

Cf. A000108, A014486, A014138, A056207.

Sequence in context: A340066 A212614 A037852 * A226214 A331212 A160516

Adjacent sequences: A367430 A367431 A367432 * A367434 A367435 A367436

Keyword

nonn

Author

John Tromp, Nov 18 2023

Status

approved