Problems & Puzzles: Puzzles

Puzzle 222. Equations with consecutive primes

This week I started studying the following general equation:

p1* p2 * ... *pk = q1+q2+...+qk .............. (1)

where {p1,...pk} is a set of k consecutive primes and {q1,...qk} is another set of k consecutive primes.

The smallest example that I have found is this one:

For k=3: 29*31*37 = 11083+11087+11093

In order to save space I will report other solutions as a the following triad: (k, p1, q1). Accordingly the above example will be written as (3, 29, 11083).

Here are the earliest solution for each odd k value:

K p1 q1
3 29 11083
5 293 555136752211
7 229 7448535640735789
9 3119 3484361319642920210271255507593
11 67 216819892656221844131
13 18121 1808428663367515289053240288029870491511801302236142987

Question 1:  Find the earliest solution for K= 17, 19 & 21

Question 2: Find one solution for K even (if it exists)

A close equation to (1) is the following one:

p^k = q1+q2+...+qk ................ (2)

p is prime and {q1,...qk} is a set of k consecutive primes.

The smallest example is: (k, p, q1) = (5, 3, 41)

In this case my smallest results for each odd k are:

k p q1
3 11 439
5 3 41
7 241 6745610455578689
9 1741 16328505265216430302654575827
11 6569 89350954320781903650329652408736433449103
13 9011 198657750603940016519616647998134179968573622037967
15 1187 872307336818553421835903886542441308957300291

Question 3:  Find the earliest solution for K= 15, 17, 19 & 21

Question 4:  Find one solution for K even (if it exists)

 


Solution:

Solutions came from Jim Fougeron, John Wiesenbauer and J. K. Andersen

Fougeron wrote:

I am sure that I will submit this solution with lots of others :) since it is not too awfully hard of a problem.

For question #1, (first table), here are the next following values: (note 15 was not asked for, but since it was not listed, it is provided here)

k=15 p1=59629 q1=29078571394731776342443354126820734140155865170701085974267234571782657

k=17 p1=10247 q1=9785006399109340879013256874616886354795520907037650463250430001893

k=19 p1=15391 q1=2132759828550742498685066290824061285211489253263883046534515463344137569441423

k=21 p1=5903 q1=1125112337359143700021131708732871660802357010093542985845576342285073251235473

Question #2, you can never have an "even" k. Since any even number of odd numbers added together, is even, and since multiplying together odd values results in an odd result, you can have no solutions of k even.

Question #3.

First, take the k=15 result from the first table (it belongs in this table). Then the requested values are:

k=15 p=1187 q1=872307336818553421835903886542441308957300291 (from first table)

k=17 p=41281 q1=172704890172945321437762101508606961816215362152245353695589040010039040498183

k=19 p=15683 q1=2718943016343634293062289064163010275152091226696523505374718410927647426172583

k=21 p=8237 q1=810832393671441759255950351667063820703541393665016758906724001834735716368876839

Question #4, you can never have this happen (see my reply for question #2)

Some "additional" questions could be:

