Lucas-Lehmer Primes - Page 3

science_man_88 · 2016-07-01, 15:15

Quote:

Originally Posted by Batalov

(((((((((((((30201^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 is 3-PRP!

does (((((((((((((10037^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 factor if not then it has to be prime I think as 30201 is 3*10037 so either 30201 replaced with 3 or 10037 can't factor for it to be prime.edit: I might be confusing myself now.

Xyzzy · 2016-07-01, 18:32

Quote:

Originally Posted by Batalov

(((((((((((((30201^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 is 3-PRP!

It took us a while but we think we have this right:

30201 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 - 2 ^ 2 -

We really dislike parentheses!

henryzz · 2016-07-01, 18:33

Quote:

Originally Posted by science_man_88

does (((((((((((((10037^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 factor if not then it has to be prime I think as 30201 is 3*10037 so either 30201 replaced with 3 or 10037 can't factor for it to be prime.edit: I might be confusing myself now.

These two numbers are unrelated. The one you posted also has a factor 3276799

science_man_88 · 2016-07-01, 19:04

Quote:

Originally Posted by henryzz

These two numbers are unrelated. The one you posted also has a factor 3276799

depends on what you mean by unrelated ( technically if one one x value wasn't a multiple of the other you couldn't say that technically until there was no prime that gave the same mod value for both x) and based on that factor I can tell you that x=10037+3276799*(k) for $-\infty\leq{k}\lt\infty$ are all composite with that factor as one of their's by the fact that all differences of the polynomial will be 0 or a multiple of r.

Batalov · 2016-07-01, 19:29

Here is a primitive [linux] sieve (it is for n=15, but easily modified).
It is reasonably fast to sieve to 45 bits for this n.

Test cases (compare to PFGW with -f9999"{131072}" option):

Code:

20323762176001 | ((((((((((((((6055^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
10062405304321 | ((((((((((((((6009^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
13088925155329 | ((((((((((((((1003^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2

EDIT: added the k*2^(n+2)-1 divisors. Version bumped to 1.2.

science_man_88 · 2016-07-01, 20:02

Quote:

Originally Posted by henryzz

These two numbers are unrelated. The one you posted also has a factor 3276799

I think where the division rule came from in my head, was for n=0 it would be true.

however the rule about dividing differences comes from the binomial theorem. The rule about division in LLP(x,n) for constant x is simply implied by modular constraints.

henryzz · 2016-07-01, 22:24

Quote:

Originally Posted by Batalov

Here is a primitive [linux] sieve (it is for n=15, but easily modified).
It is reasonably fast to sieve to 45 bits for this n.

Test cases (compare to PFGW with -f9999"{131072}" option):

Code:

20323762176001 | ((((((((((((((6055^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
10062405304321 | ((((((((((((((6009^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
13088925155329 | ((((((((((((((1003^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2

I am being clueless currently. Time for bed I think. I can't work out the parameters or what goes in the input file. It just crashes straight away for me. Will come back to this in the morning. Any hints would be useful.
I am running it on windows which may be the issue.
Thanks for making this you have saved me some time tomorrow.

Batalov · 2016-07-01, 22:33

There is no support for Windows in that code.

The input is the s₀ values (odd numbers, one per line; n is implicitly 15 for now).

Batalov · 2016-07-03, 15:38

For n=15, there is
((((((((((((((34251^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
(148593 digits PRP)

henryzz · 2016-07-03, 18:16

Quote:

Originally Posted by Batalov

For n=15, there is
((((((((((((((34251^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
(148593 digits PRP)

What ranges are you searching? I don't want to duplicate any more work.
Looks like a large n=16 or any n=17 would reach the level of the top 5000 primes. If we could prove it that is.

Batalov · 2016-07-03, 18:34

I am now sieving n=16 (up to s<80000) and will stop there.

These are PRPs; there's no good path forward to prove them, and the larger they get the tinier the chance.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Lucas-Lehmer test	Mathsgirl	Information & Answers	23	2014-12-10 16:25
lucas-lehmer theorem	Robot2357	Math	6	2013-06-15 03:10
lucas lehmer outstretch	science_man_88	Miscellaneous Math	7	2010-07-14 12:35
Lucas-Lehmer Test	storm5510	Math	22	2009-09-24 22:32
Lucas-Lehmer	Dougal	Information & Answers	9	2009-02-06 10:25

2016-07-01, 22:33	#30
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	There is no support for Windows in that code. The input is the s₀ values (odd numbers, one per line; n is implicitly 15 for now).

2016-07-03, 15:38	#31
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2505₁₆ Posts	For n=15, there is ((((((((((((((34251^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 (148593 digits PRP)

2016-07-03, 18:34	#33
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	I am now sieving n=16 (up to s<80000) and will stop there. These are PRPs; there's no good path forward to prove them, and the larger they get the tinier the chance.