A372008 - OEIS

%I #29 Apr 16 2024 07:08:15

%S 0,0,0,0,0,14,26,74,86,126,106,130

%N Maximum number of moves to solve "Reverse The List of Integers" game with high value n.

%C Given a list of unique positive integers with a maximum value n, you can perform the following "moves": a) split one number into two numbers that sum to the original number, or b) add two adjacent numbers into a new number.  In all moves the list must not have duplicates or contain a value greater than n.

%C Some lists can be reversed (e.g., 1,6,3) and some cannot (e.g., 1,6,4).  The "distance" of a list is the smallest number of a moves to reverse it; this sequence deals with the maximum distance of all reversible lists.

%C For n<6, the only lists that can be reversed are the ones that are single-number sequences that are implicitly reversed in 0 moves.

%H Alexandre Muñiz, <a href="https://mathstodon.xyz/@two_star/112242224494626411">Reverse The List of Integers</a>, Discussion on Mastodon.

%H Alexandre Muñiz, <a href="https://news.ycombinator.com/item?id=40010066">Reverse The List of Integers</a>, Discussion on Hacker News.

%e For n=6, the worst case is 1,6,3 -> 1,4,2,3 -> 5,2,3 -> 4,1,2,3 -> 4,1,5 -> 4,6 -> 1,3,6 -> 1,3,2,4 -> 1,5,4 -> 6,4 -> 5,1,4 -> 3,2,1,4 -> 3,2,5 -> 3,2,4,1 -> 3,6,1.  There is no shorter solution for this list, and no other reversible list requires more than 14 moves. So a(6) = 14.

%K nonn,more

%O 1,6

%A _Tomas Rokicki_, Apr 15 2024