mersenneforum.org Probable primes of the form (2^(p^2)-1) / (2^p-1)
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-14, 19:59 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 230310 Posts Probable primes of the form (2^(p^2)-1) / (2^p-1) Hey all, Are primes of the form: (2^(p^2)-1) / (2^p-1) Where p is a prime number. Example: p=7 => 4432676798593 Studied/Researched? If so how are they referred to as? Are there any known shortcut-deterministic-primality tests specifically geared for them? Thanks in advance. ETA: I did google 4432676798593 https://numbermatics.com/n/4432676798593/ https://metanumbers.com/4432676798593 Last fiddled with by a1call on 2022-08-14 at 20:09
2022-08-14, 20:29   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,329 Posts

Quote:
 Originally Posted by a1call If so how are they referred to as?
One specific case of cyclotomic. Phip^2(2), or equivalently, Phip(2p): A156585
Also with generalization, Phip(ap), where a>2, will produce some hits.
Quote:
 Originally Posted by a1call Are there any known shortcut-deterministic-primality tests specifically geared for them?
For any interestingly large numbers, - No. They will be large PRPs. The PRP test will have decent speed if prepared with TLC.
(For any p>>3; the "small" ones could get some chance of luck in factoring N-1 and/or, of course, ECPP.)

 2022-08-14, 21:05 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 72×47 Posts Thank you Batalov for the reply. Phi function is foreign to me. I will try to read about it. Is the 59 yield, the largest known Prime/PRP of the form (as listed in the eois)? ETA: It seems to me that all the factors must be of the form 2kp^2+1 but I haven't ran any codes to verify, so I could be wrong. Last fiddled with by a1call on 2022-08-14 at 21:51
 2022-08-14, 21:26 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 998710 Posts There are some larger ones, e.g.: (130^6889-1)/(130^83-1) and (200^10201-1)/(200^101-1) (250^18769-1)/(250^137-1) (263^16129-1)/(263^127-1) (315^9409-1)/(315^97-1) (1155^10609-1)/(1155^103-1) (and these are not new in FactorDB; someone had clearly searched for them before) But not for a=2: as you can see in OEIS, ATH searched it until 1999 at least. And this sequence may not have any other terms, it would be expected to be finite.
 2022-08-14, 21:35 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 72·47 Posts Thanks for the quick research sir. Perhaps I will use this thread to list the PRP's at some point and ask for an update on the oeis since AFAIK they do not distinguish PRP'S from Primes..
2022-08-14, 21:55   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

230310 Posts

Quote:
 Originally Posted by Batalov But not for a=2: as you can see in OEIS, ATH searched it until 1999 at least. And this sequence may not have any other terms, it would be expected to be finite.
Acknowledged with thanks.

 2022-08-16, 15:50 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts Found a newer, larger one (was not in factorDB and big enough for PRPtop) - (1126^24649-1)/(1126^157-1) (74739 digits)
2022-08-16, 18:53   #8
ryanp

Jun 2012
Boulder, CO

32·47 Posts

Quote:
 Originally Posted by Batalov One specific case of cyclotomic. Phip^2(2), or equivalently, Phip(2p): A156585 Also with generalization, Phip(ap), where a>2, will produce some hits. For any interestingly large numbers, - No. They will be large PRPs. The PRP test will have decent speed if prepared with TLC. (For any p>>3; the "small" ones could get some chance of luck in factoring N-1 and/or, of course, ECPP.)
Interesting. What software can test these efficiently? e.g. I don't see a way to specify (2^(p^2)-1)/(2^p-1) in LLR documentation:

Code:
    - Moreover, LLR accepts these ABC FORMAT DESCRIPTORS :

- Two numbers per data line formats :

- Fixed k and c : ABC%d*$a^$b+%d or ABC%d*$a^$b-%d
- Fixed b and c : ABC$a*%d^$b+%d or ABC$a*%d^$b-%d
- Fixed n and c : ABC$a*$b^%d+%d or ABC$a*$b^%d-%d

- Three numbers per data line formats :

