Search primes of form 2*n^n ± 1 - Page 2

rogue · 2018-04-08, 21:20

Quote:

Originally Posted by Batalov

I am not sure how frequent this use for this code branch would be.

The depth was around 29.3 bits after a day or two sieving (on 1 core up to n<=250k) so I am sure that it did save some time; factors for these are general, so I now checked a default PFGW sieving would have been ~26 bits (~83,000 candidates times 0-4 minutes = ...quite a bit of time saved).

I would expect that a new and improved version could get you to 32 bits.

Batalov · 2018-04-08, 23:13

Quote:

Originally Posted by JeppeSN

Good one! I hoped this would catch your interest.

Are you continuing the search? And did you consider the minus form as well?

/JeppeSN

Though I did sieve far (to n=250k), but that was just in case.
Stopping the plus side search at n=84438.

I've double-checked the minus side from scratch and went a bit above 50k now. The minus side is twice thicker; ...more sieving will help, Mark, sounds good.

henryzz · 2018-04-09, 08:51

Quote:

Originally Posted by rogue

I see that you used MultiSieve. I hope that it saved you some time. Is sieving this form a candidate for mtsieve? It would probably take me only a day or two to write it.

More useful might be a guide on how to add more forms like it.

rogue · 2018-04-09, 12:56

Quote:

Originally Posted by henryzz

More useful might be a guide on how to add more forms like it.

Do you mean, how to add support for other forms to mtsieve?

rogue · 2018-04-09, 15:28

I have some code, which is about 2.5x faster than MultiSieve for this form. I know that getting another 20% is doable, but I would need to write some assembly do that. Writing some GPU code could easily double the speed. I can probably write and test the GPU code faster than the asm code. Is there any interest in that?

henryzz · 2018-04-09, 18:37

Quote:

Originally Posted by rogue

Do you mean, how to add support for other forms to mtsieve?

Yes. Every so often people post about a potential new form or I think of one. Working out the progression of the form mod p isn't that hard so it shouldn't be hard to come up with a basic sieve. I am expecting that you would often be able to speed up any sieve I created based upon mtsieve. http://mersenneforum.org/showthread.php?t=23069 was an example.

rogue · 2018-04-09, 20:05

Quote:

Originally Posted by henryzz

Yes. Every so often people post about a potential new form or I think of one. Working out the progression of the form mod p isn't that hard so it shouldn't be hard to come up with a basic sieve. I am expecting that you would often be able to speed up any sieve I created based upon mtsieve. http://mersenneforum.org/showthread.php?t=23069 was an example.

Okay. I'll work to put together a page with the steps. It isn't too difficult. The hardest part is the math that finds the factors. The most tedious is doing I/O to disk because of formatting and parsing data.

Citrix · 2018-04-11, 06:35

I had searched these types of primes up to 50000 on both + and - sides several years ago. I used a script and srsieve - this was significantly faster than multisieve to sieve these numbers.

rogue · 2018-04-11, 12:02

Quote:

Originally Posted by Citrix

I had searched these types of primes up to 50000 on both + and - sides several years ago. I used a script and srsieve - this was significantly faster than multisieve to sieve these numbers.

What optimizations did you use? I could implement them in kbbsieve.

Dr Sardonicus · 2018-04-11, 13:24

The behavior of nⁿ (mod p) has some (perhaps) interesting consequences for sieving.

If p == 3 (mod 8), then the multiplicative order m of Mod(-2, p) is odd, and the multiplicative order of Mod(2, p) is 2*m. It follows that the number of residues of n (mod (p-1)*p) for which

2*nⁿ + 1 == 0 (mod p)

is three times the number for which

2*nⁿ - 1 (mod p).

For example, with p = 3,

2*nⁿ + 1 == 0 (mod 3) for n == 1, 2, or 4 (mod 6), while

2*nⁿ - 1 == 0 (mod 3) for n == 5 (mod 6).

If p == 7 (mod 8) the situation is reversed; the multiplicative order m of Mod(2, p) is odd, and the multiplicative order of Mod(-2, p) is 2*m. The number of residues n (mod (p-1)*p) for which

2*nⁿ - 1 -- 0 (mod p)

is three times the number for which

2*nⁿ + 1 == 0 (mod p).

For example, with p = 7,

2*nⁿ - 1 == 0 (mod 7) for n == 2, 4, 10, 23, 25, or 26 (mod 42), while

2*nⁿ + 1 == 0 (mod 7) for n == 5 or 31 (mod 42).

For p == 5 (mod 8), the multiplicative orders of 2 and -2 (mod p) are the same, and the number of residues (mod (p-1)*p) for which 2*nⁿ + 1 and 2*nⁿ - 1 are divisible by p, are the same. For example, with p = 5,

