OFFSET
1,2
COMMENTS
Let L(k) be the expected length of the k-th (maximal) ascending run in a sequence of numbers drawn uniformly and independently from [0,1]. If the set {L(k) : k>=1} is sorted in increasing order, then a(n) is the index k of the n-th entry in the list.
The set {a(n):n>=1} consists of those k for which L(k) < 2.
L(k) is periodic with period approximately 5.332398 (see the formula below). Since this is close to 16/3, the sequence a(n), n>=1, exhibits long stretches of periodicity; e.g. a(n)-2*n has period 8 for 26<=n<=294.
REFERENCES
Donald E. Knuth. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, second edition, 1998, pages 39-42,45,603.
LINKS
David Bevan, Table of n, a(n) for n = 1..1000
Betty Jane Gassner, Sorting by replacement selecting, Commun. ACM, 10(2):89-93, 1967.
William W. Hooker, On the expected lengths of sequences generated in sorting by replacement selecting, Commun. ACM, 12(7):411-413, 1969.
FORMULA
If k>=2, then the expected length of the k-th ascending run is L(k) = k * Sum_{j=0..k-1} (-1)^j*(k-j)^(j-1)*exp(k-j)/j!. The expected length of the first run is L(1) = e-1.
The o.g.f. for L(k) is z*(1-z)/(exp(z-1)-z)-z.
Limit_{k->oo} L(k) = 2.
If z ~ 3.088843 + 7.461489i satisfies z=exp(z-1), then asymptotically L(k)-2 ~ 2*r^-k*cos(k*t), where r = |z| ~ 8.075566, and t = arg(z) ~ 1.178304 ~ Pi/2.666199.
EXAMPLE
min{L(k) : k>=1} = L(1) = e-1, so the first run has shortest expected length and a(1) = 1.
The second and third runs have second and third shortest expected length, so a(2) = 2 and a(3) = 3.
The fourth smallest value in the set {L(k) : k>=1} is L(7), so the seventh run has fourth shortest expected length and a(4) = 7.
MATHEMATICA
eLen[1]=N[E-1]; eLen[k_]:=N[k Sum[(-1)^j(k-j)^(j-1)/j!E^(k-j), {j, 0, k-1}], k+10]; incList[n_]:=First/@Take[SortBy[Table[{k, eLen[k]}, {k, 2n+8}], Last], n]; incList@20
CROSSREFS
KEYWORD
nonn
AUTHOR
David Bevan, Jul 28 2025
STATUS
approved