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

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

Offset: 1

Author

Tomas Rokicki, Apr 15 2024

Keywords

• nonn
• more

Comments

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.

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.

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.

Examples

			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.
		

Links

• Alexandre Muñiz, Reverse The List of Integers, Discussion on Mastodon.
• Alexandre Muñiz, Reverse The List of Integers, Discussion on Hacker News.