2*nⁿ - 1 == 0 (mod 5) for n == 7 or 13 (mod 20), while

2*nⁿ + 1 == 0 (mod 5) for n == 3 or 17 (mod 20).

For p == 1 (mod 8) the situation is not generally predictable. If however 2 is not a biquadratic residue (mod p), then the numbers of residues (mod (p-1)*p) for which 2*nⁿ + 1 and 2*nⁿ - 1 are divisible by p, will be the same. Unfortunately, determining whether 2 is a biquadratic residue (mod p) isn't cheap AFAIK.

If m is the multiplicative order of 2 (-2, resp) mod p, the number of residues (mod (p-1)*p) for which 2*nⁿ - 1 (2*nⁿ+ 1, resp) are divisible by p are

$(p-1)\sum_{d \mid \frac{p-1}{m}}\frac{\varphi(md)}{md}$

Citrix · 2018-04-11, 22:05

Quote:

Originally Posted by rogue

What optimizations did you use? I could implement them in kbbsieve.

No optimizations - just testing one candidate at a time and then LLRing it if no factor was found.
The generic FFT made me stop the search as each candidate was taking too long.

2018-04-11, 13:24	#21
Dr Sardonicus Feb 2017 Nowhere 11043₈ Posts	The behavior of nⁿ (mod p) has some (perhaps) interesting consequences for sieving. If p == 3 (mod 8), then the multiplicative order m of Mod(-2, p) is odd, and the multiplicative order of Mod(2, p) is 2m. It follows that the number of residues of n (mod (p-1)p) for which 2nⁿ + 1 == 0 (mod p) is three times the number for which 2nⁿ - 1 (mod p). For example, with p = 3, 2nⁿ + 1 == 0 (mod 3) for n == 1, 2, or 4 (mod 6), while 2nⁿ - 1 == 0 (mod 3) for n == 5 (mod 6). If p == 7 (mod 8) the situation is reversed; the multiplicative order m of Mod(2, p) is odd, and the multiplicative order of Mod(-2, p) is 2m. The number of residues n (mod (p-1)p) for which 2nⁿ - 1 -- 0 (mod p) is three times the number for which 2nⁿ + 1 == 0 (mod p). For example, with p = 7, 2nⁿ - 1 == 0 (mod 7) for n == 2, 4, 10, 23, 25, or 26 (mod 42), while 2nⁿ + 1 == 0 (mod 7) for n == 5 or 31 (mod 42). For p == 5 (mod 8), the multiplicative orders of 2 and -2 (mod p) are the same, and the number of residues (mod (p-1)p) for which 2nⁿ + 1 and 2nⁿ - 1 are divisible by p, are the same. For example, with p = 5, 2nⁿ - 1 == 0 (mod 5) for n == 7 or 13 (mod 20), while 2nⁿ + 1 == 0 (mod 5) for n == 3 or 17 (mod 20). For p == 1 (mod 8) the situation is not generally predictable. If however 2 is not* a biquadratic residue (mod p), then the numbers of residues (mod (p-1)p) for which 2nⁿ + 1 and 2nⁿ - 1 are divisible by p, will be the same. Unfortunately, determining whether 2 is a biquadratic residue (mod p) isn't cheap AFAIK. If m is the multiplicative order of 2 (-2, resp) mod p, the number of residues (mod (p-1)p) for which 2nⁿ - 1 (2nⁿ+ 1, resp) are divisible by p are $(p-1)\sum_{d \mid \frac{p-1}{m}}\frac{\varphi(md)}{md}$ Last fiddled with by Dr Sardonicus on 2018-04-11 at 13:36

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primes of the form (b+-1)*b^n+-1 and b^n+-(b+-1)	sweety439	sweety439	162	2020-05-15 18:33
Primes of the form n+-phi(n)	carpetpool	carpetpool	3	2017-01-26 01:29
Infinitely many primes of a form?	PawnProver44	Homework Help	1	2016-03-15 22:39
Primes of the form a^(2^n)+b^(2^n)	YuL	Math	21	2012-10-23 11:06
Primes of the form 2.3^n+1	Dougy	Math	8	2009-09-03 02:44

2018-04-09, 15:28	#16
rogue "Mark" Apr 2003 Between here and the 11·577 Posts	I have some code, which is about 2.5x faster than MultiSieve for this form. I know that getting another 20% is doable, but I would need to write some assembly do that. Writing some GPU code could easily double the speed. I can probably write and test the GPU code faster than the asm code. Is there any interest in that?

2018-04-11, 06:35	#19
Citrix Jun 2003 2×7×113 Posts	I had searched these types of primes up to 50000 on both + and - sides several years ago. I used a script and srsieve - this was significantly faster than multisieve to sieve these numbers.