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 5·467 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

89×113 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 233510 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 89×113 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 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..
2022-08-14, 21:55   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

5×467 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 89×113 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

52×17 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 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^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 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() 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

233510 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 sweety439 sweety439 140 2022-12-20 07:08 kijinSeija Math 0 2022-05-13 20:32 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:01.

Thu Feb 2 15:01:22 UTC 2023 up 168 days, 12:29, 1 user, load averages: 0.83, 0.94, 0.98

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.

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