0,3

Each of these sets of functions is naturally a quotient set of the set of natural numbers (including 0) on which addition and multiplication are well-defined, thus forming a commutative rig (not ring) with a(n) elements.

This rig is the natural numbers modulo the congruence generated by setting a(n) equivalent to a(n)-n.

a(n) = lcm(seq(i, i=1..n))+n-1, except at n=0 (where the lcm is infinite).

a(2) = 3 as follows: Let {a,b} be a set with 2 elements. Then the 2^2 = 4 functions from {a,b} to itself are i (the identity function), t (the transposition), a (the constant function with value a) and b (the constant function with value b).

We're looking at functions from {i,t,a,b} to itself that are defined by typed lambda-calculus expressions. These expressions are lambda-f.(lambda-x.x), lambda-f.(lambda-x.fx), lambda-f.(lambda-x.ffx), lambda-f.(lambda-x.fffx) and so on.

Respectively, these map (i,t,a,b) to (i,i,i,i), (i,t,a,b), (i,i,a,b), (i,t,a,b), (i,i,a,b), (i,t,a,b) and so on. Only the first 3 of these are distinct; thereafter they are all repetitions. Therefore a(2) = 3.

a(n) = A060401(n)-1 = A003418(n)+n-1, except at n=0 (where the cross-references are undefined).

Sequence in context: A032159 A032064 A151397 this_sequence A120341 A094357 A136532

Adjacent sequences: A065497 A065498 A065499 this_sequence A065501 A065502 A065503

easy,nonn,nice

Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001