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,6

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.

Links

Table of n, a(n) for n=1..12.

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

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

Example

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.

Crossrefs

Sequence in context: A112772 A155505 A086258 * A063799 A086451 A190991

Adjacent sequences: A372005 A372006 A372007 * A372009 A372010 A372011

Keyword

nonn,more

Author

Tomas Rokicki, Apr 15 2024

Status

approved