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

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

Offset: 0

Author

John Tromp, Nov 18 2023

Keywords

• nonn

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.

Examples

			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
		

Links

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

Crossrefs

Cf. A000108, A014486, A014138, A056207.

Programs

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)