login
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

%I #8 Jul 28 2024 17:00:31

%S 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,

%T 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,

%U 8,10,9,8,7,6,7,10,7,10,9,8,7,9,7,9,6,6

%N 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.

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

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

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

%H Ran Bachrach and Ran El-Yaniv, <a href="https://dl.acm.org/doi/10.5555/314161.314180">Online list accessing algorithms and their applications: recent empirical evidence</a>, Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5-7, 1997, 53-62.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Move-to-front_transform">Move-to-front transform</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-organizing_list">Self-organizing list</a>.

%F a(n) = A374996(k,n) whenever k >= A333766(n)-1.

%F 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.

%F a(n) = a(A025480(n-1)) + A374997(n) for n >= 1.

%e 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:

%e list | position of requested element

%e --------+------------------------------

%e 1 2 3 4 | 1

%e ^ |

%e 1 2 3 4 | 1

%e ^ |

%e 1 2 3 4 | 2

%e ^ |

%e 2 1 3 4 | 4

%e ^ |

%e 4 2 1 3 | 3

%e ^ |

%e 1 4 2 3 | 1

%e ^ |

%e ---------------------------------------

%e a(931) = 12

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

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

%K nonn

%O 0,3

%A _Pontus von Brömssen_, Jul 27 2024