Problems & Puzzles: Collection 20th

Coll.20th-002. 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 = 3-2
2
3
4= 17-13
5 = 2+3
6= 17-13+2
7= 17-13+3
8= 13-3-2
9= 2+3+17-13
10= 13-3
11= 13-2
12= 13-3+2
13
14= 13+3-2
17
18= 17+3-2
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}

***

 


Records   |  Conjectures  |  Problems  |  Puzzles