A374995 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, ...), where a requested element at position i is moved to position floor((i+1)/2).

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

Offset: 0

Author

Pontus von Brömssen, Jul 27 2024

Keywords

• nonn

Comments

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

After a request for an element at position i in the list (1-based), that element is moved to position floor((i+1)/2). Apparently, Bachrach and El-Yaniv consider the similar strategy where a requested element at position i is moved to position floor(i/2)+1 (MOVE-FRACTION(2) in their terminology). With this strategy, the element at the front of the list will stay there forever.

Examples

			For n=931 (the smallest n for which A374992(n), A374993(n), A374994(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 4 1 3 |         3
      ^   |
  2 1 4 3 |         2
    ^     |
  ---------------------------------------
          a(931) = 13
		

Links

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

Crossrefs

Analogous sequences for other updating strategies: A374992, A374993, A374994, A374996.

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

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)) + A375000(n) for n >= 1.