- Fixed k : ABC%d*$a^$b$c - Fixed b : ABC$a*%d^$b$c
- Fixed n : ABC$a*$b^%d$c - Fixed c : ABC$a*$b^$c+%d or ABC$a*$b^$c-%d - General k*b^n+c format (four numbers per data line) : - ABC$a*$b^$c$d - Some special ABC formats : - ABC$a^$b+1 : Generalized Fermat candidates - ABC4^$a+1 : Gaussian-Mersenne norm candidates
- ABC$a^$b-$a^$c-1 : a^b-a^c-1 candidates
- ABC$a^$b-$a^$c+1 : a^b-a^c+1 candidates
- ABC(2^$a+1)/3 : Wagstaff PRP candidates - ABC(10^$a-1)/9 : Repunits PRP candidates
- ABC($a^$b-1)/($a-1) : Generalized Repunits PRP candidates - ABC$a*$b^$a$c : (Generalized) Cullen/Woodall candidates - ABC(2^$a$b)^2-2 : near-square (ex-Carol/Kynea) candidates - ABC$a$b$c : Used to launch a Wieferich prime search,
the range being $b to$b and the base $c (new feature!) - ABC$a$b : Used to test a Wieferich prime candidate$a, base $b - ABC$a : General APR-CL primality test of number $a  2022-08-16, 22:03 #9 Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 270316 Posts I vaguely remember coding something into a patch to P95 (and then George vetted it and merged it to the trunk). The idea was to simplify the "task description". But I think it was only for Phi(a*b,n) values (where a and b are primes, and a is likely small, probably like 3 or 5) that could be added to worktodo.txt as PRP=...,1,n,a*b,-1,..."1" and P95 on the fly would factor out gcd(n^a-1,N) and gcd(n^b-1,N), leaving the wanted value Phi(a*b,n). I will have to search for old notes.... But I am quite certain that what can be done with P95 as is, -- is this: PRP=...,1,n,a^2,-1,..."F" and instead of F, insert its externally computed n^a-1, which will be reasonably small especially if n=2. Then one could extend Andreas' search of Phi(a^2,2) for a>=1999. It is possible that LLR will also accept the same, but it is best to check its source, how long its internal buffer is to read value of "e" */ ABC ($a*$b^$c$d)/$e 1 2 4012009 -1 9185045562194<<..insert the rest of 2^2003-1 here...>>35007 Something like that. And threaded call will work. If it works - then LLR and P95 will be as fast as the usual test. Because this is implemented as doing everything in nice FFT and then do just one gcd at the end using bigints. ________________ */ this is a hidden form, but known to many. I think it is forgotten from "-h" output but it is hidden in readme.txt, and also discovered by "strings sllr" (this gets text-like strings from a binary.
 2022-08-16, 22:26 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts P.S. (which is a bit different and deserves a separate post) Phi(3*p,b) is also easily shown to be identical to Phi(3,b^p), which in turn is frequently 'simplified' to avoid Phi() b2p - bp + 1. That would be not a PRP (if it passes PRP test; just don't use "b" for the PRPbase, esp if b=3), no, it will be a proven prime! ...and if we further generalize from prime p to p {a 2- or 3-smooth number} may need to * be divided by 2 or 3 for positive b - see here * or -b^p should be negative power with exponent a power of 2, or 3-smooth - see here
2022-08-17, 00:03   #11
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

72×47 Posts

FTR my hunch about the format of all factors seems to have been correct which at the least should facilitate the sieving.

Quote:
 \\ EPP-200-A ExpPower1=2 subtrExpPBy =1 ExpPower2=ExpPower1-subtrExpPBy a=2 forprime(q=2,13,{ 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(p-1,q)); ); })

Quote:
 (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 = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 valuation = 3 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 = 4 valuation = 4 valuation = 4

 Similar Threads Thread Thread Starter Forum Replies Last Post kijinSeija Math 0 2022-05-13 20:32 sweety439 sweety439 139 2022-04-23 20:44 enzocreti enzocreti 5 2020-03-01 02:10 enzocreti enzocreti 0 2019-07-15 13:12 philmoore Five or Bust - The Dual Sierpinski Problem 388 2019-03-01 04:30

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

Tue Nov 29 15:49:27 UTC 2022 up 103 days, 13:18, 0 users, load averages: 0.81, 0.99, 0.98