Problems & Puzzles: Puzzles

 Puzzle 703 Dividing a set of primes in other two Here you asked to divide the set A of primes from 2 to P in two sets, B & C.The set B contains two distinct primes of the set A, let's say Q & R. The set C is the same than the set A minus the primes in B Such that the product of the primes in B is equal to the sum of primes in C Example: If P=71 then Q=19 and R=31. The sum of the primes in A is equal to 639. 639-19-31=589=19*31 Sometimes for the same prime P you can find several pairs Q & R. Example1: If P=1231 there are 3 pairs Q & R: 131 & 863, 191 & 593, 263 & 431 Example 2: If P=44887, there are five pairs Q & R: 2437,40499, etc., etc. Q1. Find the least P such that there are k pairs Q & R satisfying the rules, for k=1, 2, 3, ... Q2. Is there a prime P such that Q & R are consecutive primes?

Contributions came from Vicente Felipe Izquierdo, Emmanuel Vantieghem, Hakan Summakoglu, Giovanni Resta & Fred Schneider.

***

Vicente wrote:

Q1: Checking up
the prime(800.000) = 12.195.257, I found the following:
K, Prime, Pairs (Q&R).
== ===== ========
1, 7, (2,5)
2, 1423,(149,953),(317,449)
3, 1231,(131,863),(191,593),(263,431)
4, 53617,{4159,33211},{4783,28879},{6991,19759},{11551,11959}
5, 44887,{2437,40499},{2861,34499},{3449,28619},{4049,24379},{7451,13249}
6, 234547,{16811,137999},{18679,124199},{21481,107999},{28019,82799},{34499,67247},{41399,56039}
7, 637321,{26459,597131},{27701,570359},{52379,301643},{61559,256661},{73331,215459},{86183,183329},{110807,142589}
8, 996169,{57287,650623},{59023,631487},{62743,594047},{68447,544543},{76543,486947},{111103,335477},{120427,309503},{169693,219647}
9, 1942411,{74797,1806479},{75269,1795151},{78311,1725419},{90359,1495363},{138959,972373},{172541,783119},{174329,775087},{180647,747979},{290657,464879}
10, ?
11, ?
12, ?
13, ?
14, 4961371,{197539,4181183},{202519,4078367},{223103,3702089},{228479,3614981},{248879,3318671},{278879,2961671},{317321,2602879},{324031,2548979},{383791,2152079},{398207,2074169},{508129,1625471},{582623,1417639},{711143,1161439},{799679,1032851}

***

Emmanuel wrote:

This is what I could find about puzzle 703

Q1.

Table :

n    Smallest  P
1           7
2        1423
3        1231
4        53617
5        44887
6       234547
7       637321
8       996169
9      1942411
For  n = 10, P will be bigger than 2736011.

Q2. I found no solution for  P < 10000000.

***

Hakan wrote:

Q1:
k=1:P=7 Q&R:2 & 5
k=2:P=1231 Q&R:131 & 863 , 191 & 593
k=3:P=1231 Q&R:131 & 863 , 191 & 593 , 263 & 431
k=4:P=44887 Q&R:2437 & 40499 , 2861 & 34499 , 3449 & 28619 , 4049 & 24379
k=5:P=44887 Q&R:2437 & 40499 , 2861 & 34499 , 3449 & 28619 , 4049 & 24379 , 7451 & 13249
k=6:P=234547 Q&R:16811 & 137999 , 18679 & 124199 , 21481 & 107999 , 28019 & 82799 , 34499 & 67247 , 41399 & 56039
k=7:P=637321 Q&R:26459 & 597131 , 27701 & 570359 , 52379 & 301643 , 61559 & 256661 , 73331 & 215459 , 86183 & 183329 , 110807 & 142589
k=8:P=996169 Q&R:57287 & 650623 , 59023 & 631487 , 62743 & 594047 , 68447 & 544543 , 76543 & 486947 , 111103 & 335477 , 120427 & 309503 , 169693 & 219647
k=9:P=1942411 Q&R:74797 & 1806479 , 75269 & 1795151 , 78311 & 1725419 , 90359 & 1495363 , 138959 & 972373 , 172541 & 783119 , 174329 & 775087 , 180647 & 747979 , 290657 & 464879 ,
k=10:P=4961371 Q&R:197539 & 4181183 , 202519 & 4078367 , 223103 & 3702089 , 228479 & 3614981 , 248879 & 3318671 , 278879 & 2961671 , 317321 & 2602879 , 324031 & 2548979 , 383791 & 2152079 , 398207 & 2074169
k=11:P=4961371 Q&R:197539 & 4181183 , 202519 & 4078367 , 223103 & 3702089 , 228479 & 3614981 , 248879 & 3318671 , 278879 & 2961671 , 317321 & 2602879 , 324031 & 2548979 , 383791 & 2152079 , 398207 & 2074169 , 508129 & 1625471
k=12:P=4961371 Q&R:197539 & 4181183 , 202519 & 4078367 , 223103 & 3702089 , 228479 & 3614981 , 248879 & 3318671 , 278879 & 2961671 , 317321 & 2602879 , 324031 & 2548979 , 383791 & 2152079 , 398207 & 2074169 , 508129 & 1625471 ,582623 & 1417639 ,
k=13:P=4961371 Q&R:197539 & 4181183 , 202519 & 4078367 , 223103 & 3702089 , 228479 & 3614981 , 248879 & 3318671 , 278879 & 2961671 , 317321 & 2602879 , 324031 & 2548979 , 383791 & 2152079 , 398207 & 2074169 , 508129 & 1625471 ,582623 & 1417639 , 711143 & 1161439
k=14:P=4961371 Q&R:197539 & 4181183 , 202519 & 4078367 , 223103 & 3702089 , 228479 & 3614981 , 248879 & 3318671 , 278879 & 2961671 , 317321 & 2602879 , 324031 & 2548979 , 383791 & 2152079 , 398207 & 2074169 , 508129 & 1625471 ,582623 & 1417639 , 711143 & 1161439 , 799679 & 1032851

