mersenneforum.org  

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

Reply
 
Thread Tools
Old 2013-06-22, 20:37   #78
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

Can't edit any more. I just found a mistake in my calculation for x. Dang! This will change the sieve quite a bit. I'll be back...
Puzzle-Peter is offline   Reply With Quote
Old 2013-06-23, 00:29   #79
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

247510 Posts
Default

do you need some large n value to help?
firejuggler is offline   Reply With Quote
Old 2013-06-23, 07:48   #80
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

OK, got it ( I hope...). After testing the small example I wanted to make my life easier and went a little bit too far.

Let's start at the beginning.

Like I said, I want to be able to prove all three members of a triple by N+1 or N-1 tests. So I thought about creating a triple from already known primes. The small working example used numbers of the form

N=(s+2)*(a*s^2 + b*s -2) -1/+1/+5 with s constant, a,b variable

For the -1 and +1 number, N+1 and N-1 can be done with a helper (s+2) and for +5 a N-1 test can be done with helper s. So I need s and (s+2) to be known primes, i.e. a pair of twin primes. Those are available in every reasonable size from e.g. http://www.noprimeleftbehind.net/gary/twins1M.htm

To make my life easier, I first got rid of the b*p part, wich results in

N=(s+2)*(a*s^2 -2) -1/+1/+5 which still works (again, tested on a small example to make sure I didn't miss any algebraic factorizations)

Next I thought I could simplify this whole process even more by going for N=a*(s+2)*(s^2 -2) which is wrong. This was the version my last question was based on.

So, back one step.

N=(s+2)*(a*s^2 -2) -1/+1/+5
ABC2 works for small numbers but it's way too slow for larger numbers.

Assuming I made no further mistakes, here's what I've got:
The coefficient a needs to be an even number. (After deciding which s to use, the number of possible values for a can be further reduced by eliminating a's resulting in candidates divisible by 3 or 5, that's about as far as I can think lol)
For a=2 we have a starting point of (s+2)*(2*s^2 -2)
Incrementing a by 2 increases the candidate by (s+2)*2s^2
Again I can precompute the starting point mod p and the increment mod p for a list of sieve primes p and use this information for going through a bitarray representing the a's. Which means I am stuck at the same point as before i.e. how to quickly go through the array without calculating mods for every a.

I hope I didn't make this sound like a lot of gibberish. If so, let me know and I'll try to clarify.
Puzzle-Peter is offline   Reply With Quote
Old 2013-06-23, 08:22   #81
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×1,427 Posts
Default

Twin primes also available on my page:
- see Downloads -> all primes listed in the data tables
- see Related -> First twin k: all first twin of any k-value < 15000
kar_bon is offline   Reply With Quote
Old 2013-06-23, 08:34   #82
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·132 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Twin primes also available on my page:
- see Downloads -> all primes listed in the data tables
- see Related -> First twin k: all first twin of any k-value < 15000
Thanks!
Puzzle-Peter is offline   Reply With Quote
Old 2013-07-04, 13:57   #83
biwema
 
biwema's Avatar
 
Mar 2004

5758 Posts
Default

If I understand you correctly, you try to find x that k*x+4 or k*x+6 or both can be factored easily (N+1; N-1) that you don’t need PRIMO. In that case there are also some restrictions for x.

Actually there are already triplets, which have a special form which can be proven with PFGW. For example, have a look at this triplet:


(99241437759 * 205881 * 4001# (205881*4001# + 1) + 210) (205881*4001# − 1)/35 + d, d = 1, 5, 7 (5132 digits, Mar 2006, Ken Davis).

If you change the parameters, you could find larger primes. Due to the special form you need an adapted sieve and the PRP as well as the sieve could be somewhat slower.
biwema is offline   Reply With Quote
Old 2013-07-04, 15:09   #84
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

Quote:
Originally Posted by biwema View Post
If I understand you correctly, you try to find x that k*x+4 or k*x+6 or both can be factored easily (N+1; N-1) that you don’t need PRIMO. In that case there are also some restrictions for x.
I'm not sure we are talking about the same thing.

I plan to look at numbers of the form
N=(s+2)*(a*s^2 -2) -1/+1/+5
for -1 and +1, N+1 and N-1 have a helper factor (s+2)
for +5 we get
a*s^3 + 2*a*s^2 - 2*s - 4 + 5 which simplifies to
a*s^3 + 2*a*s^2 - 2*s + 1 so we can do a N-1 test with helper factor s.
That means I need s and (s+2) to be a pair of twin primes.

The variable I will be sieving is a. I know all the stuff I need is in the programs uploaded to this thread, but rearranging the pieces is quite tricky.
Puzzle-Peter is offline   Reply With Quote
Old 2013-07-13, 10:57   #85
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167716 Posts
Default

I have been thinking about how to modify gsieve for different forms. I think I understand quite a bit of the code.
However, in the array Table each value is set to ((p+1)/2)^e%p. I don't get what this is trying to do. I am probably being stupid. Can anyone help me out by pointing me in the correct direction?

Once I understand that I think I should be able to change the sieve to k*x+c[i] where x is anything we want(currently 2^n) and c[i] are -1,+1 etc. A primorial sieve should be possible for instance.
henryzz is offline   Reply With Quote
Old 2013-07-13, 13:16   #86
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·132 Posts
Default

I keep trying a far less universal approach only for the form I mentioned in my last post. So I can use the pow_mod and mod_inv functions without fully understanding what's happening inside. But the array handling stuff is far above my head.

To make things even worse, the number of sieve primes needs to be increased as well. For the usual forms of triples and quads I used gsieve to get a starting list of candidates which I then sieved further using NewPGen. For the stuff we're talking about here, all the sieving needs to be done in the program itself.
Puzzle-Peter is offline   Reply With Quote
Old 2013-07-13, 13:59   #87
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

575110 Posts
Default

Currently the memory usage is too high to sieve much deeper. However, it should be possible to split the list of primes into blocks which use a sensible amount of memory. This might potentially come at a bit of a speed cost.
henryzz is offline   Reply With Quote
Old 2013-07-14, 12:43   #88
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts
Default

I'm in the process to rewrite gsieve.c for your new problem. It will be possible to sieve large primes also (so q>2^31), what gsieve currently doesn't handle.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve? Stargate38 And now for something completely different 2 2017-04-28 00:08
Efficiently finding a linear progression in data fivemack Math 27 2015-12-12 18:42
GPU Prime Sieve tapion64 GPU Computing 7 2014-04-10 06:15
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Prime in Riesel Sieve Project Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 05:04.

Sun Nov 29 05:04:15 UTC 2020 up 80 days, 2:15, 3 users, load averages: 2.70, 1.90, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.