mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-03-04, 19:41   #12
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

647 Posts
Default

Oh it's not my CPU time.
I torture the computer at my workplace with that :)
mart_r is offline   Reply With Quote
Old 2009-03-04, 22:44   #13
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
Jens K Andersen is offline   Reply With Quote
Old 2009-03-05, 19:45   #14
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

647 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
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 View Post
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 View Post
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 View Post
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
File Type: txt p+n(n+1)_n=0...11.txt (29.9 KB, 189 views)
mart_r is offline   Reply With Quote
Old 2009-03-06, 02:36   #15
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

23010 Posts
Default

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
Jens K Andersen is offline   Reply With Quote
Old 2009-03-06, 16:59   #16
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

64710 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
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?
mart_r is offline   Reply With Quote
Old 2009-03-06, 18:53   #17
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
Jens K Andersen is offline   Reply With Quote
Old 2009-03-06, 21:47   #18
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

647 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2009-03-19, 18:19   #19
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

647 Posts
Default

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?)
mart_r is offline   Reply With Quote
Old 2009-03-20, 01:52   #20
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×7×223 Posts
Default

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
ATH is offline   Reply With Quote
Old 2009-03-20, 07:21   #21
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

647 Posts
Default

Quote:
Originally Posted by ATH View Post
First prime millennia with only 5 primes: 21,185,697,626,___ (primes at 083, 267, 983, 993, 999)
Cool. Thanks!
mart_r is offline   Reply With Quote
Old 2009-03-20, 15:21   #22
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 01:55.

Sat May 8 01:55:50 UTC 2021 up 29 days, 20:36, 0 users, load averages: 2.14, 1.70, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.