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

Offset: 1

Author

John Tromp, Apr 22 2020

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A114852, A195691, A333479, A004147.

Extensions

Terms > 2729 corrected by John Tromp, Mar 29 2025