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

24·3 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

2×3×7 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

929 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×3×7 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

2·3·7 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

929 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

528 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

528 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

2×3×7 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
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 05:31.


Mon Dec 5 05:31:54 UTC 2022 up 109 days, 3 hrs, 0 users, load averages: 1.07, 0.98, 1.07

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.

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