mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Wagstaff PRP Search (https://www.mersenneforum.org/forumdisplay.php?f=102)
-   -   A new Wagstaff PRP test ? (https://www.mersenneforum.org/showthread.php?t=27352)

JCoveiro 2022-02-09 01:28

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,[/CODE]

JCoveiro 2022-02-09 01:54

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,[/CODE]

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,[/CODE]

kijinSeija 2022-08-14 15:37

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

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

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

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

You can run the test here : [url]https://sagecell.sagemath.org/?z=eJxtj7FuxCAQRPuT7h9WrhYH5ECKFGTzB3Hj9nQS9nEyEj6QIYny91n7ohRRGmYYDQ-NI2UsnE7QOiAwkFZQpj0eMunne768lwqjh7yGxYO7XeAVtkZPqNw5Ky06Niz2eIj0xOdAb-mCUfZbNNWVNOvnHKJHvr1QlgOZNqc4zX78KrP_QDcWdEJqOXRGWG490A4smmK4VtyAg_r3keLfd9PtXoszYlb4mwkmMjhu0osNGq7IXHqUPOlW8c8MYe9xsw9uxE-rmdKSUwmVI2G_AQMYVjg=&lang=gp&interacts=eJyLjgUAARUAuQ==[/url]

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 :smile:

T.Rex 2022-08-15 14:47

[QUOTE=kijinSeija;611393]Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions :

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

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

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

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 :smile:[/QUOTE]
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)

kijinSeija 2022-08-15 15:47

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
[/CODE]

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
[/CODE]

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)}[/CODE]

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)

kijinSeija 2022-08-15 21:15

[TEX]S_{0} = 7[/TEX] not [TEX]3[/TEX] sorry for the mistake

T.Rex 2022-08-16 07:47

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

kijinSeija 2022-08-20 21:23

New property ?
 
Maybe I found a new property about the Reix conjecture :

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

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

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

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
[/CODE]

I don't know if T.Rex has noticed that before, we now have something for the conjecture for [TEX]S_{p-2}[/TEX], like the Lucas-Lehmer test for Mersenne numbers.

kijinSeija 2022-08-21 18:53

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 :

[TEX]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[/TEX]

And it seems than [TEX]W_q[/TEX] is prime only if it divides [TEX]G_{q-2}[/TEX] 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 :grin:

kijinSeija 2022-08-25 13:22

New formula
 
I checked with this formula

[TEX]$\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})}$[/TEX]

And it seems than [TEX]$\omega \equiv 0 (mod W_p)$[/TEX] only if [TEX]$W_p$[/TEX] 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. :grin:


All times are UTC. The time now is 01:30.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.