A333958 The number of closed lambda calculus terms of size n that have a normal form, where size(lambda M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda.

0, 0, 0, 1, 0, 1, 1, 2, 1, 6, 5, 13, 14, 37, 44, 101, 134, 297, 431, 882, 1361, 2729, 4405, 8549, 14311, 27400, 47101, 89022, 156080, 293014, 521730, 975507, 1757787, 3278660, 5961402, 11112179

Offset

1,8

Comments

This sequence is uncomputable, like the corresponding Busy Beaver sequence A333479, which takes the maximum normal form size of the a(n) terms that have one.

Computed by Haskell program BB.lhs except for some TODOs at sizes 32..36 whose manual analysis has been added to output BB.txt

Links

Table of n, a(n) for n=1..36.

John Tromp, Haskell program BB.lhs for analyzing Busy Beaver numbers

John Tromp, annotated output of BB.lhs

Example

This sequence first differs from A114852 at n=18 where it excludes the shortest term without a normal form (lambda x. x x)(lambda x. x x), hence a(18) = 298-1 = 297.

Crossrefs

Cf. A114852, A195691, A333479, A004147.

Sequence in context: A030770 A307048 A188652 * A114852 A188048 A191529

Adjacent sequences: A333955 A333956 A333957 * A333959 A333960 A333961

Keyword

nonn,hard,more

Author

John Tromp, Apr 22 2020

Extensions

Terms > 2729 corrected by John Tromp, Mar 29 2025

a(32)-a(36) from John Tromp, Feb 03 2026

Status

approved