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, 4404, 8548, 14310, 27397, 47095, 89014, 156049, 292954, 521639, 975319, 1757422, 3277997, 5960021, 11109379

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.

Links

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

Computed by changing "maximum $ (n,0,P Bot) :" in the main function of this Haskell program for analyzing Busy Beaver numbers to "length".

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,more

Author

John Tromp, Apr 22 2020

Status

approved