Problems & Puzzles:
Collection 20th
Coll.20th002.
Minimal set
of primes such that...
On
March 10, 2018, Claudio Meller posed the following puzzle:
What is the least
quantity K of primes and what are them, to obtain all the integers for 1
to certain target T, using only adding and subtracting operations and
using each prime at the much once in each equation (except in the
identity equation, p=p)
Example. For
T=20. K=4, {2, 3, 13, 17} because:
1 = 32
2
3
4= 1713
5 = 2+3
6= 1713+2
7= 1713+3
8= 1332
9= 2+3+1713
10= 133
11= 132
12= 133+2
13
14= 13+32
17
18= 17+32
19= 17+2
20=17+3
21= impossible
Q. Find K for T=50,
100, 200.
Contributions came from Giovanni Resta, Simon Cavegn,
Michael Hürter
***
Giovanni wrote:
The minimal sets of primes that cover the requested ranges
and fail
for the next integer
should be:
20 : 5, 7, 11, 13
50 : 2, 3, 5, 19, 23
100 : 2, 3, 7, 23, 67
200 : 2, 3, 13, 17, 53, 127
300 : 2, 3, 7, 23, 67, 97, 103
400 : 2, 3, 7, 23, 67, 149, 151
The
minimal solutions (in terms of number of primes and maximal prime)
of set of primes which can cover "at least" the given range are:
21 : 2, 3, 7, 11
52 : 2, 3, 7, 19, 23
100 : 2, 3, 7, 23, 67
201 : 2, 3, 7, 23, 67, 101
304 : 2, 3, 7, 23, 67, 101, 103
400 : 2, 3, 7, 23, 67, 149, 151
502 : 2, 3, 7, 23, 67, 191, 211
The best ranges that can be obtained with 4, 5, 6, or 7
primes are
(I think):
4 : 33 : 2, 3, 7, 23
5 : 100 : 2, 3, 7, 23, 67
6 : 299 : 2, 3, 7, 23, 67, 199
7 : 900 : 2, 3, 7, 23, 67, 199, 601
***
Simon wrote:
Tested all sets up to K=6, then continued the pattern and
just found the best next prime up to K=10 (Would be easy to continue
beyond that, knowing the next prime is somewhere around multiplying the
last prime by 3.)
K=2: T=3 set:{2, 3} Number of best sets: 1
K=3: T=10 set:{2, 3, 7} Number of best sets: 1
K=4: T=33 set:{2, 3, 7, 23} Number of best sets: 1
K=5: T=100 set:{2, 3, 7, 23, 67} Number of best sets: 1
K=6: T=299 set:{2, 3, 7, 23, 67, 199} Number of best
sets: 1
K=7: T=900 set:{2, 3, 7, 23, 67, 199, 601} (Probably the
best set, but not sure.)
K=8: T=2701 set:{2, 3, 7, 23, 67, 199, 601, 1801}
(Probably the best set, but not sure.)
K=9: T=8100 set:{2, 3, 7, 23, 67, 199, 601, 1801, 5399}
(Probably the best set, but not sure.)
K=10: T=24293 set:{2, 3, 7, 23, 67, 199, 601, 1801, 5399,
16193} (Probably the best set, but not sure.)
See attached file
for all 24293 formula for K=10
***
Michael wrote:
I have the following results:
T = 50: K = 5 {2, 3, 5, 19, 23}
T = 100: K = 5 {2, 3, 7, 23, 67}
T = 200: K = 6 {2, 3, 7, 23, 67, 101}
***
