A386673 Indices of ascending runs in a random sequence in order of increasing expected length.

1, 2, 3, 7, 8, 9, 13, 14, 12, 18, 19, 23, 24, 25, 29, 30, 28, 34, 35, 39, 40, 41, 45, 46, 44, 50, 51, 55, 56, 57, 61, 60, 62, 66, 67, 71, 72, 73, 77, 76, 78, 82, 83, 87, 88, 89, 93, 92, 94, 98, 99, 103, 104, 105, 109, 108, 110, 114, 115, 119, 120, 121, 125

Offset: 1

Author

David Bevan, Jul 28 2025

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

The natural numbers are partitioned between this sequence and A386674.

Programs

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

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.