View Single Post
Old 2015-09-09, 20:41   #23
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39A16 Posts
Default

Here is a modified code that shows the pseudoprimes such that N=0 mod(2*c-1) :
Code:
CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn,
     y=Mod(N,2*c-1);
     if(!isprime(N),
          print1(k,"*2^",n,"+",c," : ");
          if(y==0,
                Nf=factor(N/(2*c-1)); print(Nf),
                print("New kind of pseudoprime !")
          )
     )
)
);
}
And here is the result, showing that these pseudoprimes are of a special kind since they all are: N=(2*c-1)*P where P is prime.

Code:
for(k=0,200,for(c=0,100,CEk2c(2*k+1,2*c+1,200)))

1*2^3+1 :      Mat([3, 2])
15*2^3+1 :     Mat([11, 2])
27*2^158+25 :  Mat([201329307183338667303568828996630824136276421737, 1])
33*2^79+25 :   Mat([407087265788599620054121, 1])
35*2^83+17 :   Mat([10257552408851399058113009, 1])
37*2^92+17 :   Mat([5551973509522311535911223793, 1])
41*2^141+17 :  Mat([3463373307347558896980925943858268264186353, 1])
45*2^3+1 :     Mat([19, 2])
49*2^80+17 :   Mat([1795071671548994835169777, 1])
67*2^144+41 :  Mat([18446295411130268524480162027993089146922073, 1])
91*2^166+17 :  Mat([257932895024702381685401832295140372923519731220977, 1])
91*2^196+17 :  Mat([276953337173424460368027557581526130358940288701201037902321, 1])
95*2^77+17 :   Mat([435030124482537013625329, 1])
95*2^197+17 :  Mat([578254220471985137032145449895494118331853350035474694521329, 1])
97*2^48+17 :   Mat([827365840634353, 1])
131*2^69+17 :  Mat([2343295489605770920433, 1])
153*2^150+73 : Mat([1505992392993185253806329333281191419769380921, 1])
163*2^38+17 :  Mat([1357730267633, 1])
169*2^42+17 :  Mat([22523329102321, 1])
169*2^142+17 : Mat([28551711655694509931208609000587674958414321, 1])
171*2^147+25 : Mat([622600396563059029747364542795570582452677737, 1])
173*2^121+17 : Mat([13936754137623663394688401298696946161, 1])
191*2^151+41 : Mat([6730970600168847834126731362095149902447027289, 1])
197*2^169+17 : Mat([4467057610537702786112014150518035469532605454991857, 1])
215*2^35+17 :  Mat([223858901489, 1])
229*2^38+17 :  Mat([1907486081521, 1])
229*2^108+17 : Mat([2251962084478173346464931173089777, 1])
229*2^188+17 : Mat([2722455108718844497951507155141203805468635221178530120177, 1])
231*2^3+1 :    Mat([43, 2])
235*2^62+17 :  Mat([32840794373649580529, 1])
235*2^182+17 : Mat([43652903285270773541116551682463352503079235601593516529, 1])
295*2^78+17 :  Mat([2701766036259966716199409, 1])
295*2^198+17 : Mat([3591263053457591903673324373035173998060983963378211260711409, 1])
299*2^163+17 : Mat([105936724742288478192218609692646938879302746751473, 1])
305*2^41+17 :  Mat([20324305846769, 1])
305*2^101+17 : Mat([23432329276946058633726938038769, 1])
329*2^179+17 : Mat([7639258074922385369695396544431086688038866230278865393, 1])
335*2^121+41 : Mat([10994848854023378207969762103553467481, 1])
355*2^36+17 :  Mat([739254977009, 1])
361*2^68+17 :  Mat([3228739205143829398001, 1])
363*2^113+25 : Mat([76930765699924180781900823163546729, 1])
365*2^153+17 : Mat([126289795839436450081521061539167448431443034609, 1])
367*2^132+17 : Mat([60549638138174262347179869540586149626353, 1])
391*2^137+33 : Mat([1048027809209792505810152144784316027504609, 1])
395*2^89+17 :  Mat([7408883568450381948259910129, 1])
401*2^179+89 : Mat([1735962462958252633338127564653316335116142338970690601, 1])
But there are exceptions... ants and mush-rooms...

