mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Wagstaff PRP Search

Reply
 
Thread Tools
Old 2022-02-09, 01:28   #12
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

4810 Posts
Thumbs up more wagstaff simplifications

t3(q)={w=(2^q+1)/3;s=4;for(i=1,q,s=(s^2-2)%(6*w););if(s==14||s==194,print1(q","))}
forprime(x=1,100000,t3(x))

Code:
3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,1709,2617,3539,
JCoveiro is offline   Reply With Quote
Old 2022-02-09, 01:54   #13
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

24×3 Posts
Default more simplifications (2)

t3(q)={w=(2^q+1)/3;s=4;for(i=2,q,s=(s^2-2)%(6*w));if(ispowerful(s+2),print1(q","))}
forprime(x=1,1000,t3(x))

Code:
3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,
or

t3(q)={w=(2^q+1)/3;s=4;for(i=2,q,s=(s^2-2)%(6*w));if(issquare(s+2),print1(q","))}
forprime(x=1,1000,t3(x))

Code:
3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,

Last fiddled with by JCoveiro on 2022-02-09 at 02:00
JCoveiro is offline   Reply With Quote
Old 2022-08-14, 15:37   #14
kijinSeija
 
Mar 2021
France

1100102 Posts
Default

Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions :

Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers

Let the sequence S_i = 2 \cdot T_{|a|}(S_{i-1}/2) where T_{n}(x) is the Chebyshev's polynomial of the first kind with $S_0 = 3$

$N$ is prime if S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)

You can run the test here : https://sagecell.sagemath.org/?z=eJx...yLjgUAARUAuQ==

Do you think if it's possible to prove it ? It was provable for the classic Lucas-Lehmer test, so maybe it is provable with this test too, I didn't found any counterexample for the moment
kijinSeija is offline   Reply With Quote
Old 2022-08-15, 14:47   #15
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16458 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions :

Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers

Let the sequence S_i = 2 \cdot T_{|a|}(S_{i-1}/2) where T_{n}(x) is the Chebyshev's polynomial of the first kind with $S_0 = 3$

$N$ is prime if S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)

Do you think if it's possible to prove it ? It was provable for the classic Lucas-Lehmer test, so maybe it is provable with this test too, I didn't found any counterexample for the moment
Interesting.
I'll have a deeper look asap.
Maybe you could replace all "-" signs in N by "+" signs.
And give details about each of Wagstaff and Mersenne cases: computed values for small p and the complete and simplified formula for each case.
How far did you test?
(I have no PC with me now)

Last fiddled with by T.Rex on 2022-08-15 at 14:48
T.Rex is offline   Reply With Quote
Old 2022-08-15, 15:47   #16
kijinSeija
 
Mar 2021
France

2·52 Posts
Default

For Wagstaff Numbers :

Code:
? forprime(q=3,200, print(t(q)))
q:3 ,w: 3
 s1=0

q:5 ,w: 11
 s1=0

q:7 ,w: 43
 s1=0

q:11 ,w: 683
 s1=0

q:13 ,w: 2731
 s1=0

q:17 ,w: 43691
 s1=0

q:19 ,w: 174763
 s1=0

q:23 ,w: 2796203
 s1=0

q:29 ,w: 178956971
 s1=35462304

q:31 ,w: 715827883
 s1=0

q:37 ,w: 45812984491
 s1=22633578773

q:41 ,w: 733007751851
 s1=237058155852

q:43 ,w: 2932031007403
 s1=0

q:47 ,w: 46912496118443
 s1=43837675287567

q:53 ,w: 3002399751580331
 s1=2323597922301294

q:59 ,w: 192153584101141163
 s1=43405475675237573

q:61 ,w: 768614336404564651
 s1=0

q:67 ,w: 49191317529892137643
 s1=18491486101210104962

q:71 ,w: 787061080478274202283
 s1=672936394093447809238

q:73 ,w: 3148244321913096809131
 s1=1795244001282278966829

q:79 ,w: 201487636602438195784363
 s1=0

q:83 ,w: 3223802185639011132549803
 s1=575962240197809829006347

