Problems & Puzzles: Puzzles

Puzzle 914. Puzzle 172, revisited.

Almost 14 years ago Ray G. Opao sent his solutions to this interesting puzzle 172 related to Minimal-prime-complete-rules (MPCR).

Let's remember the basics about this issue.

A MPCR is a rod with marks that define a set of k distances. Each distance is a distance between two consecutive marks. All the distances allowed are 1 and the first K prime numbers. Any distance may be used one or several times (but only the "1" is repeated in the real minimal rods). The length L of the rod is just the sum of all the k distances used. With this kind of rods you may define any integer length from 1 to L as the sum of some consecutive distances as distributed in the ruler, at least in one way.

Example:

For K=4:

Set of distances allowed={1, 2, 3, 5, 7}

Total number of distances=7 (which means that the distance "1" is repeated three times)

One of these rules is: 1.1.2.7.3.5.1

Total length of this rod: L=20

Verification:
1=1
2=2
3=3
4=1+1+2
5=6
6=5+1
7=7
8=3+5
9=2+7
10=1+2+7
11=1+1+2+7
12=2+7+3
13=1+2+7+3
14=1+1+2+7+3
15=7+3+5
16=7+3+5+1
17=2+7+3+5
18=2+7+3+5+1
19=1+2+7+3+5+1
20=1+1+2+7+3+5+1

Mr. Opao found three distinct possible rulers for K=4:

1.1.2.7.3.5.1
1.1.5.2.7.3.1
1.1.7.5.2.3.1

Mr. Opao's nice work on this puzzle, solved these rods for K=1 to 8, and this is summarized in the following pair of tables:

Table #1

K L K-th prime number of distances number of "1"s number of distinct rules
0 1 NA 1 1 1
1 3 2 2 1 1
2 6 3 3 1 1
3 12 5 5 2 1
4 20 7 7 3 3
5 33 11 10 5 7
6 48 13 13 7 41
7 66 17 15 8 2
8 87 19 18 10 18


Table #2

K L Minimal rulers
0 1 1
1 3 1.2
2 6 1.3.2
3 12 1.3.1.5.2
4 20 1.1.2.7.3.5.1
1.1.5.2.7.3.1
1.1.7.5.2.3.1
5 33 1.1.2.1.11.7.1.5.1.3
1.1.2.11.1.7.1.3.5.1
1.1.2.11.1.7.1.5.1.3
1.1.7.2.5.11.1.1.3.1
1.3.5.1.7.1.11.1.1.2
1.5.1.3.7.1.11.1.1.2
1.5.3.7.11.1.1.1.1.2
6 48 1.1.1.1.1.1.2.1.13.11.5.7.3
1.1.1.1.1.1.3.13.11.5.7.2.1
1.1.1.1.1.3.13.1.11.5.7.2.1
1.1.1.1.1.7.1.13.5.11.3.1.2
1.1.1.1.11.2.1.7.13.5.1.3.1
1.1.1.1.11.2.7.1.13.5.1.3.1
1.1.1.1.13.1.7.11.3.5.1.1.2
1.1.1.1.2.13.3.11.5.7.1.1.1
1.1.1.1.3.1.11.1.13.1.7.2.5
1.1.1.1.3.13.2.11.5.7.1.1.1
(10/41)
7 66 1.1.1.1.11.1.1.2.13.7.17.1.3.5.1
1.1.1.1.11.2.1.1.13.7.17.1.5.3.1
8 87 1.1.1.1.1.1.19.1.1.1.13.17.11.1.5.2.7.3
1.1.1.1.1.1.19.1.1.1.13.17.11.1.5.3.2.7
1.1.1.1.1.1.19.1.1.1.13.17.11.1.5.3.7.2
1.1.1.1.1.1.19.1.1.11.1.17.13.1.2.7.5.3
1.1.1.1.1.1.19.1.1.11.1.17.13.7.3.5.1.2
1.1.1.1.1.1.19.1.1.13.1.17.11.1.5.2.7.3
1.1.1.1.1.1.19.1.1.13.1.17.11.1.5.3.7.2
1.1.1.1.1.1.19.1.13.1.17.11.7.1.5.3.1.2
1.1.1.1.1.1.19.1.13.1.17.11.7.1.5.3.2.1
1.1.1.1.1.1.19.1.13.1.17.11.7.5.3.1.1.2
(10/18)

Mr. Opao published the following sequence related to the Puzzle 172: A096221.

During all these almost 14 years nobody has reviewed and/or extended Mr. Opao's good work. Mmmmhhh...! It just happens!!!...Perhaps it's time to put hands to work again!

Q1. Can you verify the work of Mr. Opao for K<=8?

Q2. Can you extend these two tables for K=9 to 15?

I have another reason for revisiting this puzzle 172.

