Lucas-Lehmer Primes

[henryzz]

Originally Posted by science_man_88

I'm not sure if I believe the factor form without the proof, I do see based on an assumption that in theory the lowest factor has to exceed 2^(n+1) because if not then there can't be 2^n values of every n below that and still have values leftover to delete ( as they would sum up to 2^(n+1)-1). okay I guess I see the logic of 2^(n+2) because then it allows there to be the proper 2^(n+1) values the chosen n. still not convinced on the exact form though. my guess is this comes from it needing to be odd ? and not the 1 or 7 mod 8 form. also have you sieved the k the same way I would have sieved the values at any n because every third one allows the difference to divide by 3 etc. so the k in the same congruence classes can all fall to the same factor possibly.

I am pretty convinced of this form. A proof would be nice. Again it may be worth looking for a proof of the form of factors for fermat numbers as that may be fairly similar.
I don't have the time or brain power to put too much effort in currently I will probably come back to it with more time.

[science_man_88]

Originally Posted by henryzz

I am pretty convinced of this form. A proof would be nice. Again it may be worth looking for a proof of the form of factors for fermat numbers as that may be fairly similar.
I don't have the time or brain power to put too much effort in currently I will probably come back to it with more time.

by using your form of factor I did disprove my idea that the values needed to happen consecutively and I also disproved the 2^(n+1) part of it though there can be more. still got my function down to below x^3 in most cases with a few potentially as low as x^2 for timing.

LLPsieve(r)={
my(r=r,m=logint(r,2),a=[1..r-1],b=vector(m,i,[]),c=[%1,%2,%3,%4,%5,%6,%7,%8,%9,%10,%11][1..m]);
for(z=1,#c,
     for(y=1,r\2+1,
          if(a[y]==0,
              ,
             g=r-y;if(r%(2^z)==1 && subst(c[z],x,y)%r,
             ,
             b[z]=concat(b[z],[y,g]);
             a[y]=0;
             a[g]=0
                       )
            )
         )
    );
b
}

{parforprime(x=1,8000,
                             if(x%8==1 || x%8==7,
                                LLPsieve(x)
                               ),
                               c,
                               if(c,
                                  print(c)
                                 )
                             )}

edit: okay properly testing the forms given blew up the time a bit even searching through primes. note: one of them is missing a check in the code above.okay maybe the pattern isn't disproved about 2^z being in n=z it just looks like it because of how my data shows it with some n=2 lining up with n=3 when i look at it.

[science_man_88]

[19, 340], [], [], [1, 358, 2, 357, 3, 356, 4, 355, 5, 354, 6, 353, 7, 352, 8, 351, 9, 350, 10, 349, 11, 348, 12, 347, 13, 346, 14, 345, 15, 344, 16, 343, 17, 342, 18, 341, 20, 339, 21, 338, 22, 337, 23, 336, 24, 335, 25, 334, 26, 333, 27, 332, 28, 331, 29, 330, 30, 329, 31, 328, 32, 327, 33, 326, 34, 325, 35, 324, 36, 323, 37, 322, 38, 321, 39, 320, 40, 319, 41, 318, 42, 317, 43, 316, 44, 315, 45, 314, 46, 313, 47, 312, 48, 311, 49, 310, 50, 309, 51, 308, 52, 307, 53, 306, 54, 305, 55, 304, 56, 303, 57, 302, 58, 301, 59, 300, 60, 299, 61, 298, 62, 297, 63, 296, 64, 295, 65, 294, 66, 293, 67, 292, 68, 291, 69, 290, 70, 289, 71, 288, 72, 287, 73, 286, 74, 285, 75, 284, 76, 283, 77, 282, 78, 281, 79, 280, 80, 279, 81, 278, 82, 277, 83, 276, 84, 275, 85, 274, 86, 273, 87, 272, 88, 271, 89, 270, 90, 269, 91, 268, 92, 267, 93, 266, 94, 265, 95, 264, 96, 263, 97, 262, 98, 261, 99, 260, 100, 259, 101, 258, 102, 257, 103, 256, 104, 255, 105, 254, 106, 253, 107, 252, 108, 251, 109, 250, 110, 249, 111, 248, 112, 247, 113, 246, 114, 245, 115, 244, 116, 243, 117, 242, 118, 241, 119, 240, 120, 239, 121, 238, 122, 237, 123, 236, 124, 235, 125, 234, 126, 233, 127, 232, 128, 231, 129, 230, 130, 229, 131, 228, 132, 227, 133, 226, 134, 225, 135, 224, 136, 223, 137, 222, 138, 221, 139, 220, 140, 219, 141, 218, 142, 217, 143, 216, 144, 215, 145, 214, 146, 213, 147, 212, 148, 211, 149, 210, 150, 209, 151, 208, 152, 207, 153, 206, 154, 205, 155, 204, 156, 203, 157, 202, 158, 201, 159, 200, 160, 199, 161, 198, 162, 197, 163, 196, 164, 195, 165, 194, 166, 193, 167, 192, 168, 191, 169, 190, 170, 189, 171, 188, 172, 187, 173, 186, 174, 185, 175, 184, 176, 183, 177, 182, 178, 181, 179, 180], [], [], [], []] disproves that hypothesis so that actually helps because as long as 2^z is the minimum of n=z (assuming any solutions) we could use less length in the vector printed.

