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) |
|
