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