***

Giovanni wrote:

I have checked primes up to prime(10^7) = 179424673.
The smallest P with exactly k pairs that I found are:

k P sum
0 5 10
1 7 17
2 1423 143099
3 1231 114047
4 53617 138161919
5 44887 98738999
6 234547 2320055999
7 637321 15800112719
8 996169 37272947711
9 1942411 135121091039
10 17672453 9656348276735
11 39096289 45042399939599
12 32329777 31150382131439
13 24116129 17639490959999
14 4961371 825951087359
15 78954349 176382098323199
16 118339799 387385553154599
17 86455613 210410390211839
18 22121447 14921700767999
20 145739701 580844307067199

For the last value the 20 pairs are
{4556627, 127472399}, {4955039, 117222929}, {5242967, 110785399},
{5934059, 97883119}, {6056159, 95909669}, {6834941, 84981599},
{7553549, 76896863}, {7814861, 74325599}, {7983119, 72759059},
{9701207, 59873399}, {11367071, 51098849}, {11651039, 49853429},
{12816143, 45321299}, {13294247, 43691399}, {13473899, 43108847},
{15966239, 36379529}, {16315667, 35600399}, {18945119, 30659309},
{22710599, 25575911}, {22783139, 25494479}.

for Q2, I've searched for P < 3.9*10^12 without success.

***

Fred wrote,[a very elegant approach, CR]:

B(n) is the sum of the first n primes
C(n) is B(n) with two primes Q and R removed such that: p(1) <= Q < R <= p(n)

S(n) = sum of primes in B(n)
S(n)' = sum of primes in C(n)

We are looking for
S(n) - Q - R = S(n)' = Q * R

"n" subscript omitted now for brevity

S - Q -R = Q * R

Rearranging the terms we have:
(S + 1) = (Q + 1) * (R +1)

So, instead of just doing trial division of large number primes,
we can instead factorize S + 1 and check the divisors.
If there are sufficient divisors (I was using 240 after p(n) > 10^6),
test Q and R for primality where Q and R could be legal solutions to the problem.

Solution set size: 1: 71 (sum=639)
19 and 31

Solution set size: 2-3: 1231 (sum=114047):
131 and 863, 191 and 593, 263 and 431

Solution set size: 4-5: 44887 (sum=98738999):
2437 and 40499, 2861 and 34499, 3449 and 28619,
4049 and 24379, 7451 and 13249

Solution set size: 6: 234547 (sum=2320055999)
21481 and 107999, 41399 and 56039, 28019 and 82799,
18679 and 124199, 34499 and 67247, 16811 and 137999

Solution set size: 7: 637321 (sum=15800112719)
26459 and 597131, 27701 and 570359, 110807 and 142589,
61559 and 256661, 86183 and 183329, 73331 and 215459,
52379 and 301643

Solution set size: 8: 996169 (sum=37272947711)
169693 and 219647,  62743 and 594047,  68447 and 544543,
76543 and 486947,  59023 and 631487, 120427 and 309503,
57287 and 650623, 111103 and 335477

Solution set size: 9: 1942411 (sum=135121091039)
290657 and 464879, 174329 and 775087, 138959 and 972373,
180647 and 747979, 75269 and 1795151, 74797 and 1806479,
172541 and 783119, 78311 and 1725419, 90359 and 1495363

Solution set size: 10-14: 4961371 (sum=825951087359)
228479 and 3614981, 799679 and 1032851, 582623 and 1417639,
202519 and 4078367, 324031 and 2548979, 383791 and 2152079,
398207 and 2074169, 248879 and 3318671, 197539 and 4181183,
711143 and 1161439, 508129 and 1625471, 317321 and 2602879,
278879 and 2961671, 223103 and 3702089

Solution set size: 15-18: 22121447 (sum=14921700767999)
954719 and 15629399, 3818879 and  3907349, 1988999 and  7502111,
2983499 and  5001407, 1111423 and 13425749, 2051999 and  7271783,
3001049 and  4972159, 1481999 and 10068623,  839051 and 17783999,
760447 and 19622249, 3084749 and  4837247,  680237 and 21935999,
913999 and 16325711, 1233899 and 12093119, 2193599 and  6802379,
1462399 and 10203569, 1679599 and  8884079, 2221019 and  6718399

Solution set size: 19-20: 145739701 (sum=580844307067199)
5242967 and 110785399, 11651039 and  49853429, 13294247 and 43691399,2816143 and  45321299,  7553549 and  76896863, 16315667 and 35600399, 5934059 and  97883119, 22783139 and  25494479,  6834941 and 84981599, 4556627 and 127472399,  4955039 and 117222929,  7814861 and 74325599, 6056159 and  95909669, 18945119 and  30659309, 22710599 and 25575911, 11367071 and  51098849, 13473899 and  43108847,  7983119 and 72759059, 15966239 and  36379529,  9701207 and  59873399

***

 Records   |  Conjectures  |  Problems  |  Puzzles