login
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.
5
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,3
COMMENTS
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.
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 1998, pp. 401-403.
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
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.
EXAMPLE
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
CROSSREFS
Analogous sequences for other updating strategies: A374993, A374994, A374995, A374996.
Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A374997.
Sequence in context: A350238 A376937 A374994 * A352746 A330416 A359043
KEYWORD
nonn
AUTHOR
STATUS
approved