cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

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

Views

Author

Pontus von Brömssen, Jul 27 2024

Keywords

Comments

See A374992 for details.

Crossrefs

Analogous sequences for other updating strategies: A374998, A374999, A375000, A375001.
Cf. A025480, A066099 (compositions in standard order), A333766, A374992.

Formula

a(n) = A374992(n) - A374992(A025480(n-1)).
a(n) = A375001(k,n) whenever k >= A333766(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.

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

Views

Author

Pontus von Brömssen, Jul 27 2024

Keywords

Comments

See A374993 for details.

Crossrefs

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

Formula

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.

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

Views

Author

Pontus von Brömssen, Jul 27 2024

Keywords

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

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.

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

Original entry on oeis.org

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

Views

Author

Pontus von Brömssen, Jul 27 2024

Keywords

Comments

See A374994 for details.

Crossrefs

Analogous sequences for other updating strategies: A374997, A374998, A375000.
Cf. A025480, A066099 (compositions in standard order), A333766, A374994.

Formula

a(n) = A374994(n) - A374994(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.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.