mersenneforum.org > Math Primes in millennia
 Register FAQ Search Today's Posts Mark Forums Read

 2009-03-04, 19:41 #12 mart_r     Dec 2008 you know...around... 2·73 Posts Oh it's not my CPU time. I torture the computer at my workplace with that :)
2009-03-04, 22:44   #13
Jens K Andersen

Feb 2006
Denmark

111001102 Posts

Quote:
 Originally Posted by mart_r Another thing I'd like to share is "primes in a quadratic pattern", i.e. p ± n*(n+1) for a run of n's (say up to 12 or 13, starting from 0). I've searched p+n(n+1) to 37*10^12 some time ago and am now with p-n(n+1), currently at ~ 4*10^12. Strangely, the OEIS only lists a sequence for n=0...6, and nothing else. That would require me to send about 18 separate sequences. I was thus thinking about a single sequence for each p+ and p-, listing ten (or more) terms successively for each n.
Making a sequence which lists the first ten (or more) terms in each of a number of different sequences sounds like an ugly arbitrary combination to me. I would prefer A092749, a similar sequence with the smallest term for each exact length (as opposed to at least that length in A092749), and maybe separate sequences for each fixed length.

I guess you know Euler found that 41+n*(n+1) is prime for n = 0..39.
Jörg Waldvogel and Peter Leikauf found in http://www.sam.math.ethz.ch/~waldvog...clprimes05.pdf that the next occurrence of at least 21 primes is
234505015943235329417+n*(n+1) for n = 0..20.
I suspect you have an inefficient program.

2009-03-05, 19:45   #14
mart_r

Dec 2008
you know...around...

2×73 Posts

Quote:
 Originally Posted by Jens K Andersen Making a sequence which lists the first ten (or more) terms in each of a number of different sequences sounds like an ugly arbitrary combination to me.
I just came across the idea when I saw http://www.research.att.com/~njas/sequences/A033626. Not very nice, indeed.

Quote:
 Originally Posted by Jens K Andersen I would prefer A092749, a similar sequence with the smallest term for each exact length (as opposed to at least that length in A092749), and maybe separate sequences for each fixed length.
Hmm, maybe for the second smallest term for each n.
I wonder why there's not even a sequence for the smallest term for the p- series (which would be 2, 5, 13, 19, 43, 43, 73, 73, 109, 109, 245333323, 23181771649 ...).

Quote:
 Originally Posted by Jens K Andersen I guess you know Euler found that 41+n*(n+1) is prime for n = 0..39. Jörg Waldvogel and Peter Leikauf found in http://www.sam.math.ethz.ch/~waldvoge/Projects/clprimes05.pdf that the next occurrence of at least 21 primes is 234505015943235329417+n*(n+1) for n = 0..20.
Yes, I'm aware of these results.

Quote:
 Originally Posted by Jens K Andersen I suspect you have an inefficient program.
For an amateur, I think my program is quite good.
You get an idea of how good (or bad) it actually is by looking at the code in the attachment. It's designed for finding at least 12 simultaneous primes from the p+ sequence.
And yes, it's very unconventional. Could make it a bit faster, though. But, like I said, it's not my CPU time.
Attached Files
 p+n(n+1)_n=0...11.txt (29.9 KB, 207 views)

 2009-03-06, 02:36 #15 Jens K Andersen     Feb 2006 Denmark 3468 Posts p, length of p+ sequence 4296903559301 12 14334964751111 13 17518107964451 12 30431463129071 14 57725094574571 12 60693437191061 12 1 minute with a C program. Added later: 521999251772081 16 Last fiddled with by Jens K Andersen on 2009-03-06 at 03:22 Reason: Found a length 16
2009-03-06, 16:59   #16
mart_r

Dec 2008
you know...around...

2·73 Posts

Quote:
 Originally Posted by Jens K Andersen p, length of p+ sequence 4296903559301 12 14334964751111 13 17518107964451 12 30431463129071 14 57725094574571 12 60693437191061 12 1 minute with a C program. Added later: 521999251772081 16
Okay now, the question that I wanted to ask for years:
What gives you (and Mr Luhn, Mr Wroblewski, Mr Rosenthal and all the other well-known prime pattern seekers) the ultimate power boost in searching for these patterns?
Any sample program you can put at my disposal?

2009-03-06, 18:53   #17
Jens K Andersen

Feb 2006
Denmark

2×5×23 Posts

Quote:
 Originally Posted by mart_r What gives you (and Mr Luhn, Mr Wroblewski, Mr Rosenthal and all the other well-known prime pattern seekers) the ultimate power boost in searching for these patterns? Any sample program you can put at my disposal?
4422004492429759 gives length 16 for the p- sequence, but I don't currently know whether it's the smallest solution.

The details vary but the main things in a search for simultaneous primes are:
1) Use a construction with modular math to only examine cases where none of the numbers have a very small prime factor (for example below 40).
2) Use sieving on an efficient sieve form like arithmetic progressions to quickly eliminate cases where one of the numbers has a relatively small prime factor.
3) Use a fast prp test on the remaining candidates. I usually use the GMP library or PrimeForm/GW for prp testing.
4) Prove the prp solutions.

I divide the search space for one of the simultaneous primes into arithmetic progressions of form k*p#+d where d<p#, and p is the largest prime factor to be avoided by the construction.
Identify the d values between 0 and p# (or a lower value for an inexhaustive search) for which no candidates of form k*p#+d will have a prime factor <=p in one of the numbers.
For each d value, sieve on k to eliminate cases with a small prime factor above p. The sieve often becomes so sparse that I use a form of individual trial factoring after some sieving. If sieving continued then the vast majority of the sieve time would be used on candidates which had already been eliminated.

If you want to search for length 17 on a Windows PC then I can prepare and mail an executable in a couple of days when I have better time. My C source is not public and is modified and recompiled by me for each form and length. I don't have a flexible executable where the form can be input.

2009-03-06, 21:47   #18
mart_r

Dec 2008
you know...around...

10101011102 Posts

So I'm already quite good with the technique I mentioned earlier here:
http://www.mersenneforum.org/showpos...56&postcount=3

Only thing is, I don't know how to effectively sieve an already pre-sieved range for larger factors, since I'm dealing with simultaneous primes, not with separate primes where sieving would be a piece of cake.
... Well, I can think of something, but I'd have yet to test if it is viable.

The main obstacle then is the rather slow BASIC which can only handle distinct integers to 2^53 ("long integers" to 2^31).

Quote:
 If you want to search for length 17 on a Windows PC then I can prepare and mail an executable in a couple of days when I have better time.
You don't have to if it takes you that long. Besides, I don't know how to run C codes *feels outdated - again*.
At least now I have an idea of where I'm standing in the field of prime number research.

Thanks anyway.

Last fiddled with by mart_r on 2009-03-06 at 22:11

 2009-03-19, 18:19 #19 mart_r     Dec 2008 you know...around... 2·73 Posts So, to make this whole p-n(n+1) thingy more interesting: Code:  p smallest divisor of p-n(n+1) 73 17 109 19 2293 29 6163 31 18523 43 42739 47 53509 61 501229 67 11100253 71 17787043 73 38638519 83 40880029 101 65288413 107 432015433 127 2361810469 131 4888301653 137 12276955783 149 96498898819 167 3303436989913 173 3626693315809 179 14456049750829 191 Does anyone feel inclined to continue? (Also, http://www.primepuzzles.net/conjectures/conj_017.htm - no update since 2005?)
 2009-03-20, 01:52 #20 ATH Einyen     Dec 2003 Denmark 32·5·71 Posts First prime millennia with only 5 primes: 21,185,697,626,___ (primes at 083, 267, 983, 993, 999) Last fiddled with by ATH on 2009-03-20 at 01:55
2009-03-20, 07:21   #21
mart_r

Dec 2008
you know...around...

2×73 Posts

Quote:
 Originally Posted by ATH First prime millennia with only 5 primes: 21,185,697,626,___ (primes at 083, 267, 983, 993, 999)
Cool. Thanks!

2009-03-20, 15:21   #22
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by ATH First prime millennia with only 5 primes: 21,185,697,626,___ (primes at 083, 267, 983, 993, 999)

So? We know there are infinitely many such intervals. What is the
point of finding one?

May I suggest that those of you participating in this effort might
actually participate in a different project? This one has a well defined
goal: Assist in the computations that are attempting to disprove
the convexity of pi(x). Such a computation would actually establish a
THEOREM. Much progress has already been made on narrowing the range in
which an exception might be found.

I suggest (without trying to flame anyone) that from the viewpoint of
mathematical aesthetics, that the efforts under discussion in this forum
are more or less pointless? There are several *useful* prime chasing
projects that have a realistic goal. Seventeen or Bust is one such.
The convexity of pi(x) is another. Another VERY VERY useful
computation would be the search for a composite that is both a
Lucas PRP *and* an ordinary PRP. Money is offered for this problem
by Selfridge, Wagstaff & Pomerance.

A good source of problems that mathematicians consider important
is given in Richard Guy's book: Unsolved Problems in Number Theory.

But, IMO, finding examples of intervals of length 1000 that only contain
5 (or some other fixed number less than 168) serve no useful purpose.
We not only know that they exist, but we also know how often an
interval of length 1000 will contain 5 primes (on average)...

Note: I make the same suggestion to those chasing aliquot sequences
in the factoring forum. Unless they have a well-established goal,
there are better uses for the CPU time.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Mickey1 Miscellaneous Math 1 2013-05-30 12:32 Unregistered Information & Answers 0 2011-01-31 15:41 troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 03:49.

Wed Dec 1 03:49:17 UTC 2021 up 130 days, 22:18, 1 user, load averages: 1.26, 1.19, 1.34