login
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.
6
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,4
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).
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.
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.
EXAMPLE
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
PROG
(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
CROSSREFS
Cf. A000120, A025480, A029837 (row n=0), A374993 (row n=1), A333766, A374992, A375001.
Sequence in context: A287528 A328312 A289281 * A212957 A035393 A068913
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved