 |
|
| Science Forum Index » Mathematics Forum » sum n consecutive primes... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| jm bergot... |
 Posted: Sun Oct 25, 2009 11:14 am |
|
|
|
Guest
|
Given the question about the first sum of ten consecutive
primes having a total that is a number with ten square-free factors, one can see that this would take a bit of
time for a computer to solve. Any guesses? What about more than ten consecutive primes? |
|
|
| Back to top |
|
|
|
| christian.bau... |
| Posted: Sun Oct 25, 2009 12:51 pm |
|
|
|
Guest
|
On Oct 25, 9:14 pm, jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
[quote]Given the question about the first sum of ten consecutive
primes having a total that is a number with ten square-free factors, one can see that this would take a bit of
time for a computer to solve. Any guesses? What about more than ten consecutive primes?
[/quote]
I don't think that is too difficult.
First, unless the sequence of primes starts with two, the primes are
all odd so the sum of ten of those is even.
The first few thousand products of ten distinct primes with the first
one being "2" should be reasonably easy to find.
There are probably a few thousand such products less than 10^15.
Let p (n) be the n-th prime, and f (n) the sum of ten consecutive
primes starting with the p (n). f (n+1) = f (n) + p (n+10) - p (n), so
the growth in f (n) is about ten times the gap between consecutive
primes or roughly 10 ln n. For sums up to 10^15 and therefore primes
up to 10^14 that growth is roughly 10*33 = 330; since the sum is
always even the chance that f (n) = x for some even x <= 10^15 is
about 2 / 330 = 1 / 165.
So for each of those few thousand products x of ten primes, I create a
small sieve to find primes say from x/10 - 1000 to x/10 + 1000 (time
should be roughly sqrt (p/10) and check if f (n) "hits" the value x
exactly. Shouldn't take more than a few hundred attempts.
For more than 10 consecutive primes this is just as easy, except that
the sum of k consecutive primes is odd when k is odd and therefore the
product of distinct primes must _not_ contain the number 2. |
|
|
| Back to top |
|
|
|
| christian.bau... |
| Posted: Sun Oct 25, 2009 2:38 pm |
|
|
|
Guest
|
A rather inefficient program found this in a fraction of a second:
Prime #1 = 1490842261
Prime #2 = 1490842271
Prime #3 = 1490842321
Prime #4 = 1490842337
Prime #5 = 1490842343
Prime #6 = 1490842349
Prime #7 = 1490842363
Prime #8 = 1490842399
Prime #9 = 1490842433
Prime #10 = 1490842453
Sum = 14908423530 = 2*3*5*7*11*13*17*19*29*53
The sum equals the 27th-smallest product of ten distinct primes. |
|
|
| Back to top |
|
|
|
| jm bergot... |
| Posted: Mon Oct 26, 2009 7:22 am |
|
|
|
Guest
|
Gobs of thanXXX to gnasher729. A further wonder is if
there are gnashers from 1 to 728.
A further puzzle arises: Can there be ten consecutive
primes as factors in the sum of ten consecutive primes?
The example you gratefully gave has eight consecutive
primes in the sum of the 27th least sum of ten consecutive primes. For one armed with a NEC SX-7
and a desire to send a sequence into OEIS, one could
pursue this in order. Find the first sum of n consecutive primes such that this sum has n consecutive
primes as factors; of course it could have a total of
more than n factors. but these n must be consecutive. |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Mon Oct 26, 2009 4:11 pm |
|
|
|
Guest
|
In article
<1003083240.115974.1256577768610.JavaMail.root at (no spam) gallium.mathforum.org>,
jm bergot <thekingfishb at (no spam) yahoo.ca> wrote:
[quote]Gobs of thanXXX to gnasher729. A further wonder is if
there are gnashers from 1 to 728.
A further puzzle arises: Can there be ten consecutive
primes as factors in the sum of ten consecutive primes?
The example you gratefully gave has eight consecutive
primes in the sum of the 27th least sum of ten consecutive primes. For one
armed with a NEC SX-7
and a desire to send a sequence into OEIS, one could
pursue this in order. Find the first sum of n consecutive primes such that
this sum has n consecutive
primes as factors; of course it could have a total of
more than n factors. but these n must be consecutive.
[/quote]
I'll get you started:
For n = 1, the answer is 2.
For n = 2, the answer is 12 = 5 + 7 = 2 x 2 x 3
(if you don't like repeated factors, 30 = 13 + 17 = 2 x 3 x 5).
--
Gerry Myerson (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
| jm bergot... |
| Posted: Tue Oct 27, 2009 6:27 am |
|
|
|
Guest
|
It appears that contributors are few who own a
NEC SX-7 to pursue this for n consecutive primes
when n is greater than ten. For the sum of ten
consecutive primes to be a number with ten
consecutive prime factors (among others)--this
solution would take a peppy flock of electrons.
The execution time to find the solution for n=20
would merely contribute to global warming. |
|
|
| Back to top |
|
|
|
| Mensanator... |
| Posted: Tue Oct 27, 2009 7:01 am |
|
|
|
Guest
|
On Oct 26, 5:11 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email>
wrote:
[quote]In article
1003083240.115974.1256577768610.JavaMail.r... at (no spam) gallium.mathforum.org>,
jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
Gobs of thanXXX to gnasher729. A further wonder is if
there are gnashers from 1 to 728.
A further puzzle arises: Can there be ten consecutive
primes as factors in the sum of ten consecutive primes?
The example you gratefully gave has eight consecutive
primes in the sum of the 27th least sum of ten consecutive primes. For one
armed with a NEC SX-7
and a desire to send a sequence into OEIS, one could
pursue this in order. Find the first sum of n consecutive primes such that
this sum has n consecutive
primes as factors; of course it could have a total of
more than n factors. but these n must be consecutive.
I'll get you started:
For n = 1, the answer is 2.
For n = 2, the answer is 12 = 5 + 7 = 2 x 2 x 3
(if you don't like repeated factors,
[/quote]
Isn't that what "squarefree" means?
[quote]30 = 13 + 17 = 2 x 3 x 5).
--
Gerry Myerson (ge... at (no spam) maths.mq.edi.ai) (i -> u for email)[/quote] |
|
|
| Back to top |
|
|
|
| jm bergot... |
| Posted: Tue Oct 27, 2009 9:04 am |
|
|
|
Guest
|
I think the "fog has rolled in" with this task.
The world will never see the answer for 20
consecutive primes having a sum that
contains 20 square-free consecutive primes. An
example would be some sum having these factors
2*5*7*11*13...(each of the first 20 consecutive primes
starting at 5)...149^5 * 211*2 and as many others as
will be found. |
|
|
| Back to top |
|
|
|
| Jim Ferry... |
| Posted: Tue Oct 27, 2009 12:27 pm |
|
|
|
Guest
|
On Oct 27, 3:04 pm, jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
[quote]I think the "fog has rolled in" with this task.
The world will never see the answer for 20
consecutive primes having a sum that
contains 20 square-free consecutive primes. An
example would be some sum having these factors
2*5*7*11*13...(each of the first 20 consecutive primes
starting at 5)...149^5 * 211*2 and as many others as
will be found.
[/quote]
The 20 consecutive primes
59160358954618231593590000 + {7373, 7403, 7451,
7487, 7493, 7563, 7649, 7667, 7731, 7761, 7763,
7817, 7911, 8037, 8039, 8097, 8127, 8247, 8313,
8361}
sum to the product of the 20 primes
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 61, 71, 83, 101}.
The 30 consecutive primes
3987616574498184374914720877696312744176750000 +
{759, 763, 1117, 1293, 1513, 1561, 1711, 1717, 1879,
1893, 1897, 2079, 2139, 2179, 2217, 2349, 2571, 2649,
2713, 2737, 2763, 2913, 3217, 3223, 3279, 3321, 3531,
3553, 3847, 3987}
sum to the product of the 30 primes
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 71, 73, 79, 83, 97, 103, 107, 109,
113, 127, 131, 137} |
|
|
| Back to top |
|
|
|
| Mensanator... |
| Posted: Tue Oct 27, 2009 2:39 pm |
|
|
|
Guest
|
On Oct 27, 4:31 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email>
wrote:
[quote]In article
27b54280-1cdc-49c2-b030-58d2c09f3... at (no spam) v25g2000yqk.googlegroups.com>,
Mensanator <mensana... at (no spam) aol.com> wrote:
On Oct 26, 5:11 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email
wrote:
In article
1003083240.115974.1256577768610.JavaMail.r... at (no spam) gallium.mathforum.org>,
jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
Gobs of thanXXX to gnasher729. A further wonder is if there are
gnashers from 1 to 728. A further puzzle arises: Can there be
ten consecutive primes as factors in the sum of ten consecutive
primes? The example you gratefully gave has eight consecutive
primes in the sum of the 27th least sum of ten consecutive
primes. For one armed with a NEC SX-7 and a desire to send a
sequence into OEIS, one could pursue this in order. Find the
first sum of n consecutive primes such that this sum has n
consecutive primes as factors; of course it could have a total of
more than n factors. but these n must be consecutive.
I'll get you started:
For n = 1, the answer is 2.
For n = 2, the answer is 12 = 5 + 7 = 2 x 2 x 3
(if you don't like repeated factors,
Isn't that what "squarefree" means?
Yes, though I confess that I don't see the relevance of your question,
[/quote]
The OP originally asked "having a total that is a number with ten
square-free factors".
[quote]as the question to which I responded didn't use that word.
[/quote]
Sorry, didn't notice that the question you replied to was also from
the OP.
[quote]
30 = 13 + 17 = 2 x 3 x 5).
--
Gerry Myerson (ge... at (no spam) maths.mq.edi.ai) (i -> u for email)[/quote] |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Tue Oct 27, 2009 3:31 pm |
|
|
|
Guest
|
In article
<27b54280-1cdc-49c2-b030-58d2c09f32a4 at (no spam) v25g2000yqk.googlegroups.com>,
Mensanator <mensanator at (no spam) aol.com> wrote:
[quote]On Oct 26, 5:11 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email
wrote:
In article
1003083240.115974.1256577768610.JavaMail.r... at (no spam) gallium.mathforum.org>,
jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
Gobs of thanXXX to gnasher729. A further wonder is if there are
gnashers from 1 to 728. A further puzzle arises: Can there be
ten consecutive primes as factors in the sum of ten consecutive
primes? The example you gratefully gave has eight consecutive
primes in the sum of the 27th least sum of ten consecutive
primes. For one armed with a NEC SX-7 and a desire to send a
sequence into OEIS, one could pursue this in order. Find the
first sum of n consecutive primes such that this sum has n
consecutive primes as factors; of course it could have a total of
more than n factors. but these n must be consecutive.
I'll get you started:
For n = 1, the answer is 2.
For n = 2, the answer is 12 = 5 + 7 = 2 x 2 x 3
(if you don't like repeated factors,
Isn't that what "squarefree" means?
[/quote]
Yes, though I confess that I don't see the relevance of your question,
as the question to which I responded didn't use that word.
[quote]30 = 13 + 17 = 2 x 3 x 5).
[/quote]
--
Gerry Myerson (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
| jm bergot... |
| Posted: Wed Oct 28, 2009 9:33 am |
|
|
|
Guest
|
I believe Jim FERRY has a secret NEC SX-7 in his
garage, basement, or attic. What was the length of
the execution time to find the one with 30 consecutive
prime factors?
If his supercomputer is hungry for exercise, I could
give the electrons little yummies. |
|
|
| Back to top |
|
|
|
| Jim Ferry... |
| Posted: Wed Oct 28, 2009 12:02 pm |
|
|
|
Guest
|
On Oct 28, 3:33 pm, jm bergot <thekingfi... at (no spam) yahoo.ca> wrote:
[quote]I believe Jim FERRY has a secret NEC SX-7 in his
garage, basement, or attic. What was the length of
the execution time to find the one with 30 consecutive
prime factors?
If his supercomputer is hungry for exercise, I could
give the electrons little yummies.
[/quote]
No, just a laptop -- not a petaflop roadrunner.
Although this may be Christian Bau's version of
the question rather than the OP's, I've computed
the first several values of a function a(n)
defined as follows.
For positive integers n, a(n) is the smallest
prime p such that the sum of the n consecutive
primes beginning with p equals the product of
n distinct primes.
a(2) is undefined. Let's set it to infinity.
The following table gives (n, ind(n), a(n)),
where ind(n) is the number of products of
n primes tested. As Christian Bau suggested,
the algorithm works by first testing if there
is a solution for the smallest product of n
primes, then testing the second smallest such
product, etc., with the caveat that the parity
of the products tested must equal the parity
of n for n > 2.
Here are the first 47 values of a(n):
n ind(n) a(n)
----------------
1 1 2
2 infty infty
3 45 331
4 3 89
5 6 5297
6 8 11149
7 76 2960267
8 114 6189857
9 210 1645492081
10 27 1490842261
11 49 763377367829
12 97 1692363920551
13 203 1428615512790811
14 1122 4401056418164533
15 184 2690463974722206427
16 180 5028108033082285561
17 505 9398423714051661403759
18 242 15054255844981354512899
19 1247 42790982903120007314853547
20 277 59160358954618231593597373
21 222 150858357480821001471438748571
22 201 283091413746739793317919709137
23 634 1166922172297427709990493565352661
24 671 2256927676431324343328093768969213
25 419 8738879741094170622541702004279713633
26 69 12974373730511999083618081197640795577
27 1529 106103368476660382198247571954116634516307
28 679 179850028454933065488567961867239129366401
29 47 798981963626223430868752284905104291343232281
30 1601 2455806834048298871744887660790424917495080471
31 4228 21006121744828913542916570957975218679397809287511
32 648 30893853089907985332328311937181734711399398789377
33 1244 296030023348153128803274895108440569404307009702382451
34 182 453193787553064803888721265655136140662855197942652209
35 69 4290131558735970179348562484554096464289203960650305527557
36 1455
11683138211412229145489656403730689890282129740149150950153
37 674
126963802421682899316427461561475825720633430801737897241877173
38 5396
319048742551950592504388504559264986580295964868467448164034943
39 910
3499658569890580528064229783367121987965476528855280390620750200489
40 5566
8433720182032629480337296645110891460626605533772871481814008171749
41 477
99535964375489572166123969812213740607437230804294832569722371509129783
42 214
180542258406729608566013588049558064218097212160887569398222050292782973
43 1015
3664391463558735272402068418292721142115140467161517066082363254964348015491
44 5852
8629280419240528847557238535977249268605856125793246538157513718190189147853
45 1004
140400230015638249863563081880253060777207063001404823085005404356453610323501091
46 7356
337053843588856436374245884578435294025442552974424159686334316122272724653818913
47 31954
8638198430096265919110963746158491676075029612669076296346745618299147984335667878517
The n=30 case took about 3 minutes.
The whole table took about 12 hours, with the
n=47 case responsible for at least half of this.
The Mathematica code is below. It relies on
Mathematica's probabilistic primality testing.
The final sequence of consecutive primes is
checked to comprise provable primes, but the
rest of the code trusts the probabilistic
testing.
<< PrimalityProving`
(* a[n] returns {ind,p} where p is the smallest prime such that the n
consecutive primes beginning with p sum to a product of distinct
primes and ind is the the number of products of distinct primes that
needed to be tested *)
a[1] = {1, 2};
a[2] = {Infinity, Infinity};
a[n_] := a[n] = Module[{imin = 1, imax = 10, v = {}, plist},
While[Length[v] == 0, v = search[n, imin, imax]; imin = imax + 1;
imax *= 10];
plist = NestList[NextPrime, v[[2]], n - 1];
If[And at (no spam) at (no spam) ProvablePrimeQ / at (no spam) plist, v,
Prepend[v, "What? PrimeQ failed!"]]
];
(* f[n] returns the list of distinct primes associated with a[n] *)
f[n_] := FactorInteger[
Plus at (no spam) at (no spam) NestList[NextPrime, a[n][[2]], n - 1]][[All, 1]];
(* Searches for n consecutive primes which sum to a product of n
distinct primes starting with the imin^th smallest product of n
distinct primes and ending with the imax^th. *)
search[n_, imin_, imax_] : Module[{clist = makeCandidates[n, imax, EvenQ[n]], inds},
inds = Select[Range[imin, imax], validQ[clist[[#]], n][[1]] &, 1];
If[Length[inds] == 0, {}, {inds[[1]],
validQ[clist[[inds[[1]]]], n][[2, 1]]}]
];
(* Returns a list of the first r even or odd products of n distinct
primes
depending on evenQ *)
makeCandidates[n_, r_, evenQ_] : If[evenQ, 2 mcOdd[n - 1, r], mcOdd[n, r]];
mcOdd[n_, r_] := Module[{x = Product[Prime[j], {j, 2, n + 1}], list},
While[Length[list = prods[n, x = Ceiling[1.5 x], 3]] < r];
Take[list, r]
];
(* Generate all products less than or equal to x of n distinct odd
primes
which are at least k *)
prods[n_, x_, k_] := If[x < Times at (no spam) at (no spam) NestList[NextPrime, k, n - 1],
{},
Sort[Join[k prods[n - 1, Floor[x/k], NextPrime[k]],
prods[n, x, NextPrime[k]]]]];
prods[1, x_, k_] : Select[Range[2 Ceiling[(k - 1)/2] + 1, x, 2], PrimeQ];
(* Returns a list of n consecutive primes with sum approximately v *)
makeChain[v_, n_] : Rest[NestList[NextPrime, Floor[v/n - n Log[v/n]/2], n]];
iterChain[ch_, dir_] : If[dir > 0, Append[Rest[ch], NextPrime[Last[ch]]],
If[dir < 0, Prepend[Drop[ch, -1], -NextPrime[-First[ch]]], ch]];
validQ[v_, n_] := Module[{ch = makeChain[v, n], dir, dirOld},
dir = Sign[v - Plus at (no spam) at (no spam) ch];
While[ch = iterChain[ch, dir]; dirOld = dir;
dir = Sign[v - Plus at (no spam) at (no spam) ch]; dir*dirOld > 0];
{dir == 0, ch}
]; |
|
|
| Back to top |
|
|
|
| christian.bau... |
| Posted: Wed Oct 28, 2009 2:10 pm |
|
|
|
Guest
|
Related problem: For n >= 3, is it possible to find a number X (n)
that is both the sum and the product of n consecutive primes? For odd
n it should be not much harder to find (a bit harder because the
numbers involved are bigger). For even n, X (n) would have to be the
product of the _first_ n primes; so ind (n) = 1 in your solution. It
seems possible, but not very likely that a solution exists.
Playing a bit with heuristics:
Sum of 20 consecutive primes = product of 20 consecutive primes and
other primes -> easy to find.
Sum of 20 consecutive primes = product of 20 consecutive primes and
one more prime -> easy to find.
Sum of 20 consecutive primes = product of 20 first primes and one more
prime -> easy to find.
Sum of 20 consecutive primes = product of 20 or more consecutive
primes -> solutions are awfully hard to find. |
|
|
| Back to top |
|
|
|
| jm bergot... |
| Posted: Thu Oct 29, 2009 9:09 am |
|
|
|
Guest
|
What a stupendous amount of computational derring-do
by "sizzlin' laptop" Ferry! All this should be perhaps
passed on to OEIS?
It is fortunate that I did not refer to two items at
primepuzzles.net which have ONLY two solutions listed.
It is equally fortunate that I did not suggest extending
A154598 at OEIS.
ThanXXX again to the vigorous electrons in Ferry's
sizlin' laptop. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Dec 14, 2009 8:50 pm
|
|