cp's OEIS Frontend

A386674 Indices of ascending runs in a random sequence in order of decreasing expected length.

%I A386674 #32 Aug 10 2025 16:36:32
%S A386674 5,4,6,10,11,15,16,17,21,22,20,26,27,31,32,33,37,38,36,42,43,47,48,49,
%T A386674 53,52,54,58,59,63,64,65,69,68,70,74,75,79,80,81,85,84,86,90,91,95,96,
%U A386674 97,101,100,102,106,107,111,112,113,117,116,118,122,123,127
%N A386674 Indices of ascending runs in a random sequence in order of decreasing expected length.
%C A386674 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 decreasing order, then a(n) is the index k of the n-th entry in the list.
%C A386674 The set {a(n):n>=1} consists of those k for which L(k) > 2.
%C A386674 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 29<=n<=288.
%D A386674 Donald E. Knuth. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, second edition, 1998, pages 39-42,45,603.
%H A386674 David Bevan, <a href="/A386674/b386674.txt">Table of n, a(n) for n = 1..999</a>
%H A386674 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 A386674 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 A386674 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 A386674 The o.g.f. for L(k) is z*(1-z)/(exp(z-1)-z)-z.
%F A386674 Limit_{k->oo} L(k) = 2.
%F A386674 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 A386674 max{L(k) : k>=1} = L(5) = e^5 - 5*e^4 + 15/2*e^3 - 10/3*e^2 +5/24*e, so the fifth run (surprisingly) has longest expected length and a(1) = 5.
%t A386674 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];decList[n_]:=First/@Take[Reverse@SortBy[Table[{k,eLen[k]},{k,2n+8}],Last],n];decList@20
%Y A386674 The natural numbers are partitioned between this sequence and A386673.
%K A386674 nonn
%O A386674 1,1
%A A386674 _David Bevan_, Jul 28 2025