Set of numbers used in the smoothsort algorithm
This article relies too much on references to primary sources. Please improve this by adding secondary or tertiary sources. (July 2017) (Learn how and when to remove this template message)
The Leonardo numbers are a sequence of numbers given by the recurrence:

Edsger W. Dijkstra[1] used them as an integral part of his smoothsort algorithm,[2] and also analyzed them in some detail.[3]
A Leonardo prime is a Leonardo number that's also prime.
Values
The first few Leonardo numbers are
- 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ... (sequence A001595 in the OEIS)
The first few Leonardo primes are
- 3, 5, 41, 67, 109, 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... (sequence A145912 in the OEIS)
Modulo cycles
The Leonardo numbers form a cycle in any modulo n>=2. An easy way to see it is:
- If a pair of numbers modulo n appears twice in the sequence, then there's a cycle.
- If we assume the main statement is false, using the previous statement, then it would imply there's infinite distinct pairs of numbers between 0 and n-1, which is false since there are n^2 such pairs.
The cycles for n<=8 are:
Modulo
|
Cycle
|
Length
|
2
|
1
|
1
|
3
|
1,1,0,2,0,0,1,2
|
8
|
4
|
1,1,3
|
3
|
5
|
1,1,3,0,4,0,0,1,2,4,2,2,0,3,4,3,3,2,1,4
|
20
|
6
|
1,1,3,5,3,3,1,5
|
8
|
7
|
1,1,3,5,2,1,4,6,4,4,2,0,3,4,1,6
|
16
|
8
|
1,1,3,5,1,7
|
6
|
The cycle always end on the pair (1,n-1) , as it's the only pair which can precede the pair (1,1).
Expressions
- The following equation applies:

Proof