Problems & Puzzles: Puzzles

Puzzle 356. A minimal set of K primes I will make a little twist to a nice puzzle ('100 numbers') published in a nice site of puzzles named 'Puzzleup': There is a set of K primes (p1, p2, ...pK; p1<p2< ...<pK ), such that all their pair wise sums are different. What is the minimum value of the largest prime in a set like that? Note: Pairwise sums include the sums of pairs formed by the same primes. Example for K=10. I got three solutions with the same largest prime (p10=101). This is one of these three solutions: {2,3,5,13,17,41,61,67,83,101} Questions: 1) Solve the question for K=20, 25 & 30. 2) Do you devise a function f(K) bounding pK.

---

Contribution came from Fred Schneider.

***

Fred wrote (April, 2006):

1) They most likely aren't minimal but they're the smallest values I have found:
K= 20, minmax P = 751
K=25, minmax P = 1409
K=30, minmax P = 2273

I found the following values for K=2 to 30. For K <=12, I believe the answers are minimal because I did an exhaustive search. I used a crude brute search method and as such could only search a miniscule fraction for K > 12.
Note: minmax P=89 for K=10.

K Set of primes
2 2 3
3 2 3 5
4 2 3 5 11
4 2 5 7 11
5 2 5 7 11 17
5 2 3 5 13 17
5 2 3 11 13 17
5 2 5 7 13 17
5 2 5 11 13 17
6 2 3 5 11 19 23
6 2 3 5 13 17 23
6 2 3 5 13 19 23
6 2 3 11 13 17 23
6 2 3 11 13 19 23
6 2 3 11 17 19 23
7 2 3 5 13 17 31 37
7 2 3 7 17 19 31 37
7 2 3 7 17 29 31 37
7 2 3 7 19 29 31 37
7 2 3 11 13 19 23 37
7 2 3 13 17 29 31 37
7 2 5 7 11 17 29 37
8 2 3 11 13 23 29 43 47
9 2 5 7 11 17 29 37 53 67
9 2 3 7 17 19 31 37 59 67
10 2 3 5 13 23 37 41 67 83 89
10 2 3 5 17 37 53 61 79 83 89
10 2 3 5 19 23 31 43 53 83 89
10 2 3 11 13 23 43 47 61 83 89
11 2 3 13 29 37 59 71 89 103 107 109
12 2 3 11 13 23 37 67 71 103 109 131 149
13 2 3 5 11 19 29 67 71 107 157 179 191 211
14 2 3 5 11 19 29 47 89 127 167 179 199 229 233
15 2 3 5 11 19 23 41 73 83 127 167 193 241 269 293
16 2 3 5 11 19 23 41 67 101 151 179 251 283 293 409 463
17 2 3 5 11 19 23 41 67 101 151 179 251 283 293 359 479 547
18 2 3 5 11 19 23 41 67 101 151 179 251 283 359 479 547 571 613
19 2 3 5 11 19 23 41 67 101 151 179 251 283 293 401 487 607 631 677
19 2 3 5 11 19 23 41 67 101 151 179 251 283 293 409 463 607 653 677
20 2 3 5 11 19 23 41 67 101 151 179 251 283 409 463 607 617 659 683 751
21 2 3 5 11 19 23 41 67 101 151 179 251 283 409 463 503 571 617 769 821 887
21 2 3 5 11 19 23 41 67 101 151 179 251 293 373 499 569 593 757 811 877 887
22 2 3 5 11 19 23 41 67 101 151 179 251 283 353 461 547 587 661 823 911 953 977
22 2 3 5 11 19 23 41 67 101 151 179 251 283 359 461 503 577 647 773 853 967 977
23 2 3 5 11 19 23 41 67 101 151 179 251 283 353 479 547 571 701 853 863 971 1087 1129
24 2 3 5 11 19 23 41 67 101 151 179 251 283 353 461 547 673 683 797 863 1063 1087 1181 1249
25 2 3 5 11 19 23 41 67 101 151 179 251 283 409 463 607 677 797 877 991 1049 1213 1301 1367 1409
26 2 3 5 11 19 23 41 67 101 151 179 251 283 337 463 557 677 757 929 1051 1249 1259 1301 1453 1493 1559
27 2 3 5 11 19 23 41 67 101 151 179 251 283 293 409 479 613 659 733 857 1009 1217 1361 1531 1597 1733 1787
27 2 3 5 11 19 23 41 67 101 151 179 251 283 337 461 563 587 751 887 1009 1181 1381 1543 1583 1657 1777 1787
28 2 3 5 11 19 23 41 67 101 151 179 251 283 293 409 479 631 733 853 983 1163 1249 1367 1447 1571 1759 1867 1973
28 2 3 5 11 19 23 41 67 101 151 179 251 283 337 463 571 659 829 853 1019 1153 1223 1429 1559 1759 1811 1931 1973
28 2 3 5 11 19 23 41 67 101 151 179 251 283 337 463 587 739 853 941 1061 1231 1367 1489 1531 1597 1831 1871 1973
29 2 3 5 11 19 23 41 67 101 151 179 251 283 337 463 571 677 829 953 1087 1259 1283 1447 1489 1667 1783 2039 2131 2141
30 2 3 5 11 19 23 41 67 101 151 179 251 283 337 463 593 659 811 983 1063 1171 1289 1487 1609 1823 1987 2029 2153 2221 2273
=================================================
2) A crude upper bound for K would be MinMaxP(k)= the prime after
(MinMaxP(k-1) + MinMaxP(k-2))

For MinMaxP(k+1), there would be no pair less than any pair including
MinMaxP(k) so we could construct a disjoint set that way.

For a much better estimate, note the table below, where percentage = (K-1)(K-2)/(2*(MinMaxPk-1)), meaning it equals the number of odd prime pairs / (the number of even numbers < MinMaxPk) or the density of prime pairs.
If this quotient = 1/R, we have MinMaxPk = R(K-1)(K-2)/2+1. It seems reasonable that for any K, we could find a sequence ending in MinMaxPk such that the percentage > 5%, so upper bound would be MinMaxPk = 10(K-1)(K-2)+1.


K MinMaxPk Percentage
4 11 30.00%
5 17 37.50%
6 23 45.45%
7 37 41.67%
8 47 45.65%
9 67 42.42%
10 89 40.91%
11 113 40.18%
12 149 37.16%
13 211 31.43%
14 233 33.62%
15 293 31.16%
16 463 22.73%
17 547 21.98%
18 613 22.22%
19 677 22.63%
20 751 22.80%
21 887 21.44%
22 977 21.52%
23 1129 20.48%
24 1249 20.27%
25 1409 19.60%
26 1559 19.26%
27 1787 18.20%
28 1973 17.80%
29 2141 17.66%
30 2273 17.87%
 

***

 

---