q:89 ,w: 206323339880896712483187371
 s1=101697903320160405940678618

q:97 ,w: 52818775009509558395695966891
 s1=47418661886717800473597639812

q:101 ,w: 845100400152152934331135470251
 s1=0

q:103 ,w: 3380401600608611737324541881003
 s1=2163853741122871996993570309177

q:107 ,w: 54086425609737787797192670096043 s1=40984583554059445857015264239417

q:109 ,w: 216345702438951151188770680384171 s1=48553388173305748538138563460025

q:113 ,w: 3461531239023218419020330886146731 s1=1501577949756601699943132034371628

q:127 ,w: 56713727820156410577229101238628035243
 s1=0

q:131 ,w: 907419645122502569235665619818048563883 s1=675255604002653037167762564789642028717

q:137 ,w: 58074857287840164431082599668355108088491
 s1=29782361227426807280197948853870970493442

q:139 ,w: 232299429151360657724330398673420432353963 s1=180823998115931831437870551556753357923954

q:149 ,w: 237874615450993313509714328241582522730457771 s1=26502703015677001084529847262630194280688763

q:151 ,w: 951498461803973254038857312966330090921831083 s1=767834026054558051499460097360371231864912320

q:157 ,w: 60895901555454288258486868029845125818997189291 s1=22758383762731006210941976567879889094160008662

q:163 ,w: 3897337699549074448543159553910088052415820114603 s1=3147755244116520759735228945070115202448119192873

q:167 ,w: 62357403192785191176690552862561408838653121833643
 s1=0

q:173 ,w: 3990873804338252235308195383203930165673799797353131 s1=3773380018331381359874134732369509944603170792643824

q:179 ,w: 255415923477648143059724504525051530603123187030600363 s1=90278170195369259663664519328330687398992158859609666

q:181 ,w: 1021663693910592572238898018100206122412492748122401451 s1=25275761152202162177068118911776013172313057421921272

q:191 ,w: 1046183622564446793972631570534611069350392574077339085483
 s1=0

q:193 ,w: 4184734490257787175890526282138444277401570296309356341931 s1=490498661136809600403936047657568663261295050600166752926

q:197 ,w: 66955751844124594814248420514215108438425124740949701470891 s1=35495427703180153027963472585444260458023196834276102776577

q:199 ,w: 267823007376498379256993682056860433753700498963798805883563
 s1=0
For Mersenne numbers :

Code:
? forprime(q=3,200, print(t(q)))
q:3 ,w: 7
 s1=0

q:5 ,w: 31
 s1=0

q:7 ,w: 127
 s1=0

q:11 ,w: 2047
 s1=1607

q:13 ,w: 8191
 s1=0

q:17 ,w: 131071
 s1=0

q:19 ,w: 524287
 s1=0

q:23 ,w: 8388607
 s1=815074

q:29 ,w: 536870911
 s1=289611393

q:31 ,w: 2147483647
 s1=0

q:37 ,w: 137438953471
 s1=62131939238

q:41 ,w: 2199023255551
 s1=143549775376

q:43 ,w: 8796093022207
 s1=7551383590233

q:47 ,w: 140737488355327
 s1=52891699560247

q:53 ,w: 9007199254740991
 s1=8366824338705290

q:59 ,w: 576460752303423487
 s1=358615917252629447

q:61 ,w: 2305843009213693951
 s1=0

q:67 ,w: 147573952589676412927
 s1=67009295408650361316

q:71 ,w: 2361183241434822606847
 s1=1735688411577756295226

q:73 ,w: 9444732965739290427391
 s1=30922976274147574010

q:79 ,w: 604462909807314587353087
 s1=290547409084571062280606

q:83 ,w: 9671406556917033397649407
 s1=2165342894805439856382527

q:89 ,w: 618970019642690137449562111
 s1=0

q:97 ,w: 158456325028528675187087900671
 s1=31771632134636405756544106260

q:101 ,w: 2535301200456458802993406410751
 s1=1336439533263272606812194950146

q:103 ,w: 10141204801825835211973625643007
 s1=1509296843045822788662294171957

