A374993 -id:A374993 - cp's OEIS frontend

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

Pontus von Brömssen, Jul 27 2024

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

			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

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.

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

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

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.

A374992 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 move-to-front updating strategy.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 3, 3, 4, 5, 3, 5, 4, 5, 4, 4, 5, 6, 6, 6, 5, 5, 6, 6, 5, 6, 4, 6, 5, 6, 5, 5, 6, 7, 7, 7, 4, 9, 8, 7, 6, 8, 4, 6, 7, 8, 7, 7, 6, 7, 7, 7, 6, 6, 7, 7, 6, 7, 5, 7, 6, 7, 6, 6, 7, 8, 8, 8, 8, 10, 9, 8, 7, 6, 7, 10, 7, 10, 9, 8, 7, 9, 7, 9, 6, 6

Offset: 0

Pontus von Brömssen, Jul 27 2024

nonn

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

After a request, the requested element is moved to the front of the list.

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

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

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, Move-to-front transform.
Wikipedia, Self-organizing list.

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

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

a(n) = A374996(k,n) whenever k >= A333766(n)-1.
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)) + A374997(n) for n >= 1.

A374998 Position of the last requested element 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.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 1, 4, 1, 1, 1, 3, 2, 2, 1, 5, 1, 3, 1, 3, 2, 2, 1, 4, 1, 1, 1, 3, 2, 2, 1, 6, 1, 2, 1, 2, 1, 3, 1, 4, 3, 1, 1, 3, 2, 2, 1, 5, 1, 3, 1, 3, 2, 2, 1, 4, 1, 1, 1, 3, 2, 2, 1, 7, 1, 2, 1, 4, 2, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 5, 2, 1, 2, 3, 2, 2, 1

Offset: 1

Pontus von Brömssen, Jul 27 2024

nonn

See A374993 for details.

Row n=1 of A375001.
Analogous sequences for other updating strategies: A374997, A374999, A375000.
Cf. A025480, A066099 (compositions in standard order), A333766, A374993.

a(n) = A374993(n) - A374993(A025480(n-1)).

Sum_{j=1..m} a(n*2^j+2^(j-1)) = m*(m+1)/2 if m >= A333766(n). 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.

A374994 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 frequency-count updating strategy.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 3, 3, 4, 5, 3, 5, 4, 5, 4, 4, 5, 6, 6, 6, 5, 5, 6, 6, 5, 6, 4, 6, 5, 5, 5, 5, 6, 7, 7, 7, 4, 9, 8, 7, 6, 8, 4, 7, 7, 8, 7, 7, 6, 7, 7, 7, 6, 6, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 10, 9, 8, 7, 6, 7, 10, 7, 10, 9, 8, 7, 9, 7, 9, 6, 6

Offset: 0

Pontus von Brömssen, Jul 27 2024

nonn

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

After a request, the requested element is moved so that the list is kept ordered by decreasing number of requests so far. In case of ties, the most recently requested element is placed before all other elements with the same number of requests.

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

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

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.

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

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

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

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

Original entry on oeis.org

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

Pontus von Brömssen, Jul 27 2024

nonn

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.

			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

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.

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

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

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A374992 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 move-to-front updating strategy.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A374998 Position of the last requested element 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.

Views

Author

Keywords

Comments

Crossrefs

Formula

A374994 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 frequency-count updating strategy.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula