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
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.
FORMULA
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.
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
KEYWORD
nonn,tabl
AUTHOR
Pontus von Brömssen, Jul 27 2024
STATUS
approved