q:107 ,w: 162259276829213363391578010288127
 s1=0

q:109 ,w: 649037107316853453566312041152511
 s1=556884570374941377547115102393166

q:113 ,w: 10384593717069655257060992658440191
 s1=5068074721493003956791340784974471

q:127 ,w: 170141183460469231731687303715884105727
 s1=0

q:131 ,w: 2722258935367507707706996859454145691647
 s1=1516757122616911896094254191049737051849

q:137 ,w: 174224571863520493293247799005065324265471
 s1=163842583007416170909821893382414965645556

q:139 ,w: 696898287454081973172991196020261297061887
 s1=46705198311407299245440149148266534783772

q:149 ,w: 713623846352979940529142984724747568191373311
 s1=561891623480948338529701112067154730490230926

q:151 ,w: 2854495385411919762116571938898990272765493247
 s1=2829464711188493325175801501249655843781087386

q:157 ,w: 182687704666362864775460604089535377456991567871
 s1=100673681739430680947486076923530912740937570376

q:163 ,w: 11692013098647223345629478661730264157247460343807
 s1=11368492991431645161264116930802833588285449233837

q:167 ,w: 187072209578355573530071658587684226515959365500927
 s1=30366014861212227154107279163299712464685645481638

q:173 ,w: 11972621413014756705924586149611790497021399392059391
 s1=3258300855337674590876910647524040908033118687155945

q:179 ,w: 766247770432944429179173513575154591809369561091801087
 s1=88996800370430364572446925655732968627245182062583665

q:181 ,w: 3064991081731777716716694054300618367237478244367204351
 s1=2873106258197702872144284527457473447108057424250030158

q:191 ,w: 3138550867693340381917894711603833208051177722232017256447
s1=782801006335836471924253266478273673553323419418577508933

q:193 ,w: 12554203470773361527671578846415332832204710888928069025791
s1=510009340455423487745953843163838674653030967481885342349

q:197 ,w: 200867255532373784442745261542645325315275374222849104412671
s1=177512020029058784941440331206388581089073179204650354567171

q:199 ,w: 803469022129495137770981046170581301261101496891396417650687
s1=229107978040452740359342358033137472971457177405266811118373
I checked until p = 1000 and I didn't find counterexample. I will check higher later.

For the code I used this one on Pari GP
Code:
t(q)={a=-2;w=(-a^q-1)/(-a-1);l=3;S0=2*polchebyshev(abs(a),1,l/2);print("q:",q," ,w: ",w);S=S0;for(i=1,q-1,S=Mod(sum(k=0, floor(abs(a)/2), (-1)^k*abs(a)/(abs(a)-k)*binomial(abs(a)-k,k)*(S)^(abs(a)-2*k)) ,w));s1=lift(Mod(S-2*polchebyshev(abs(a)-(-abs(a)/a)-(-1)^((q-(abs(a)/a))/2),1,l/2),w));print(" s1=",s1)}
I use Chebyshev functions instead of S^2-2, because I check some Generalized Wagstaff and Mersenne numbers (a^p-1)/(a-1) and (a^p+1)/(a+1)

Last fiddled with by kijinSeija on 2022-08-15 at 15:50
kijinSeija is offline   Reply With Quote
Old 2022-08-15, 21:15   #17
kijinSeija
 
Mar 2021
France

628 Posts
Default

S_{0} = 7 not 3 sorry for the mistake

Last fiddled with by kijinSeija on 2022-08-15 at 21:16
kijinSeija is offline   Reply With Quote
Old 2022-08-16, 07:47   #18
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16458 Posts
Default

That reminds me this: https://arxiv.org/pdf/2010.02677.pdf

Last fiddled with by T.Rex on 2022-08-16 at 07:47
T.Rex is offline   Reply With Quote
Old 2022-08-20, 21:23   #19
kijinSeija
 
Mar 2021
France

628 Posts
Talking New property ?

Maybe I found a new property about the Reix conjecture :

Let W_p = (2^p+1)/3 where p is a prime number >3

