Problems & Puzzles: Puzzles

Puzzle 212.  Substring reversion

Jon Perry sent the following interesting puzzle:

Given 1 2 3 4 5 6 7 8 9, you are allowed to reverse any consecutive group of digits, as long as their sum is prime. e.g. we might progress:

1 2 3 4 5 6 7 8 9
1 2 4 3 5 6 7 8 9
1 2 4 3 5 7 6 8 9
1 2 7 5 3 4 6 8 9

A permutation is not allowed to be repeated. What is the longest run achievable?

This is easy for smaller sets: e.g. n=2 has the complete run of 2 (1 2 -> 2 1) n=3 has 2 runs of 2 (1 2 3 -> 2 1 3 or 1 3 2) but soon gets more difficult.

Q1. Find the longest run for the starting string 123456789

Now, let me (C.R.) add the following natural variation.:

Let's start with a prime composed of nine distinct digits of the ten available. In each step you may reverse any substring (not necessarily these with a prime sum). A permutation is not allowed to be repeated

Q2. What is the largest path if all the permutations must be prime numbers?

Solution:

 Records   |  Conjectures  |  Problems  |  Puzzles