Probable primes of the form (2^(p^2)-1) / (2^p-1) - Page 2

a1call · 2022-08-17, 05:55

Just realized my error in the code checking valuation p instead of x.
Not getting any younger.

ryanp · 2022-08-17, 15:43

LLR2 does seem to be able to handle these:

Code:

Starting Fermat PRP test of M3636649/known_factors
Using AVX-512 FFT length 192K, Pass1=192, Pass2=1K, clm=1, 4 threads, a = 3
Iteration: 30000 / 3636649 [0.32%], ms/iter:  0.612, ETA: 00:36:48

I'm going to attempt to test p in the range [2000...5000].

a1call · 2022-08-17, 20:40

Quote:

Originally Posted by a1call

Just realized my error in the code checking valuation p instead of x.
Not getting any younger.

Finally had time to run the corrected code.

Code:

\\ EPP-340-A
ExpPower1=2
subtrExpPBy =1
ExpPower2=ExpPower1-subtrExpPBy
a=2
forprime(q=2,19,{
    p=(a^(q^ExpPower1)-1)/(a^(q^ExpPower2)-1);
    print("\n(",a,"^(",q,"^",ExpPower1,")-1)/(",a,"^(",q,"^",ExpPower2,")-1)");
    if(ispseudoprime(p),print("** PRP ",p));
    fordiv(p,x,
        if(x==1,next(1));
        print("valuation = ",valuation(x-1,q));
    );
})

Code:

(2^(2^2)-1)/(2^(2^1)-1)
** PRP 5
valuation = 2

(2^(3^2)-1)/(2^(3^1)-1)
** PRP 73
valuation = 2

(2^(5^2)-1)/(2^(5^1)-1)
valuation = 2
valuation = 2
valuation = 2

(2^(7^2)-1)/(2^(7^1)-1)
** PRP 4432676798593
valuation = 2

(2^(11^2)-1)/(2^(11^1)-1)
valuation = 2
valuation = 2
valuation = 2

(2^(13^2)-1)/(2^(13^1)-1)
valuation = 2
valuation = 2
valuation = 2
valuation = 2
valuation = 2
valuation = 2
valuation = 2

(2^(2^3)-1)/(2^(2^2)-1)
** PRP 17
valuation = 4

(2^(3^3)-1)/(2^(3^2)-1)
** PRP 262657
valuation = 3

(2^(5^3)-1)/(2^(5^2)-1)
valuation = 3
valuation = 3
valuation = 3

(2^(7^3)-1)/(2^(7^2)-1)
valuation = 3
valuation = 3
valuation = 4
valuation = 4
valuation = 3
valuation = 3
valuation = 5
valuation = 3
valuation = 5
valuation = 3
valuation = 3
valuation = 3
valuation = 4
valuation = 3
valuation = 3

(2^(2^4)-1)/(2^(2^3)-1)
** PRP 257
valuation = 8

(2^(3^4)-1)/(2^(3^3)-1)
valuation = 4
valuation = 4
valuation = 4
valuation = 4
valuation = 5
valuation = 5
valuation = 4

ATH · 2022-08-17, 21:27

Quote:

Originally Posted by ryanp

LLR2 does seem to be able to handle these:

Code:

Starting Fermat PRP test of M3636649/known_factors
Using AVX-512 FFT length 192K, Pass1=192, Pass2=1K, clm=1, 4 threads, a = 3
Iteration: 30000 / 3636649 [0.32%], ms/iter:  0.612, ETA: 00:36:48

I'm going to attempt to test p in the range [2000...5000].

PFGW also works like this:

ABC (2^($a*$a)-1)/(2^$a-1)
59

result:
(2^(59*59)-1)/(2^59-1) is 3-PRP! (0.0235s+0.0004s)

Here are my results from back then, including more factors up to 10000:
http://hoegge.dk/mersenne/M(p2)divM(p).txt

Here is the remaining candidates 2000-5000:

Code:

ABC (2^($a*$a)-1)/(2^$a-1)
2027
2029
2069
2081
2089
2099
2141
2143
2161
2179
2239
2243
2267
2269
2281
2287
2297
2311
2333
2341
2351
2377
2383
2423
2447
2459
2467
2477
2531
2539
2549
2551
2579
2617
2647
2677
2683
2689
2713
2719
2729
2731
2767
2789
2797
2801
2803
2833
2851
2857
2861
2897
2917
2927
2939
2963
3001
3011
3019
3119
3137
3169
3181
3187
3191
3203
3221
3251
3253
3271
3323
3331
3371
3407
3413
3433
3449
3457
3469
3491
3511
3571
3581
3631
3643
3697
3709
3719
3727
3779
3803
3823
3833
3881
3911
3919
3929
3931
3943
3967
3989
4007
4013
4019
4021
4027
4073
4091
4139
4153
4157
4159
4177
4231
4241
4243
4283
4297
4327
4337
4339
4349
4357
4363
4409
4423
4441
4447
4481
4513
4519
4523
4583
4591
4637
4651
4663
4703
4721
4723
4729
4733
4759
4793
4817
4831
4861
4877
4903
4919
4933
4967
4969

Batalov · 2022-08-18, 00:11

Quote:

Originally Posted by ATH

PFGW also works like this:

ABC (2^($a*$a)-1)/(2^$a-1)
59

I would recommend squaring ($a*$a) externally, like this

ABC (2^$a-1)/(2^$b-1)
3481 59

