Problems & Puzzles:
Puzzles
Puzzle 172. Minimal Length,
primecompleterules
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 Kth 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 Kth 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 L1), those that didn't
start or end with a "2" or had a "1" on both ends (as the remaining length
would be L2), etc. If I found a complete rule for a particular K using W
"1"s, I would recheck using W1 "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 
Kth 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) 