Let the sequence S_i = S_{i-1}^2-2 with S_0 = 1/4 = (2^{(p-2)}+1)/3

W_p is prime if S_{p-2} \equiv (W_p-1)/2+2 \equiv 2 \cdot S_0 + 1

The Pari GP code to check the conjecture :

Code:
 t(q)={w=(2^q+1)/3;S0=1/4;print("w: ",w);S=S0;for(i=1,q-2,S=Mod(S^2-2,w));s1=lift(Mod(S-((w-1)/2+2),w));print(s1," ")}

? forprime(q=3,200,(t(q)))
q: 3 w: 3
2
q: 5 w: 11
0
q: 7 w: 43
0
q: 11 w: 683
0
q: 13 w: 2731
0
q: 17 w: 43691
0
q: 19 w: 174763
0
q: 23 w: 2796203
0
q: 29 w: 178956971
148328604
q: 31 w: 715827883
0
q: 37 w: 45812984491
24013210652
q: 41 w: 733007751851
578666895402
q: 43 w: 2932031007403
0
q: 47 w: 46912496118443
45479133625061
q: 53 w: 3002399751580331
582220641320127
q: 59 w: 192153584101141163
149471670618762341
q: 61 w: 768614336404564651
0
q: 67 w: 49191317529892137643
29433794893490190258
q: 71 w: 787061080478274202283
341602215950445231784
q: 73 w: 3148244321913096809131
2588298572977432531241
q: 79 w: 201487636602438195784363
0
q: 83 w: 3223802185639011132549803
2941972935918702317448471
q: 89 w: 206323339880896712483187371
66974682110145709677667101
q: 97 w: 52818775009509558395695966891
49692803662195088107287524127
q: 101 w: 845100400152152934331135470251
0
q: 103 w: 3380401600608611737324541881003
1617593003444420535702916633129
q: 107 w: 54086425609737787797192670096043
5672753555637487782056481655731
q: 109 w: 216345702438951151188770680384171
194118643299931373894593838136116
q: 113 w: 3461531239023218419020330886146731
1019543448087266479215549595100475
q: 127 w: 56713727820156410577229101238628035243
0
q: 131 w: 907419645122502569235665619818048563883
314277216384605587120839967100937178478
q: 137 w: 58074857287840164431082599668355108088491
24778318022691375721663916596760266302224
q: 139 w: 232299429151360657724330398673420432353963
57382243707830577855987457895453136163716
q: 149 w: 237874615450993313509714328241582522730457771
93176910676270118136233263825222545067689724
q: 151 w: 951498461803973254038857312966330090921831083
648060689992125350030081556538812233582203959
q: 157 w: 60895901555454288258486868029845125818997189291
35630434179621771049596888226219699913450832505
q: 163 w: 3897337699549074448543159553910088052415820114603
2317790472758544518337676019136175860599583513335
q: 167 w: 62357403192785191176690552862561408838653121833643
0
q: 173 w: 3990873804338252235308195383203930165673799797353131
371011654722662023999926776710944629956493639282711
q: 179 w: 255415923477648143059724504525051530603123187030600363
55745571531645367720541050873662338089610309630076893
q: 181 w: 1021663693910592572238898018100206122412492748122401451
1009891773589539741838500595408129006958987617245584039
q: 191 w: 1046183622564446793972631570534611069350392574077339085483
0
q: 193 w: 4184734490257787175890526282138444277401570296309356341931
3928658498611840039653581597148870081532859834159865883500
q: 197 w: 66955751844124594814248420514215108438425124740949701470891
7375405652987315748567955736547475635383458586082124230435
q: 199 w: 267823007376498379256993682056860433753700498963798805883563
0
I don't know if T.Rex has noticed that before, we now have something for the conjecture for S_{p-2}, like the Lucas-Lehmer test for Mersenne numbers.
kijinSeija is offline   Reply With Quote
Old 2022-08-21, 18:53   #20
kijinSeija
 
Mar 2021
France

2·52 Posts
Default

Inspired by Reix conjecture, I think I found a formula that divides only Wagstaff primes numbers and not the composite Wagstaff numbers :

The formula is :

