Problems & Puzzles: Puzzles

Puzzle 172. Minimal Length, prime-complete-rules

A rule is defined by a set of marks on a straight and rigid rod. This set of marks define a sequence D of k distances di between each two contiguous marks

Rule: D = {d1, d2, , dk)

The length of the rod L is equal to the sum of all the distances in D.

L = d1 + d2 + + dk

A rule is said to be complete if every integer n, 1<=n<=L, can be obtained as a sum of certain subsequence of consecutive distances di  

Examples:

a)    The rod: D = {1, 3, 3, 2} is complete because:
1=1
2=2
3=3
4=1+3
5=3+2
6=3+3
7=1+3+3
8=3+3+2
9=1+3+3+2

b)    The rod: D = {1, 2, 3, 3} is incomplete because 4 & 7 can not be obtained using only consecutive distances di

Here we are interested only in complete prime rules, that is to say rules where all the members of D are "1" or prime numbers. Notice that any of the distances may be repeated in the sequence D.

Our puzzle here is to find the complete prime rule of minimal L that uses (at least once) each of the following numbers: "1" and the first K primes.

Here are the first solutions that I have obtained:

K

Distances available

Rules

L

0

1

1

1

1

1 & 2

1, 2

3

2

1, 2, & 3

1, 3, 2

6

3

1, 2, 3, &5

1, 3, 1, 5, 2

12

4

1, 2, 3, 5, & 7

1, 1, 2, 7, 3, 5, 1
1, 1, 5, 2, 7, 3, 1

20

5

1, 2, 3, 5, 7 & 11

?

?

Questions:

1. Find the minimal solutions for K= 5, 6, 7, 8, 9, & 10
2. Do you devise an algorithm to find these solutions?

______
Note: This puzzle is cousin but distinct to the well known puzzles: Golomb Rules and Sparser Rules, which certainly served greatly as inspiration.


Solution:

Several times I have had the opportunity to say 'every puzzle has its solver'. This is one more opportunity.

Ray Opao sent (July 18, 2004) the following minimal solutions for 5<=k<=8 and some 'principles' that he has obtained as a result of his search:

I came up with the following table using brute force for values up to K=8 and made these observations:

(1) To form a minimal rule, only the "1" should be repeated, and not the primes, as a prime can be decomposed into "1"s.

(2) The number of distances used in a minimal complete prime rule is less than or equal to the K-th prime.

Can a proof for (2) be supplied or is there a particular value of K where the number of distances in the minimal rule is greater than the K-th prime?

I haven't really found an efficient algorithm for coming up with minimal complete rules, as my procedure was more of brute force. I did some sieving though, by excluding rules that didn't start or end in a "1" (as the remaining length would be L-1), those that didn't start or end with a "2" or had a "1" on both ends (as the remaining length would be L-2), etc. If I found a complete rule for a particular K using W "1"s, I would recheck using W-1 "1"s. If I didn't find any complete rule, then the rule with W "1"s was minimum.

The tables below and the succeeding rules were thus obtained:

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

 

K L Minimal rules
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)

 

 



Records   |  Conjectures  |  Problems  |  Puzzles