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.

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, 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, 8, 8, 7, 7, 7, 7, 8, 8, 6, 8, 8, 7, 7, 8, 6, 10, 6, 6, 7

Offset

0,3

Comments

The cost of a request equals the position of the requested element in the list.

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).

References

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 1998, pp. 401-403.

Links

John Tyler Rascoe, Table of n, a(n) for n = 0..10000

Ran Bachrach and Ran El-Yaniv, Online list accessing algorithms and their applications: recent empirical evidence, Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5-7, 1997, 53-62.

Wikipedia, Self-organizing list.

Formula

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.

a(n) = a(A025480(n-1)) + A374998(n) for n >= 1.

Example

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:
   list   | position of requested element
  --------+------------------------------
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         2
    ^     |
  2 1 3 4 |         4
        ^ |
  2 1 4 3 |         2
    ^     |
  1 2 4 3 |         1
  ^       |
  ---------------------------------------
          a(931) = 11

Prog

(Python)
def comp(n):
    # see A357625
    return
def A374993(n):
    if n<1: return 0
    cost, c = 0, comp(n)
    m = list(range(1, max(c)+1))
    for i in c:
        j = m.index(i)
        cost += j+1
        if j > 0:
            m.insert(j-1, m.pop(j))
    return cost # John Tyler Rascoe, Aug 02 2024

Crossrefs

Row n=1 of A374996.

Analogous sequences for other updating strategies: A374992, A374994, A374995.

Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A374998.

Sequence in context: A306606 A229989 A126688 * A374995 A350238 A374994

Adjacent sequences: A374990 A374991 A374992 * A374994 A374995 A374996

Keyword

nonn

Author

Pontus von Brömssen, Jul 27 2024

Status

approved