On Feb 3, 2018, Mr. Fausto Morales Díaz, sent to me by email an intriguing observation. He noticed that the "number of distances" as written in the Table 1 (1, 2, 3, 5, 7, 10, 13, 15, 18, on the 4th column in Table 1) may be obtained computing another very different thing: "the number of ways to represent prime numbers up to p(K+3) as the sum of another prime and a product of two consecutive positive integers".

The probable interest in this side of the story is that the quantities as defined by Mr. Morales are by far easier to compute, while we have any idea now about how to compute these same quantities from Mr. Opao's work. It seems that these quantities are obtained by Mr. Opao after a trial and error hard work of approximations (?)

The next five terms in the Table 1, as obtained from the Mr. Morales approach are: 21, 23, 28, 31, 35,... as you can easily check.

Q3. If and after Q2 is responded, can you say whether the computation extensions of Table 1 could be benefitted from Mr. Morales observation?

 

Contributions came from Emmanuel Vantieghem and Dmitry Kamenetsky.

***

Emmanuel wrote on March 1, 2018:

I verified Opao's result up to  K = 7 (p = 17)  without using Morales' device.
For the verification of the case  K = 8  I started immediately with 18 distances.
Examining the rules with 17 distances would be a serious waste of time if Morales' observation would be true.
But, with my method the computation still will take more than one week ...  
So, I guess an extension of Opao's results to K > 8 will be a gigantic job, even with the use of Morales' theorem.
 
Of course, I am very anxious to see a proof of Morales' result.

***

Dmitry wrote on March 2, 2018:

Q1. I verified the results for K<=8 and I believe that they are all correct. I did not check the number of solutions though.

 
Q2. Here are the best solutions I found for 9<=K<=15. For each K, I show the lowest L found. Better solutions may still be possible. The Morales number of distances prediction are given inside brackets [].

 
K=9, L=113, K-th prime=23, distances=22 [21], 1s=13
1 1 1 1 1 1 1 2 1 1 1 23 19 1 17 3 11 5 7 13 1 1
 
K=10, L=145, K-th prime=29, distances=26 [23], 1s=16
2 1 13 1 5 7 19 1 1 17 11 23 1 1 29 1 1 1 1 1 1 3 1 1 1 1 
 
K=11, L=179, K-th prime=31, distances=30 [28], 1s=19
1 1 1 1 1 1 1 1 1 1 2 31 1 1 1 1 17 11 23 1 29 19 3 1 5 7 13 1 1 1 
 
K=12, L=219, K-th prime=37, distances=34, [31] 1s=22
3 1 1 1 1 1 1 1 1 1 1 1 1 29 7 37 17 19 23 13 31 5 11 2 1 1 1 1 1 1 1 1 1 1
 
K=13, L=264, K-th prime=41, distances=39 [35], 1s=26
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 41 1 1 1 1 2 23 19 1 31 37 1 29 1 3 7 11 13 5 17
 
K=14, L=310, K-th prime=43, distances=43 [40], 1s=29
19 1 1 1 7 17 3 13 37 31 11 23 5 41 2 1 1 29 1 1 1 1 1 1 43 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
 
K=15, L=360, K-th prime=47, distances=47 [45], 1s=32
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 47 41 11 2 37 1 31 5 3 43 13 29 17 1 1 23 1 1 1 1 1 1 1 1 1 1 1 19 
 
Q3. The results above do not match the values predicted by Mr. Morales. I think his values could serve as a lower bound.

On March 3, 2018, Dmitry added:

I already have two improvements:
 
K=10, L=144, K-th prime=29, distances=25 [23], 1s=15
1 1 7 1 5 1 29 13 19 1 11 3 23 1 1 2 1 1 17 1 1 1 1 1 1 
 
K=11, L=178, K-th prime=31, distances=29 [28], 1s=18
1 1 1 1 13 11 1 1 19 29 3 23 7 5 17 1 31 2 1 1 1 1 1 1 1 1 1 1 1

On March 7, 2018, Dmitry added:

I've made further improvements:
K=12, L=218, K-th prime=37, distances=33 [31], 1s=21
1 1 1 1 3 1 1 2 1 37 1 1 1 7 17 1 23 1 29 31 1 1 19 1 1 1 11 1 5 1 13 1 1

K=13, L=262, K-th prime=41, distances=37 [35], 1s=24
17 5 1 1 1 1 1 1 1 1 19 13 31 11 23 7 29 37 341 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

K=14, L=308, K-th prime=43, distances=41 [40], 1s=27
1 1 1 1 1 1 1 1 1 1 2 17 13 29 11 7 19 37 31 3 5 23 41 43 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

K=15, L=358, K-th prime=47, distances=45 [45], 1s=30
17 3 1 1 1 1 1 1 1 1 1 1 1 23 1 19 37 41 43 1329 11 31 5 1 2 47 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

 Accordingly, Morales rules are still safe...

***

 
Records   |  Conjectures  |  Problems  |  Puzzles