Code:
for(k=201,400,for(c=0,100,CEk2c(2*k+1,2*c+1,200)))
413*2^35+17 :  Mat([430017331697, 1])
413*2^155+17 : Mat([571591075963695932971706284007409930982859981297, 1])
419*2^117+41 : Mat([859485386163394677078233268915840089, 1])
427*2^48+17 :  Mat([3642115607740913, 1])
435*2^3+1 :    Mat([59, 2])
437*2^81+17 :  Mat([32018217161914724202824177, 1])
437*2^111+17 : Mat([34379298896662419297997377210139121, 1])
437*2^131+17 : Mat([36049307719866692977816897805498838401521, 1])
453*2^169+25 : Mat([6917853954203679576254894803283343233610578985462889, 1])
463*2^54+17 :  Mat([252747469996671473, 1])
487*2^120+33 : Mat([9958985137650062001602369820869658593, 1])
489*2^104+25 : Mat([202410169309911568108371548548201, 1])
511*2^40+17 :  Mat([17025770963441, 1])
511*2^130+17 : Mat([21076883575345400585428415078501037097457, 1])
511*2^180+17 : Mat([23730461254014218382458040329509333116035627013206688241, 1])
537*2^103+25 : Mat([111139326093479051200608917761129, 1])
545*2^35+17 :  Mat([567456285169, 1])
545*2^65+17 :  Mat([609301546677073068529, 1])
545*2^185+17 : Mat([809900673718215202720290065257617944312448796693394604529, 1])
553*2^144+41 : Mat([152250766602314007373694471663883258182804569, 1])
559*2^38+17 :  Mat([4656265150961, 1])
559*2^68+17 :  Mat([4999626636219946353137, 1])
559*2^98+17 :  Mat([5368308223693789662398917362161, 1])
561*2^3+1 :    Mat([67, 2])
565*2^72+17 :  Mat([80852638267313622598129, 1])
569*2^51+17 :  Mat([38826487696572913, 1])
577*2^80+17 :  Mat([21137884785383061630468593, 1])
593*2^125+41 : Mat([311400375901414365484230157726911341657, 1])
611*2^185+17 : Mat([907980388333632089655224274995237732064048100513145143793, 1])
619*2^36+17 :  Mat([1289010790897, 1])
619*2^46+17 :  Mat([1319947049878001, 1])
619*2^66+17 :  Mat([1384064797772874236401, 1])
619*2^76+17 :  Mat([1417282352919423218074097, 1])
623*2^127+17 : Mat([3212059311996131253601248188333205996017, 1])
625*2^38+17 :  Mat([5206020964849, 1])
635*2^41+17 :  Mat([42314538402289, 1])
635*2^81+17 :  Mat([46525326997290274299298289, 1])
635*2^111+17 : Mat([49956189472266902183588866197799409, 1])
635*2^99+41 :  Mat([4968877352746454752780287255641, 1])
663*2^88+25 :  Mat([4187521663501056746214894697, 1])
673*2^196+41 : Mat([834467055390663931666466426038273481093705721308502760924249, 1])
677*2^115+17 : Mat([852166054115897770791550549062304241, 1])
683*2^114+33 : Mat([218236231038725370479158707252758497, 1])
685*2^56+17 :  Mat([1495740967150928369, 1])
699*2^8+3 :    pseudoprime !
709*2^150+17 : Mat([30664200428137138050615901586051274293799010801, 1])
709*2^180+17 : Mat([32925434499209551532608122492411188217748061746308301297, 1])
717*2^90+25 :  Mat([18114347105461584838830042217, 1])
727*2^124+17 : Mat([468532728696064891927790415914574791153, 1])
741*2^3+1 :    [7, 2; 11, 2]
755*2^37+17  : Mat([3144436662769, 1])
755*2^167+17 : Mat([4279985400959347212581942491930351243016646089490929, 1])
761*2^183+41 : Mat([115183121639401621847970576559149164319393626862392222809, 1])
775*2^110+17 : Mat([30485076252761298576599504963224049, 1])
783*2^3+1 :    [5, 1; 7, 1; 179, 1]
787*2^150+41 : Mat([13867209063698647239418161209342625584360760409, 1])
801*2^162+25 : Mat([95564311143024754080094004163734097856685874850921, 1])
T.Rex is offline   Reply With Quote