mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Conjectured compositeness tests for N=k⋅2n±c by Predrag (https://www.mersenneforum.org/showthread.php?t=20467)

 T.Rex 2015-09-09 20:41

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

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

But there are exceptions... [B][COLOR="Red"]ants and mush-rooms.[/COLOR][/B]..

[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])
[B]561*2^3+1 : Mat([67, 2])[/B]
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])
[B][COLOR="Red"]699*2^8+3 : pseudoprime ![/COLOR][/B]
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])
[B]741*2^3+1 : [7, 2; 11, 2][/B]
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])
[B]783*2^3+1 : [5, 1; 7, 1; 179, 1][/B]
787*2^150+41 : Mat([13867209063698647239418161209342625584360760409, 1])
801*2^162+25 : Mat([95564311143024754080094004163734097856685874850921, 1])
[/CODE]

 LaurV 2015-09-10 06:25

[QUOTE=Batalov;409925]Tigger first claims: 'Tiggers eat evertyhing'.
[/QUOTE]
Disclaimer: The similarity with the avatar is coincidental... :razz:

 T.Rex 2015-09-11 19:13

[QUOTE=LaurV;410013]Disclaimer: The similarity with the avatar is coincidental... :razz:[/QUOTE]
I'm Hobbes ! A real Tiger !! Be afraid ! And read again all Watterson's books in order to remember how dangerous I can be !!

;)

 primus 2015-09-16 17:49

[url]http://math.stackexchange.com/q/1426586[/url]

 Batalov 2015-09-16 18:22

Proving these endless copy-pasted conjectures in one direction (i.e. is this a PRP test? -- the 'if' conjectures) is an exercise in copy-pasting the same solution over and over again. This direction is obvious. Maybe [I]mathlove[/I] likes calligraphy, or copy-pasting, or the "bounty points" that it brings ("This question has an open bounty worth +50 reputation from MathBot ending in 3 days.").

The 'iff' conjectures are almost obviously false - and in many previous cases [B]already proven false[/B] by a counterexample. Obviously it is a moot point to ask if you ever get tired of copy-pasting. Bots don't get tired.

 T.Rex 2015-10-16 19:02

I still think that an algorithm that produces only 3 kinds of numbers:
1) primes
2) composite numbers like the ones here below (only 1 small divisor equal to 2b-1)
3) cases in bold (like 561*2^3+1) which are all of the form: 3*k*2^3+1.
deserves some study.

About the number a+b=699*2^8+3 which is said "Pseudoprime", we have: 3|a and 3|b , so that's stupid. a and b must be coprimes.