5. Will all k and K odd values > 3 provide at least 1 solution? 5a. How high can k (and K) be pushed "solidly" (i.e. no missing odd k's)? 6. What is the first k (of each form) which causes a titanic p1?

These are MUCH harder problems than the original 4 problems listed.

Wiesenbauer wrote:

Some results regarding puzzle 222 (using Derive 5 as always!)

Q1:

(15,59629,

29078571394731776342443354126820734140155865170701085974267234571782657)

(17,10247,

9785006399109340879013256874616886354795520907037650463250430001893)

(19,15391, 2132759828550742498685066290824061285211489253263883046534515463344137569441

423)

(21,5903, 1125112337359143700021131708732871660802357010093542985845576342285073251235

473)

(23,24007, 2642367271219280209932806149780912734847221137377333153803807214361244928264

753653400424464490138629)

(25,11783, 2963354656761811187866250150923444315061653714059570474662858934828410322305

7398662776857001628028993)

 

Q2: No solution for k<100 (p1 must be 2, of course!)

Q3:

(15,1187, 872307336818553421835903886542441308957300291)

(17, 41281, 1727048901729453214377621015086069618162153621522453536955890400100390404981

83)

(19, 15683, 2718943016343634293062289064163010275152091226696523505374718410927647426172

583)

(21, 8237, 8108323936714417592559503516670638207035413936650167589067240018347357163688

76839)

Andersen wrote:

Question 1: Find the earliest solution for K= 17, 19 & 21

p# is p primorial, i.e. the product of the primes<=p.
The minimal solutions with a primorial expression for q1 to save space:

K p1 q1
15 59629 (59771#/59627#-13)/15-1963 (71 digits)
17 10247 (10369#/10243#-16)/17-742 (67 digits)
19 15391 (15581#/15383#-18)/19-1906 (79 digits)
21 5903 (6113#/5897#-10)/21-2650 (79 digits)
23 24007 (24181#/24001#-15)/23-3267 (100 digits)
25 11783 (11971#/11779#-19)/25-2497 (101 digits)
27 39359 (39659#/39343#-14)/27-3458 (123 digits)
29 21013 (21283#/21011#-18)/29-4028 (124 digits)
31 104917 (105323#/104911#-4)/31-5068 (155 digits)
33 38273 (38651#/38261#-28)/33-4502 (150 digits)
35 61129 (61543#/61121#-18)/35-6004 (167 digits)
37 23663 (23993#/23633#-29)/37-6601 (161 digits)

A titanic solution for K=3:
N = (10^333+1460643) * (10^333+1461033) * (10^333+1461187)
= q1 + (q1+2960) + (q1+10350), where q1=(N-2)/3-4436


Question 2: Find one solution for K even (if it exists)

Assume K is even.
There are clearly no solutions with q1=2. This means that q1+...+qK is even and p1 must be 2 to give an even product. Exhaustive testing found no solution for K<252 and I stopped the search there.
For K=252, the prime product is 1601# with 677 digits. The average distance between 677-digit primes is around ln(10^677)~=1559 and we need the sum of 252 consecutive primes to be something specific. If these primes are "right-shifted" one place by replacing the smallest with the prime 252 places later then the sum is increased by an expected 252*1559=392868. We know the sum is even and it has to be, so the heuristics say the probability of a solution with the right sum is around 1 in 392868/2, or 1 in 196434. To try our luck we would have to compute 252 (or 251 with a minor improvement) prp's with 677 digits. Heuristics indicate any solution for even K is very unlikely.


Question 3: Find the earliest solution for K= 15, 17, 19 & 21

K p q1
15 1187 (1187^15-8)/15-458 (45 digits)
17 41281 (41281^17-5)/17-885 (78 digits)
19 15683 (15683^19-8)/19-1498 (79 digits)
21 8237 (8237^21-20)/21-1438 (81 digits)
23 4691 (4691^23-22)/23-2364 (84 digits)
25 45197 (45197^25-7)/25-3831 (115 digits)
27 16061 (16061^27-26)/27-3036 (113 digits)
29 21193 (21193^29-23)/29-4569 (124 digits)
31 197807 (197807^31-27)/31-4215 (163 digits)
33 81373 (81373^33-7)/33-6853 (161 digits)
35 46049 (46049^35-19)/35-4579 (162 digits)
37 17957 (17957^37-12)/37-5058 (156 digits)


Question 4: Find one solution for K even (if it exists)

Assume K is even.
It is easy to see there are no solutions with q1=2. Therefore q1+...+qK is even and p must be 2 to make p^K even. Exhaustive testing found no solution for K<=800 where I stopped the search.
A solution requires K primes around 2^K/K with the right sum. If we round 2^K/K up to 2^K then the average distance between primes is ln(2^K)=K*ln 2. Then approximately one of every K*(K*ln 2) numbers around 2^K is the sum of K consecutive primes. We know the sum is even and the desired sum is even so that doubles the chance. The heuristic probability of a given K being a solution is approximately 2*1/(K^2*ln 2) ~= 2.9/K^2.The sum of this for all natural K is 2.9*(pi^2)/6 = 4.8. However most of the sum comes from small K (over half from K=1) and the sum for even K>800 is only 0.0018. This is the total expected number of solutions, given the absence of solutions so far. Question 2 seems even worse but harder to give a good estimate for.


All solutions were found with a C program using the GMP library.
My strategy: Multiply the K primes starting at p1 and divide the product by K. For efficiency, sieve an interval around the quotient before prp-testing to find K surrounding probable primes and test whether they have the right sum. If the sum is wrong then increase p1 - or increase K if the goal is even K with p1=2.
Note potential solutions are discarded based on _probable_ primes with the wrong sum. If one of these prp's were really a composite then there could theoretically be a true prime giving the right sum instead. This means my solutions are not proven minimal with certainty.
However all primes in the probable minimal solutions above have been proved with Tony Forbes' VFYPR.
All primes in the titanic solution were proved with Marcel Martin's Primo.

***

Two days later Andersen added:

Question 3. A titanic solution for K=3:

N = (10^333+2703153)^3 = q1 + (q1+610) + (q1+6066), where q1=(N-1)/3-2225

All 4 primes were proved with Marcel Martin's Primo.

***

 

 



Records   |  Conjectures  |  Problems  |  Puzzles