cp's OEIS Frontend

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

%I A386673 #38 Aug 10 2025 16:36:23
%S A386673 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,
%T A386673 50,51,55,56,57,61,60,62,66,67,71,72,73,77,76,78,82,83,87,88,89,93,92,
%U A386673 94,98,99,103,104,105,109,108,110,114,115,119,120,121,125
%N A386673 Indices of ascending runs in a random sequence in order of increasing expected length.
%C A386673 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.
%C A386673 The set {a(n):n>=1} consists of those k for which L(k) < 2.
%C A386673 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.
%D A386673 Donald E. Knuth. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, second edition, 1998, pages 39-42,45,603.
%H A386673 David Bevan, <a href="/A386673/b386673.txt">Table of n, a(n) for n = 1..1000</a>
%H A386673 Betty Jane Gassner, <a href="https://doi.org/10.1145/363067.363102">Sorting by replacement selecting</a>, Commun. ACM, 10(2):89-93, 1967.
%H A386673 William W. Hooker, <a href="https://doi.org/10.1145/363156.363189">On the expected lengths of sequences generated in sorting by replacement selecting</a>, Commun. ACM, 12(7):411-413, 1969.
%F A386673 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.
%F A386673 The o.g.f. for L(k) is z*(1-z)/(exp(z-1)-z)-z.
%F A386673 Limit_{k->oo} L(k) = 2.
%F A386673 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.
%e A386673 min{L(k) : k>=1} = L(1) = e-1, so the first run has shortest expected length and a(1) = 1.
%e A386673 The second and third runs have second and third shortest expected length, so a(2) = 2 and a(3) = 3.
%e A386673 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.
%t A386673 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
%Y A386673 The natural numbers are partitioned between this sequence and A386674.
%K A386673 nonn
%O A386673 1,2
%A A386673 _David Bevan_, Jul 28 2025