mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-08-17, 05:55   #12
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72×47 Posts
Default

Just realized my error in the code checking valuation p instead of x.
Not getting any younger.
a1call is online now   Reply With Quote
Old 2022-08-17, 15:43   #13
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

1101001112 Posts
Default

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].
ryanp is offline   Reply With Quote
Old 2022-08-17, 20:40   #14
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72×47 Posts
Default

Quote:
Originally Posted by a1call View Post
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
a1call is online now   Reply With Quote
Old 2022-08-17, 21:27   #15
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,413 Posts
Default

Quote:
Originally Posted by ryanp View Post
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
ATH is offline   Reply With Quote
Old 2022-08-18, 00:11   #16
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,329 Posts
Default

Quote:
Originally Posted by ATH View Post
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 2p2 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 )
Batalov is offline   Reply With Quote
Old 2022-08-18, 05:18   #17
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,413 Posts
Default

You can trial factor 2p^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 is offline   Reply With Quote
Old 2022-08-18, 08:24   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1101010101012 Posts
Default

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

Last fiddled with by ATH on 2022-08-18 at 08:25
ATH is offline   Reply With Quote
Old 2022-08-19, 01:27   #19
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72·47 Posts
Default

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)

Last fiddled with by a1call on 2022-08-19 at 02:14
a1call is online now   Reply With Quote
Old 2022-08-19, 20:49   #20
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

270316 Posts
Default

Quote:
Originally Posted by ATH View Post
You can trial factor 2p^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.
Batalov is offline   Reply With Quote
Old 2022-08-20, 05:55   #21
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72×47 Posts
Default

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.
a1call is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
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
generalized minimal (probable) primes sweety439 sweety439 139 2022-04-23 20:44
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

All times are UTC. The time now is 15:31.


Tue Nov 29 15:31:03 UTC 2022 up 103 days, 12:59, 1 user, load averages: 1.42, 1.06, 1.01

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