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