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:

On June 22, 2023, Giorgos Kalogeropoulos wrote:

Q1. I found a run of 35465 permutations that I am sending you in a txt file1. This is not the longest path but I believe it is very close to the longest path

Q2.  For the second question I found a path of 21582 prime permutations but it is not guaranteed to be maximum.
I'm sending the path in a second txt file2,

If anyone is interested I can send the complete graph for both of the questions to make their own research.

***

On June 28, 2023, Michael Branicky wrote:

Q1.  I found a path of length 36287, attached in Puzzle212-Part1.txt
Q2.  I found a path of length 25616, attached in Puzzle212-Part2.txt

***

 Records   |  Conjectures  |  Problems  |  Puzzles