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.
%I A374994 #5 Jul 28 2024 17:00:53 %S A374994 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, %T A374994 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, %U A374994 8,10,9,8,7,6,7,10,7,10,9,8,7,9,7,9,6,6 %N 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. %C A374994 The cost of a request equals the position of the requested element in the list. %C A374994 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. %D A374994 D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 1998, pp. 401-403. %H A374994 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 A374994 Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-organizing_list">Self-organizing list</a>. %F A374994 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 A374994 a(n) = a(A025480(n-1)) + A374999(n) for n >= 1. %e A374994 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: %e A374994 list | position of requested element %e A374994 --------+------------------------------ %e A374994 1 2 3 4 | 1 %e A374994 ^ | %e A374994 1 2 3 4 | 1 %e A374994 ^ | %e A374994 1 2 3 4 | 2 %e A374994 ^ | %e A374994 1 2 3 4 | 4 %e A374994 ^ | %e A374994 1 4 2 3 | 1 %e A374994 ^ | %e A374994 1 4 2 3 | 1 %e A374994 ^ | %e A374994 --------------------------------------- %e A374994 a(931) = 10 %Y A374994 Analogous sequences for other updating strategies: A374992, A374993, A374995, A374996. %Y A374994 Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A374999. %K A374994 nonn %O A374994 0,3 %A A374994 _Pontus von Brömssen_, Jul 27 2024