mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-08-14, 19:59   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,153 Posts
Default 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
a1call is offline   Reply With Quote
Old 2022-08-14, 20:29   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

270616 Posts
Default

Quote:
Originally Posted by a1call View Post
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 View Post
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.)
Batalov is offline   Reply With Quote
Old 2022-08-14, 21:05   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

90216 Posts
Default

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
a1call is offline   Reply With Quote
Old 2022-08-14, 21:26   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234068 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2022-08-14, 21:35   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

90216 Posts
Default

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

2×1,153 Posts
Default

Quote:
Originally Posted by Batalov View Post

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.
a1call is offline   Reply With Quote
Old 2022-08-16, 15:50   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×5×37 Posts
Default

Found a newer, larger one (was not in factorDB and big enough for PRPtop) -
(1126^24649-1)/(1126^157-1) (74739 digits)
Batalov is offline   Reply With Quote
Old 2022-08-16, 18:53   #8
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

32×47 Posts
Default

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

100111000001102 Posts
Cool

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.
Batalov is offline   Reply With Quote
Old 2022-08-16, 22:26   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·5·37 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2022-08-17, 00:03   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,153 Posts
Default

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




a1call is offline   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 18:24.


Tue Dec 6 18:24:47 UTC 2022 up 110 days, 15:53, 0 users, load averages: 0.94, 1.01, 0.91

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.

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