A374996 Square array read by antidiagonals: T(n,k) is the total cost when the elements of the k-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the move-ahead(n) updating strategy; n, k >= 0.

0, 1, 0, 2, 1, 0, 2, 2, 1, 0, 3, 2, 2, 1, 0, 3, 3, 2, 2, 1, 0, 3, 4, 3, 2, 2, 1, 0, 3, 3, 4, 3, 2, 2, 1, 0, 4, 3, 3, 4, 3, 2, 2, 1, 0, 4, 4, 3, 3, 4, 3, 2, 2, 1, 0, 4, 4, 4, 3, 3, 4, 3, 2, 2, 1, 0, 4, 3, 5, 4, 3, 3, 4, 3, 2, 2, 1, 0, 4, 5, 3, 5, 4, 3, 3, 4, 3, 2, 2, 1, 0

Offset: 0

Author

Pontus von Brömssen, Jul 27 2024

Keywords

• nonn
• tabl

Comments

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

After a request, the requested element is moved n steps closer to the front of the list (or to the front if the element is already less than n steps from the front).

Examples

			Array begins:
  n\k| 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  ---+-----------------------------------------------
   0 | 0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4
   1 | 0  1  2  2  3  4  3  3  4  4  3  5  4  5  4  4
   2 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   3 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   4 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   5 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   6 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   7 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   8 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
   9 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  10 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  11 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  12 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  13 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  14 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
  15 | 0  1  2  2  3  4  3  3  4  5  3  5  4  5  4  4
		

Links

• John Tyler Rascoe, Antidiagonals n = 0..139, flattened
• 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

Cf. A000120, A025480, A029837 (row n=0), A374993 (row n=1), A333766, A374992, A375001.

Programs

Python

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

Formula

T(n,k) = A374992(k) if n >= A333766(k)-1.

The sum of T(n,k) over all k such that A000120(k) = j (number of requests) and A333766(k) <= m (upper bound on the requested elements) equals m^j * j * (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.

T(n,k) = T(n,A025480(k-1)) + A375001(n,k) for n >= 0 and k >= 1.