And with this form, prefactor; and even better - prefactor each in its own workunit with option
-N -k -l -f"9999{6962}" <-- insert 2p² here

Prefactoring pre-project can be prepared with awk or perl and then pfgw (each in separate folder).
And after pfgw ran for several hours, kill and check if pfgw.out has "has factor", then remove from candidate list.
Then finish off with LLR as configured above (with /$e )

ATH · 2022-08-18, 05:18

You can trial factor 2^{p^2}-1 more efficiently on GPU with a modified mfaktc that accepts p^2, or if on a CPU then a modified version of Ernst MFactor that accepts p^2.

If Pfgw is not used for prefactor is there any advantage of using this form?
ABC (2^$a-1)/(2^$b-1)
3481 59

ATH · 2022-08-18, 08:24

Factoring limits I factored remaining candidates up to back then with mfaktc (only looking for factors 2*k*p^2 + 1)
2000-2803 65 bits
2833-3989 66 bits
4007-5653 67 bits
5657-7993 68 bits
8009-10000 69 bits

a1call · 2022-08-19, 01:27

A false alarm with no small factors!

Code:

PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6]

(3^(19^4)-1)/(3^(19^3)-1) is 3-PRP! (56.4782s+0.0033s)

http://factordb.com/index.php?query=...19%5E3%29-1%29

And one with no known factors:

http://factordb.com/index.php?query=...23%5E2%29-1%29

Code:

PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6]
(3^(23^3)-1)/(3^(23^2)-1) is 3-PRP! (0.3976s+0.0002s)

Looks like will have to avoid any of the bases equal to the power of q:

Code:

PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6]


***WARNING! file CIM-100-E.txt may have already been fully processed.

Primality testing (3^(23^4)-1)/(3^(23^3)-1) [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
(3^(23^4)-1)/(3^(23^3)-1) is composite (426.7206s+0.0078s)

Batalov · 2022-08-19, 20:49

Quote:

Originally Posted by ATH

You can trial factor 2^{p^2}-1 more efficiently on GPU with a modified mfaktc that accepts p^2, or if on a CPU then a modified version of Ernst MFactor that accepts p^2.

If Pfgw is not used for prefactor is there any advantage of using this form?
ABC (2^$a-1)/(2^$b-1)
3481 59

Of course. But because This can only be done by Ryan and he only has a few GPUs and *000's of CPUs, this message was "preformatted for him". Ryan should definitely make use of your sieved files.

Of course, (with cold statistician's eyes) the expected yield of this fishing expedition is approximately the same as for Motzkin primes, i.e. 0.000.

a1call · 2022-08-20, 05:55

Yes indeed. They are a general format of
(a^q^n-1) / (a^q^(n-1)-1 for primes q
Fermat numbers are a subset of this format and we know how easy it is to find Fermat primes. :smile
Like Fermat numbers they seem to be easily factorable and compared to other integers of similar size they are, but they get so large so fast.
I hope I didn’t encourage anyone to go on a wild goose chase. Additionally there seems to be many pseudoprimes in small bases.

2022-08-17, 15:43	#13
ryanp Jun 2012 Boulder, CO 5²×17 Posts	LLR2 does seem to be able to handle these: Code: Starting Fermat PRP test of M3636649/known_factors Using AVX-512 FFT length 192K, Pass1=192, Pass2=1K, clm=1, 4 threads, a = 3 Iteration: 30000 / 3636649 [0.32%], ms/iter: 0.612, ETA: 00:36:48 I'm going to attempt to test p in the range [2000...5000].

2022-08-18, 08:24	#18
ATH Einyen Dec 2003 Denmark 110101101010₂ Posts	Factoring limits I factored remaining candidates up to back then with mfaktc (only looking for factors 2kp^2 + 1) 2000-2803 65 bits 2833-3989 66 bits 4007-5653 67 bits 5657-7993 68 bits 8009-10000 69 bits Last fiddled with by ATH on 2022-08-18 at 08:25

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
generalized minimal (probable) primes	sweety439	sweety439	140	2022-12-20 07:08
Probable primality test for numbers of the form (10^n-1)/9-2 and (10^n+1)/11-2 ?	kijinSeija	Math	0	2022-05-13 20:32
Primes of the form 30*n^2-1	enzocreti	enzocreti	5	2020-03-01 02:10
pg primes of the form 41s+r	enzocreti	enzocreti	0	2019-07-15 13:12
The probable primes	philmoore	Five or Bust - The Dual Sierpinski Problem	388	2019-03-01 04:30

2022-08-17, 05:55	#12
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 4435₈ Posts	Just realized my error in the code checking valuation p instead of x. Not getting any younger.

2022-08-18, 05:18	#17
ATH Einyen Dec 2003 Denmark 2·17·101 Posts	You can trial factor 2^{p^2}-1 more efficiently on GPU with a modified mfaktc that accepts p^2, or if on a CPU then a modified version of Ernst MFactor that accepts p^2. If Pfgw is not used for prefactor is there any advantage of using this form? ABC (2^$a-1)/(2^$b-1) 3481 59

2022-08-20, 05:55	#21
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2,333 Posts	Yes indeed. They are a general format of (a^q^n-1) / (a^q^(n-1)-1 for primes q Fermat numbers are a subset of this format and we know how easy it is to find Fermat primes. :smile Like Fermat numbers they seem to be easily factorable and compared to other integers of similar size they are, but they get so large so fast. I hope I didn’t encourage anyone to go on a wild goose chase. Additionally there seems to be many pseudoprimes in small bases.