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.
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
***
|