[Batalov]

Originally Posted by henryzz

Just thought I would point out that we don't need to test the small primes normally as we know the form of the factors is k*2^(n+2)+-1 or 2. This means that the factors start at over 1e4 and will finish at over 1e8 and if we get it faster maybe 1e10.
As we are only looking at a range of around 10-100k values of x this means that we can't really sieve. Quickly identifying which candidates can divide LL(x,n) is the best we can hope for. Note n will remain fixed.

If you want, take the simple sieve that I posted once for the Mills' (PR)primes #12 and #13. You will need very minimal modifications of the code.
Like Mills' primes, this is a chained process, so you want to do pre-factoring rather than sieving.

EDIT: Actually no. perhaps you want to start from ck_sieve source and repeat n=14 nested sqrts with recursion (only mod k*2^s+1 as you correctly noted) and then strike the sieve space. Then it could be a sieve, actually.

[science_man_88]

Originally Posted by Batalov

If you want, take the simple sieve that I posted once for the Mills' (PR)primes #12 and #13. You will need very minimal modifications of the code.
Like Mills' primes, this is a chained process, so you want to do pre-factoring rather than sieving.

EDIT: Actually no. perhaps you want to start from ck_sieve source and repeat n=14 nested sqrts with recursion (only mod k*2^s+1 as you correctly noted) and then strike the sieve space. Then it could be a sieve, actually.

I must be doing something majorly wrong with my code then because I can get non null results without this but with this addition I only get 4 result vectors for primes under 1000.

eg I get that (5165+276) | 276^2-2 and 5165 ^2-2 for example

[Batalov]

Originally Posted by science_man_88

I must be doing something majorly wrong with my code then

What code?

Originally Posted by science_man_88

I must be doing something majorly wrong with my code then because I can get non null results without this but with this addition

What addition?

[science_man_88]

Originally Posted by Batalov

What code?

What addition?

the code above but using a better parforprime loop.

the fact that divisors must be of a certain type if I add that in I get ( up to x=12000,n=12000) just 8 result vectors that don't even fill up my pari screen unless i truncate them to screen width.

versus without that restriction I get a file worth 7.91 MB

found my error in the former case about only getting 8 results I was stupidly looking for powers only. I might see if I can change the formatting abit so I can upload my results file from earlier I've mostly been playing around with speed ups.

[henryzz]

Originally Posted by Batalov;437212
[COLOR=Blue

EDIT: Actually no. perhaps you want to start from ck_sieve source and repeat n=14 nested sqrts with recursion (only mod k*2^s+1 as you correctly noted) and then strike the sieve space. Then it could be a sieve, actually.[/COLOR]

Ignoring the k*2^s+-1 stuff for now
I think I get how to get the roots.
For n=3 the roots will be:
sqrtmodp(2+sqrtmodp(2+sqrtmodp(2,p),p),p)
p-sqrtmodp(2+sqrtmodp(2+sqrtmodp(2,p),p),p)
sqrtmodp(2+p-sqrtmodp(2+sqrtmodp(2,p),p),p)
p-sqrtmodp(2+p-sqrtmodp(2+sqrtmodp(2,p),p),p)
sqrtmodp(2+sqrtmodp(2+p-sqrtmodp(2,p),p),p)
p-sqrtmodp(2+sqrtmodp(2+p-sqrtmodp(2,p),p),p)
sqrtmodp(2+p-sqrtmodp(2+p-sqrtmodp(2,p),p),p)
p-sqrtmodp(2+p-sqrtmodp(2+p-sqrtmodp(2,p),p),p)

As far as I can tell I can remove all the bsgs stuff as I am doing x not x^n. I just need to add p to all the roots if I want to sieve.
The trouble is I will never need to add p to the roots or even calculate all the roots as p is a lot bigger than my sieve range. This means it won't be a sieve.The big thing will be doing all the sqrts mod p.

[science_man_88]

Turns out, that file would have been bigger had I got PARI to completely print the correct thing. tried it again with two write files and unless I use writebin maybe or turn the vectors into vecsmall I don't think I can get either file under size without compression now.

[science_man_88]

here's one file of the two I made the other will only compress to over 3 MB this way though.

[Batalov]

Originally Posted by henryzz

Nothing for n=14 yet.

(((((((((((((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!