20220814, 19:59  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5·467 Posts 
Probable primes of the form (2^(p^2)1) / (2^p1)
Hey all,
Are primes of the form: (2^(p^2)1) / (2^p1) Where p is a prime number. Example: p=7 => 4432676798593 Studied/Researched? If so how are they referred to as? Are there any known shortcutdeterministicprimality 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 20220814 at 20:09 
20220814, 20:29  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89×113 Posts 
One specific case of cyclotomic. Phi_{p^2}(2), or equivalently, Phi_{p}(2^{p}): A156585
Also with generalization, Phi_{p}(a^{p}), where a>2, will produce some hits. Quote:
(For any p>>3; the "small" ones could get some chance of luck in factoring N1 and/or, of course, ECPP.) 

20220814, 21:05  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2335_{10} 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 20220814 at 21:51 
20220814, 21:26  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89×113 Posts 
There are some larger ones, e.g.:
(130^68891)/(130^831) and (200^102011)/(200^1011) (250^187691)/(250^1371) (263^161291)/(263^1271) (315^94091)/(315^971) (1155^106091)/(1155^1031) (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. 
20220814, 21:35  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5×467 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.. 
20220814, 21:55  #6 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5×467 Posts 

20220816, 15:50  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89×113 Posts 
Found a newer, larger one (was not in factorDB and big enough for PRPtop) 
(1126^246491)/(1126^1571) (74739 digits) 
20220816, 18:53  #8  
Jun 2012
Boulder, CO
5^{2}×17 Posts 
Quote:
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 : GaussianMersenne norm candidates  ABC$a^$b$a^$c1 : a^ba^c1 candidates  ABC$a^$b$a^$c+1 : a^ba^c+1 candidates  ABC(2^$a+1)/3 : Wagstaff PRP candidates  ABC(10^$a1)/9 : Repunits PRP candidates  ABC($a^$b1)/($a1) : Generalized Repunits PRP candidates  ABC$a*$b^$a$c : (Generalized) Cullen/Woodall candidates  ABC(2^$a$b)^22 : nearsquare (exCarol/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 APRCL primality test of number $a 

20220816, 22:03  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89×113 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^a1,N) and gcd(n^b1,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^a1, 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^20031 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 textlike strings from a binary. 
20220816, 22:26  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89·113 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() b^{2p}  b^{p} + 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 3smooth 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 3smooth  see here 
20220817, 00:03  #11  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2335_{10} Posts 
FTR my hunch about the format of all factors seems to have been correct which at the least should facilitate the sieving.
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
generalized minimal (probable) primes  sweety439  sweety439  140  20221220 07:08 
Probable primality test for numbers of the form (10^n1)/92 and (10^n+1)/112 ?  kijinSeija  Math  0  20220513 20:32 
Primes of the form 30*n^21  enzocreti  enzocreti  5  20200301 02:10 
pg primes of the form 41s+r  enzocreti  enzocreti  0  20190715 13:12 
The probable primes  philmoore  Five or Bust  The Dual Sierpinski Problem  388  20190301 04:30 