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 A374995 #10 Jul 30 2024 11:08:10 %S A374995 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, %T A374995 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, %U A374995 8,8,8,7,7,7,8,8,6,8,8,7,7,9,6,10,6,6,7 %N 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). %C A374995 The cost of a request equals the position of the requested element in the list. %C A374995 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. %H A374995 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 A374995 Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-organizing_list">Self-organizing list</a>. %F A374995 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 A374995 a(n) = a(A025480(n-1)) + A375000(n) for n >= 1. %e A374995 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: %e A374995 list | position of requested element %e A374995 --------+------------------------------ %e A374995 1 2 3 4 | 1 %e A374995 ^ | %e A374995 1 2 3 4 | 1 %e A374995 ^ | %e A374995 1 2 3 4 | 2 %e A374995 ^ | %e A374995 2 1 3 4 | 4 %e A374995 ^ | %e A374995 2 4 1 3 | 3 %e A374995 ^ | %e A374995 2 1 4 3 | 2 %e A374995 ^ | %e A374995 --------------------------------------- %e A374995 a(931) = 13 %Y A374995 Analogous sequences for other updating strategies: A374992, A374993, A374994, A374996. %Y A374995 Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A375000. %K A374995 nonn %O A374995 0,3 %A A374995 _Pontus von Brömssen_, Jul 27 2024