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.
***
|