[CODE]
for(k=500,600,for(c=1,100,CEk2c(2*k+1,2*c+1,200)))
1015*2^36+17 : Mat([2113644511729, 1])
1015*2^194+57 : Mat([225531265890884282311268186355956864153766045172778585153609, 1])
1055*2^99+17 : Mat([20263202776375485129985180025329, 1])
1073*2^135+17 : Mat([1416234587951193100785264305548750704067057, 1])
1077*2^83+25 : Mat([212573568608156019780988009, 1])
1085*2^57+17 : Mat([4738332698857685489, 1])
1085*2^167+17 : Mat([6150707496742902947882659077807193508176239744500209, 1])
1109*2^169+41 : Mat([10245090391229448446659233055493422578083898090890329, 1])
1151*2^37+17 : Mat([4793704104433, 1])
1159*2^52+17 : Mat([158171877821891057, 1])
1159*2^82+17 : Mat([169835760597982450119328241, 1])
1163*2^151+17 : Mat([100599337370729172222471914089076535976553595377, 1])
1167*2^196+25 : Mat([2391960073533471494333507349186398924927820017531274539281513, 1])
1175*2^135+41 : Mat([631832938085298085245574579725159740777561, 1])
1189*2^124+17 : Mat([766279799751886047458243197417371976177, 1])
...
1203*2^53+25 : Mat([221135932723539049, 1])
1205*2^137+41 : Mat([2591859371549903634794612318532144638764121, 1])
1209*2^100+25 : Mat([31277338279100598906316615822441, 1])
...
? for(k=1000,1100,for(c=1,200,CEk2c(2*k+1,2*c+1,400)))
2001*2^59+25 : Mat([23540774803247967337, 1])
2005*2^46+17 : Mat([4275434305339889, 1])
2005*2^66+17 : Mat([4483117802156078907889, 1])
2011*2^78+17 : Mat([18417801691250145987379697, 1])
2015*2^83+17 : Mat([590541945823873402917077489, 1])
2035*2^110+41 : Mat([32612111441723377234751728487539801, 1])
2039*2^185+89 : Mat([564928073731172408080030660042391941315002769741444490281, 1])
2047*2^324+33 : Mat([1076274575392025338747719244930233397807196592557309100327777026759897545519500604528493142636103649, 1])
2047*2^348+33 : Mat([18056891026660293785643655279551430645425263587797967154964785977788581259050493854305107608524720309143521, 1])
2047*2^360+33 : Mat([73961025645200563345996412025042659923661879655620473466735763365022028837070822827233720764517254386251859937, 1])
2047*2^390+41 : Mat([63728123799719110279533981301723636510813413362285644902155185460536092812843290960248891278024234916923391601902658649, 1])
2047*2^312+137 : Mat([62562463692337782432786879471856015032505382286859950493383616231857883737880196970824796702713, 1])
2075*2^357+41 : Mat([7520410276629172759059679380151040635500835322507351437835846861002058220853105741029591700074683732702569561, 1])
2081*2^169+41 : Mat([19224556450990515976102672667702265450849947634934873, 1])
2081*2^385+41 : Mat([2024582096165355833105004504898737292058541664736755420148157989487292518678659142774150322874457023420212169082184793, 1])
2111*2^149+17 : Mat([45650301201549716801727904265270973225817850353, 1])
2111*2^269+17 : Mat([60679658373113666973114702966744324276783274698731453145161221545910673326056391153, 1])
2113*2^54+17 : Mat([1153467395470770673, 1])
2125*2^248+41 : Mat([11866232138758531793744615313631452748273472097535021150841404611150434051161, 1])
2127*2^92+25 : Mat([214946813351837048547790793833, 1])
2131*2^88+41 : Mat([8142130320114646190771709017, 1])
2135*2^97+41 : Mat([4176595727603811376844847752281, 1])
2147*2^333+17 : Mat([1138430862087060994334002977362795896100182974091570206304516240475677354977226692645062494804484014577, 1])
2149*2^112+17 : Mat([338128665120949835567031412469514737, 1])
2149*2^132+17 : Mat([354553603157865094779535530361633884324337, 1])
2149*2^292+57 : Mat([151327098767381450476731532922834405008974197247929238198875339659242443763530509595828297, 1])
2161*2^50+17 : Mat([73729384808694257, 1])
2161*2^170+17 : Mat([98003162399715489551147843444360148727512288205455857, 1])
2161*2^85+33 : Mat([1286148281199859025988945889, 1])
2161*2^253+33 : Mat([481205201618923650596801728084181863213300840120094728633207382771346679138273, 1])
2171*2^262+105 : Mat([76979024148275892138433717421278146740501171049678289616738729915767855907613721, 1])
2177*2^89+17 : Mat([40833264629155649370536264177, 1])
2177*2^117+57 : Mat([3201028038521860459415473418396360777, 1])
2177*2^191+65 : Mat([52966087123786062104149277419856937162228014738752725327809, 1])
2195*2^35+17 : Mat([2285443203569, 1])
2201*2^274+105 : Mat([319663145319140975261194352341399903821765658848217635038519670591756005662130973721, 1])
[/CODE]

All times are UTC. The time now is 12:47.