cp's OEIS Frontend

A374993 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the transpose updating strategy.

%I A374993 #12 Aug 03 2024 11:07:18
%S A374993 0,1,2,2,3,4,3,3,4,4,3,5,4,5,4,4,5,5,6,5,5,5,6,6,5,5,4,6,5,6,5,5,6,6,
%T A374993 6,6,5,7,7,6,6,8,4,6,7,8,7,7,6,6,7,6,6,6,7,7,6,6,5,7,6,7,6,6,7,7,7,7,
%U A374993 8,8,7,7,7,7,8,8,6,8,8,7,7,8,6,10,6,6,7
%N A374993 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the transpose updating strategy.
%C A374993 The cost of a request equals the position of the requested element in the list.
%C A374993 After a request, the requested element is transposed with the immediately preceding element (unless the requested element is already at the front of the list).
%D A374993 D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 1998, pp. 401-403.
%H A374993 John Tyler Rascoe, <a href="/A374993/b374993.txt">Table of n, a(n) for n = 0..10000</a>
%H A374993 Ran Bachrach and Ran El-Yaniv, <a href="https://dl.acm.org/doi/10.5555/314161.314180">Online list accessing algorithms and their applications: recent empirical evidence</a>, Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5-7, 1997, 53-62.
%H A374993 Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-organizing_list">Self-organizing list</a>.
%F A374993 The sum of a(j) over all j such that A000120(j) = k (number of requests) and A333766(j) <= m (upper bound on the requested elements) equals m^k * k * (m+1)/2. This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.
%F A374993 a(n) = a(A025480(n-1)) + A374998(n) for n >= 1.
%e A374993 For n=931 (the smallest n for which A374992(n), A374994(n), A374995(n), and a(n) are all distinct), the 931st composition is (1, 1, 2, 4, 1, 1), giving the following development of the list:
%e A374993    list   | position of requested element
%e A374993   --------+------------------------------
%e A374993   1 2 3 4 |         1
%e A374993   ^       |
%e A374993   1 2 3 4 |         1
%e A374993   ^       |
%e A374993   1 2 3 4 |         2
%e A374993     ^     |
%e A374993   2 1 3 4 |         4
%e A374993         ^ |
%e A374993   2 1 4 3 |         2
%e A374993     ^     |
%e A374993   1 2 4 3 |         1
%e A374993   ^       |
%e A374993   ---------------------------------------
%e A374993           a(931) = 11
%o A374993 (Python)
%o A374993 def comp(n):
%o A374993     # see A357625
%o A374993     return
%o A374993 def A374993(n):
%o A374993     if n<1: return 0
%o A374993     cost,c = 0,comp(n)
%o A374993     m = list(range(1,max(c)+1))
%o A374993     for i in c:
%o A374993         j = m.index(i)
%o A374993         cost += j+1
%o A374993         if j > 0:
%o A374993             m.insert(j-1,m.pop(j))
%o A374993     return cost # _John Tyler Rascoe_, Aug 02 2024
%Y A374993 Row n=1 of A374996.
%Y A374993 Analogous sequences for other updating strategies: A374992, A374994, A374995.
%Y A374993 Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A374998.
%K A374993 nonn
%O A374993 0,3
%A A374993 _Pontus von Brömssen_, Jul 27 2024