G_n = 4^{2^n} \cdot ((1/8 - 1/8 (3 i sqrt(7)))^{(2^n)} + (1/8 + 1/8 (3 i sqrt(7)))^{(2^n)}) + 3

And it seems than W_q is prime only if it divides G_{q-2} when q > 3

For example :

G_3 = 70532 and it divides W_5 = 11
G_5 = -23820962743960351228 and it divides W_7 = 43
G_7 doesn't divide W_9 = 171
G_9 divides W_11 = 683
G_11 divides W_13 = 2731
G_13 doesn't divides W_15 = 10923
G_15 divides W_17 = 43691
G_17 divides W_19

Etc.

It looks like the Lucas-Lehmer test can works with the seed 1/4

Last fiddled with by kijinSeija on 2022-08-21 at 18:54
kijinSeija is offline   Reply With Quote
Old 2022-08-25, 13:22   #21
kijinSeija
 
Mar 2021
France

5010 Posts
Default New formula

I checked with this formula

$\omega = (\frac{1}{2} (1 + i \sqrt7))^{(\frac{2^{p - 1} - 1}{3})} + (\frac{1}{2} (1 - i \sqrt7))^{(\frac{2^{p - 1} - 1}{3})}$

And it seems than $\omega \equiv 0 (mod W_p)$ only if $W_p$ is prime but the numbers of the formula are growing very fast so I can't check for big numbers.

For p>3

But maybe this is promising, let's find a sequence now if it possible.

Last fiddled with by kijinSeija on 2022-08-25 at 13:31
kijinSeija is offline   Reply With Quote
Old 2023-01-01, 23:07   #22
kijinSeija
 
Mar 2021
France

2×52 Posts
Default Lucas-Lehmer test using 2^p+1 for Wagstaff numbers

Hello

All the last test were using  P=(2^p+1)/3 but  P-1 and  P+1 can't be factorised easily, so apparently LLT can't be used, I read that from some papers (I don't really understand that, if someone can explain me this, it would be very nice )

But I tried some new test with P=2^p+1 for testing if Wagstaff numbers are probable prime and I found maybe something interesting :

Let  Np=2^p+1 and  Wp=(2^p+1)/3 for Wagstaff numbers with p a prime number > 3.

Then W_p is prime if S_{p-2} \equiv 10 \cdot S_0 - 1 (mod N_p) and p \equiv 2 (mod 3) or S_{p-2} \equiv 2 \cdot S_0 + 1 (mod N_p) and p \equiv 1 (mod 3)

for example with p = 17 we get this on PARI/GP :

Code:
    Mod(10923, 131073)
    Mod(35497, 131073)
    Mod(32258, 131073)
    Mod(121088, 131073)
    Mod(84743, 131073)
    Mod(17450, 131073)
    Mod(19919, 131073)
    Mod(8588, 131073)
    Mod(90716, 131073)
    Mod(105422, 131073)
    Mod(118412, 131073)
    Mod(129713, 131073)
    Mod(14576, 131073)
    Mod(121514, 131073)
    Mod(16598, 131073)
    Mod(109229, 131073)
17 \equiv 2 (mod 3) and we get 10 \cdot (2^{17-2}+1)/3 - 1 at the last residue and (2^{17}+1)/3 = 43691 and this is indeed prime.

This is interesting because N_p - 1 is can be factorised easily (so LLT can be used ?)

I have checked until p = 10000 and I didn't find any counterexamples and I have checked with higher Wagstaff exponent too and it seems it works.

Do you think it's easier to prove it when you can use P-1 as a modulo for the test ?

Thanks in advance
kijinSeija is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Another Wagstaff PRP Test paulunderwood Wagstaff PRP Search 10 2022-03-31 04:19
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness GP2 Wagstaff PRP Search 414 2020-12-27 08:11
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Wagstaff number primality test? ixfd64 Math 12 2010-01-05 16:36

All times are UTC. The time now is 17:19.


Mon Feb 6 17:19:47 UTC 2023 up 172 days, 14:48, 1 user, load averages: 0.76, 1.01, 1.03

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

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