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.
- [All93] Lloyd Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Journal, 25(1), pp.14-20, arxiv:2206.12795, 1993.
There are more λ-calculus examples here.