Composites and Primes

Each composite number is the product of two or more prime numbers, and the prime numbers are {2, 3, 4, 5, 6, ...} with the composite numbers removed; 'composites' and 'primes' are two mutually recursive lists:




If the first prime is 2, the first composite must be 4=2×2 and hence 3 is the second prime, the second composite must be 6=2×3 and the third prime is 5, and so on.

Note that 'composites' is inspired by the Hamming numbers which are all integers of the form 2i3j5k, i,j,k≥0, i+j+k>1. For composites we have infinitely many potential factors (primes). This is another example of a 'circular program' [All89, All93] or corecursion.

References

{All89] Lloyd Allison, 'Circular Programs and Self-Referential Structures', Software Practice & Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, arxiv:2403.01866, February 1989.
[All93] Lloyd Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Journal, 25(1), pp.14-20, arxiv:2206.12795, 1993.
And other publications.

There are more λ-calculus examples here.