Primality Certificate for (4366^10099-1)/4365

Andy Steward36,758 digits19 March 2011
Originally by A.A.D.Steward 2011
A066180 #1240

This certificate uses a theorem of Konyagin and Pomerance to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 32.067824% factorization of N-1:

From Factorisation
43662 · 37 · 59
Φ211 · 397
Φ33 · 2521 · 2521
Φ67 · 31 · 31 · 2833
Φ93 · 10459 · 220745048380104169
Φ116271 · 2813467823 · 142678338629334415413067
Φ17137 · 1531 · 1871 · 40387649 · 465650686062415097 · 2362440175175844954392687
Φ1819 · 813277 · 448239677441167
Φ2211 · 23 · p34
Φ273 · 379 · 8503273 · 700609501 · 4486991843483833365667 · 10932746421020983289688799
Φ33199 · 661 · 393361 · 25442184409581226447699687699 · p34
Φ34919 · 37537 · p51
Φ51307 · 1327 · 89659 · 1409233087359781 · 47044024384367496571631599 · p66
Φ543457 · 5962472811019 · 655860850123369087 · p32
Φ6667 · 19371463 · 1965456544327 · p52
Φ994357 · 14590360889575069459213 · p193
Φ102103 · 409 · 187987 · 100626367 · 7128967065984326928499 · 9700179640114140624830359 · p52
Φ153613 · 111997 · 15711233683051 · c329
Φ187c583
Φ1982377 · 48907 · 143409054815995519 · c194
Φ2974159 · 53731693832207436343 · 10050492208605876870307902757 · c604
Φ306895210493941 · 77334438669391473879646423 · c312
Φ374c583
Φ4593673 · 200924145473871763 · c1028
Φ5611123 · 48247 · 13737006163 · 23179200529 · 881296413486226932283 · c1116
Φ594452470591 · 2035216532950929901 · 4393906103159135839 · c610
Φ9184366927 · c1042
Φ11222721685287321067 · c1150
Φ1683774181 · 44553724810057 · c3475
Φ3366c3495
Φ504910099 · 35767117 · p10472
Φ10098161569 · 1019899 · 142643106611013889 · c10456

We need the product F of all the prime factors from this partial factorization:

76 4511543043 8175352776 8681467198 3519942781 0773353471 8563478719 9310512096 7364372323 6574428035 2557145647 7488845482 2572652505 1370438171 4413733630 7078937271 6172879761 4014921467 1082284591 6738264690 4428770656 7237468097 9818437755 1879206809 0429265376 9437762702 7642605909 4696538419 8339963329 3471651734 1661617569 2023487101 0390297626 7586555427 1633508998 7033842578 8183919213 9322055065 7474520623 4471823554 3752311657 2708541837 5130761399 9666598298 7215275556 5554051637 3548583461 0460264729 9325432448 7768742790 2385429473 7752391279 9377170496 1624741129 9886461309 0048993128 4683144756 9922583421 7465145767 4597930579 8575644957 9002405418 6862610885 9076524400 5013218228 5913241164 5829229840 7154419066 0013535354 3639442361 1527716779 6147905054 6726798957 2018107407 5619321186 5622876812 7978995771 4630070053 2493479430 5904746886 5517827154 1270273349 2515930853 6887416987 5385717166 8876952091 4031353050 4818906916 9979658335 5169005032 6282236515 0371369248 7418012589 6495132398 4162737880 2952295575 0415830234 3439869346 0000598630 5040685340 4749586342 5070977172 8781410788 3758495276 3877956972 5030630303 6752363187 1732811065 6155348506 0407882292 3939729132 5345304183 4705628811 8058037450 3324910922 1186275624 6424056193 5348618388 0455901520 0438857244 1179611688 1192485366 0272366038 9424824700 9334783211 7530062174 0717911179 5272875768 8318165867 2815015312 4594065387 0020426061 9963907689 2698835960 0153699120 3518298730 1609522594 1962967025 5815721147 5654157909 5228549949 9049741709 0704385523 6899002704 8106531711 7485447769 1752318963 7652181280 4984568382 4847192776 4315318289 5658883171 4069020019 4360620789 1249225910 4579139781 9229482101 8510253150 5774030807 6882370973 8655931818 3713463297 0004947995 8892708046 0834947058 2238543263 8286349088 8064048618 2805915658 9104331237 5657357497 5201582374 8099940869 7348604933 2347673425 1471146803 9380453833 5200021997 2955710540 3920079528 1303338271 4932401365 1312598352 1704319472 6441332167 7924993620 4297609739 2590640709 5158382746 4605904921 1026746023 7348742220 1487055766 5645796115 6175487309 8932322002 2275395716 5572910652 9847478132 5908578641 6509021354 2557614712 4093353861 5280416910 0053591644 0587337638 7780318930 2045261641 4443963570 7752143099 4783034612 5022247606 2785363680 3750537343 1408181533 9297542072 8333373822 4701373533 0751672001 0236407468 6901564930 8680423526 9063620048 7440267655 5798149021 5323996502 1261947913 7504761814 0411086007 6358741166 1423848400 2604013150 6632026618 2985162963 1819133894 6991118223 4173327986 8809063422 0677559207 9563079401 1908416567 3698009465 8662853061 5748591257 1824280523 9433188168 3246559603 4453207994 1706887799 0727390162 3336530696 1686240737 4031895239 7529966208 6876193674 1093779734 1515001342 5246942903 9116079232 0136159220 2673916201 1908152204 6478104158 5012693237 3411613878 1488954457 4342139330 4019861675 0392826306 0911976647 7067907464 4960194544 7364473639 7191720344 0210111870 8059728665 8116787905 3108408534 0324689825 7732096625 1264269302 6075621570 0832021388 7756923970 2960809728 6997801685 6043269979 2496208585 8999439380 0887570954 8892329717 3909764210 2776856799 7906953161 3650144624 4179478939 8959210031 9882971553 3519516025 6274629350 4601902995 3547251172 3516595005 3654086620 0608169425 8570217746 1690803403 6137331158 9013858674 1262750016 3489354630 5556750961 0534555168 9998764359 4725841071 4117717239 5298269650 6784615475 6424368504 6931929948 1428847969 2690740259 5216517283 8919542527 9081634067 7901318790 4339025234 1480694870 8032052248 0522310664 0248391707 0535304437 6352283813 2669972674 2659897606 4441314160 0300821814 4336428390 0162204664 0463449862 4986021524 5051609042 9234479967 3007712055 0078516782 5205363660 5542684974 8334468692 5146802208 7501412065 7331430621 3928721142 1594471510 7243013541 1920721799 8538301217 9377552521 1280238071 2039537110 4087171541 9783194412 6125254185 3430396561 3486398667 8259699440 1896268682 9053735783 5336697586 8452568098 8384858033 7040589101 3354918117 6408605681 9146394135 2354014274 6085414871 6197728972 5214162203 1666785210 6415609925 0539744969 2300788235 8336629831 8264269687 8689847384 8282733564 7096855596 2583918054 3098400261 7968097048 5929149114 6669459827 3946025729 7366442899 2755470689 0097120132 9293386109 1579555307 9568832697 1439670297 3439796992 5813484054 1137630550 7336852430 8509183882 8596172733 2006287915 2912601171 8463940611 2919777463 3243705287 9384045638 8163254811 8219746390 1708843195 4367682933 0026938901 3409711290 3501102131 3284885785 0221092210 0104016191 9587452883 1668559906 8209687206 3588376448 2786074992 9283007032 7142713229 3193474081 2342112132 9055213515 5179678795 2824005336 8096972555 8727455663 8183682068 5209641804 7856381365 9354644691 1436005956 9424231738 1694475296 2558083688 5893880993 6269381361 4038275105 5607463327 3345104103 9239381359 6046350839 1118635226 9476943924 0280610025 0669778803 9606391856 9229672948 3983080715 1534205323 7549656148 7117464483 2150552830 6270311392 9794224535 2657798769 3601500326 9317922332 4633323738 7945231699 1346384187 2114584344 2932405785 1040981833 9653957831 1062080565 9090139617 2490768687 5913714509 0965357047 3396044617 2869419806 6072718250 2990072119 7956172317 6135130314 5345392436 9791573234 6710557338 2224237049 8466500277 3437463905 5480960906 0969616978 6598624930 8965658560 1859178678 8514128786 3287282641 1906909014 7157653306 6599901206 2085415191 0369327835 5589381314 0236506735 4362875911 0613625844 3314185621 1444778504 2109703902 9174641429 6431110419 7390925496 4030371919 4255046114 2483354983 1050201243 3093980968 5770744276 8862608571 8598256148 1056611236 7165779548 2640899466 5655043433 1567397485 5253791204 4563100737 1854375164 7171085793 1342545610 8731279266 7242156749 4419409648 9340699647 5105627397 3003374824 3957619317 2325319560 3884004891 4941645120 5180310899 9310599120 3857519189 5291786827 0798924774 3259806404 5065240467 7578489088 7143125346 1836992746 9571072909 6028263446 5187074576 2980754089 8620859511 7289776470 7075415520 2486210281 5767442998 1979284822 4070411290 5748730035 5596018546 5999635797 2718366980 6064626860 2912228327 7363985451 8835980579 8384985480 8685220301 7297393347 4123166189 3420909622 1723454095 7239161701 9980163476 5675152301 0699478494 9441469228 4538683334 9071025752 0421075913 1913114086 8661580413 2340152901 8371432263 3503184323 3683470635 7749045623 8112319058 1065084823 6056634377 2564443729 7802517416 9947738229 5828971310 0302650939 3704982078 4523082313 7133576276 2636084321 8652439956 4041824246 7399853030 6882184268 1080997811 4846644536 2128643206 5890751870 0627693522 8541554987 3110772142 7232205998 3026267727 6208142590 8220873791 4793076341 8059668060 6449589847 4709389388 5332235014 0015580800 5269001959 7039398735 4703198907 2155477017 9407082855 9791507244 3681664726 5213598903 6819995120 2299314453 6816709525 8963658965 7528865330 1744133134 9772629810 1249970466 4491239549 9852720256 4919545430 6600867534 9700389116 1484825205 3753937649 7987763819 2390126114 0501526815 5465114885 4500557432 3246331125 6229247198 5582263849 6541477353 8748576554 5904132465 3993048803 5322586796 6434272871 8183905614 7948580765 5327015881 7580542269 2140330174 7085393153 8813789713 0665234367 4608553655 6287837079 0882101827 7660298101 8153109674 2819813420 7689544243 8304878239 0985138945 3952715986 0871119827 5261209763 8022099073 9398808348 3037785968 7984745605 3061381737 3588742521 5514323329 5895772566 6118250192 7782448109 1346035252 5920725712 8562342718 5738067405 6172946180 4328809253 0365403295 4610899618 0673778804 0349921494 1484177690 7019026673 3373595404 8559296139 0873631141 1655158903 6970313087 3847904040 8669482447 1516749142 8966899480 2130345219 3921492600 6650924461 0499089846 5321550849 9797458348 8404907869 4664255379 7016304929 5977224473 9942748612 2787486432 3770318686 9106991621 4582035561 5087484485 0018384166 0078458981 1171160842 5595169470 4715104595 8067033679 9025105182 3184437293 8101920332 1959817249 2846132087 4719132807 4188294713 3205937193 7611284301 2396279767 2775978116 9440445127 3353096266 7566009742 1390404990 6287798721 2776167110 3321984214 8643181727 8367398678 0134361846 0567946178 6016814776 1605314260 0359456160 8318115906 4852350247 0196108840 5840958871 3838069877 9791328759 2056436428 9978875724 4734053318 2565830416 9042930804 3913251668 7114719337 9873845817 1016001696 5491934239 5409249240 8883384699 7678290636 2463594334 5103598590 3545188985 6053787967 3977999848 1027065452 2286208737 9315748614 0704168454 9890482836 3987473215 7265486925 2280235384 6077160287 9377729196 1339385601 2419831286 2013967814 6279488123 4214268836 4046966790 4025341212 2457353732 5752423828 0637022157 9681319805 2944570600 6216047898 5790258444 4678957104 2100432242 3089586488 7472973556 0118243499 2745412844 7066316222 9200843255 3781464128 6726219502 3994242496 9479330269 9466284848 3515552648 4104680997 2062540184 9928497850 6050910754 3911525667 0299467913 5749368689 1492265901 3544040512 1740717656 2919270644 2457950253 4428579787 3521761908 9275475752 6265504413 6246983440 9958166315 4429295505 7762428371 1805122218 8561513204 0033624207 6150933639 3513894140 9926476948 7652269690 4364083984 8712455761 5467369008 9698718789 1080901093 4317967256 4062182598 4538842488 4577019636 6003876789 4565161123 3219979446 8432737677 2513807013 2705110492 1069512427 6104994262 0075941233 8589166394 4538169378 2911130858 5277328078 8801976079 7814629228 2413939183 4830798848 5082766661 1450559395 5076471983 2021856486 8175344771 4032013410 2420040521 3722708395 1984718627 4857672552 6452479488 5238124843 8389704229 4099775539 2635667384 1975685067 9173323559 6445435580 6798870476 0957626860 3769345222 2173351918 1386779171 5650786443 8605451183 7335978500 2852345617 0441351136 9096212008 2259065105 9176307593 5172263105 5502855874 5920954476 1751713111 8794988071 8733256416 7822668766 5727755118 0746164974 6586790983 6404841387 2389863516 1095811846 1089735705 1684162008 3269474230 5839738660 4017101539 8555170857 6360869393 1762100084 5717804585 2487861329 3036480159 4324277306 9391090027 5796520833 9419461188 4476938893 0263806088 6720214182 7570496717 0013782102 8247066501 8053010678 7968212174 1970484561 2708762158 9962496877 0312715373 7601998516 3854056985 1655051966 2662238845 9774003312 4837034049 7595982906 3909804963 5164073283 8461714846 7516346069 6800769300 2293855136 0368357866 4400090166 2021021606 8145744166 4645189873 5153285405 4128090772 4909764152 9801821865 2184305058 4626149050 2196499427 8166175132 3659815275 2152658456 5906024415 3875140000 3782356387 7096258395 3711759739 6362734273 5032981862 9423540495 2277779905 4795120806 6752818854 5811940096 4797451096 2370128942 7997561462 2472804432 3237663459 3218236173 7792587349 0081479560 7527503341 1879803916 1802569263 4109780433 0830207314 8139665676 4850437467 5559301046 5046998308 9346013387 4941604380 8758255751 8849582522 9768585782 8720323821 4576501085 2951882800 8907206959 4485538214 6735880104 5418825571 7331134977 6201886469 5661694202 2628306584 8417549619 7744727630 9498487971 0093875358 5640106865 4099384230 7418561838 4762852104 1077068487 1422841485 6839670062 5381927457 7153006202 1247821415 0200716085 5672517238 9584364993 0763510996 2511135761 7557221366 8978518494 7106785248 0263343762 8601945915 8412052759 2950583360 3518462032 1284877215 5923119941 0950769447
399 7332625665 8605751865 6173414962 4263261665 2508817916 3031547528 2171770766 5528016636 8145311017 6727964646 0154348833 9703944471 6240885299 2563641088 6881082501 7030428364 6117138742 0318112004 8443242761
125455 4214517862 7260569204 1239812979 2349687505 1258149577 7718596639
55 1534057802 0113855263 6136405453 0831900482 8300977497
24 8355291616 4714074811 1541455837 4262465093 5437878653
5 0520212621 2830550512 6548259143 9223724378 7783078857
9945 2872643426 0444672589 1351551067
4810 3304622556 1457927547 6730961331
24 5793088034 3563393144 8785314141
254421844 0958122644 7699687699
100504922 0860587687 0307902757
773344 3866939147 3879646423
470440 2438436749 6571631599
109327 4642102098 3289688799
97001 7964011414 0624830359
23624 4017517584 4954392687
1426 7833862933 4415413067
145 9036088957 5069459213
71 2896706598 4326928499
44 8699184348 3833365667
8 8129641348 6226932283
5373169383 2207436343
439390610 3159135839
203521653 2950929901
65586085 0123369087
46565068 6062415097
22074504 8380104169
20092414 5473871763
14340905 4815995519
14264310 6611013889
272168 5287321067
140923 3087359781
44823 9677441167
4455 3724810057
1571 1233683051
596 2472811019
196 5456544327
89 5210493941
2 3179200529
1 3737006163
2813467823
700609501
452470591
100626367
40387649
35767117
19371463
8503273
4366927
1019899
813277
774181
393361
187987
161569
111997
89659
48907
48247
37537
10459
10099
6271
4357
4159
3673
3457
2833
25212
2377
1871
1531
1327
1123
919
661
613
409
397
379
307
199
137
103
67
59
37
312
23
19
112
7
33
2

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 32.067824%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w(N-1) ≡ 1 mod N and GCD(w(N-1)/p-1,N) = 1. In this case, w = 6 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F4>N, N can have no more than three prime factors.

Express N in base F

Let N = c3·F3 + c2·F2 + c1·F + 1. Let c4 = c3·F+c2.

Square Checks

For t = 0 to 5, we prove that Q(t) = (c1+t·F)2+4·t-4·c4 is not a perfect square. This is done by checking whether Q(t) is a quadratic residue modulo a variety of bases. If it happens to be a QR in all of the bases, we calculate s = floor(sqrt(Q(t))) and show that s2 < Q(t).

Continued Fraction

We approximate c1/F by a continued fraction u/v such that v is maximal while remaining less than F2 / N1/2 = 831691 7108956928 4179130986 9577179308 3503974397 4604325258 2799123992 4561000378 9049490767 5015169217 6029769566 9404228097 4438337245 8300337918 8484551780 6357213555 1512619795 8071777115 7803916587 3267522644 7732761178 8852107403 0729001297 4616691350 2413459928 7756593428 5509849638 5397932511 1984672073 5407269322 4787386505 3430141858 6721409020 6864595216 1504873220 7967152090 5220863896 9978037534 4680777867 6013481400 2764699764 1027615406 4284651899 3473518646 1278948031 0945982485 0646065397 9130729397 1588869665 0599581514 3787575924 8895247665 7071459642 6692658129 2947644183 6641096885 5654554183 1526591609 1681229038 7148985467 6607817810 8974548733 5894217896 5180432773 7082410233 7584419808 8988465245 6457365794 6368544651 8169829134 2132783034 4865331412 7191087072 7640381019 8980244497 6522521977 7774371171 9582232539 2334809397 3000165322 7295697028 1518762279 4112233674 6499514019 2127891604 1152448489 3543886967 2696483160 7291863648 9217751779 2262607360 3863843663 4030308019 0602032015 1897864362 9663650930 2864989695 2098726422 1554791676 7758138855 0669141336 8885305801 9077732151 8040841585 2836858288 9758003380 0056829559 3959837305 7084252137 7501223175 9992524868 9056385394 7006005083 3285836168 6663003635 1518409308 3735092041 0309646604 2783051116 3081812837 5346603736 2690593684 6548967068 2996279698 9513156050 0581028023 4556394083 1424445896 8833354400 8009542512 4888932178 1107984617 8873267814 2018819931 2979333476 6957369016 3084771371 0276187186 8995029642 4649290045 2449281743 7070357134 8134409738 8536251291 0875070363 1333219050 0759734723 5473447915 3270634117 0072050252 9913237207 6334965004 2371410831 1087125878 1087714510 5553456049 3059442303 6076966330 5022125861 9072807034 2810068647 8358176204 9911325909 0231705890 1838266401 5862991083 8805557402 3528374231 4557076325 4569614624 1166984019 2569525974 2579379037 3730597814 5965161411 9855574942 5945029291 3180583395 4471040097 0766381304 1456965911 7014551784 3319100899 8832710753 9537108981 3977912268 9288307433 3968949448 9181905661 3588069646 1145261694 4865475627 7206556493 7765786615 5241754759 4806096009 9594512334 9949000030 0539160606 2216468617 6825865792 6359352314 5924620088 0111846586 7711737298 5060759269 1159635277 8399942162 0635549696 6748390950 9087594169 0398207612 4976578375 3221101898 8278167544 5672300200 2821692205 6013177550 2949362466 2824742582 9185996155 9259900128 6154913390 8670181446 1965274571 5303088636 8574535356 2371821379 0755554724 0697328561 7616062025 1894799629 1185232942 5160214303 2613709813 1399045257 4757060705 8731427729 1068730139 4131935681 2253384797 9880854477 8179960362 9516662369 7966220622 5489873316 0090901321 9464861704 8358444011 1971820660 2515174348 6604130657 4349368143 7632786598 8013560097 1838832046 0152724909 2758126097 4070443333 5815541838 4923708061 4052003650 6152728598 5190936297 9677365722 3658068160 6190966154 6539323645 9422154619 8835745300 6132922192 0031067130 5180954780 4263477360 3794336715 6245907255 4678486103 6862716512 8794777687 0142075880 0010949182 6850315550 2425564549 4641406791 5039606928 2930389483 0035772529 3209664858 7693500995 9180173778 9001540511 8112518690 5134538668 5853175944 1050149390 4326513643 8622377753 2934664041 3839510699 6255832363 6638632196 7636909293 7838705831 1323554413 2393481453 2367048386 5052987968 8722288317 1489710709 6920948146 8756485639 2615370930 4088558036 8672635929 6963680356 0639076375 3833329957 1819893654 3354414813 9342529759 7003543487 7649032922 0163790698 7596598835 2260182115 7841224159 2469694560 1570614378 2298127647 7688680029 7962350715 6885572532 7896820012 4762398849 0758565200 1623259465 0293712093 3354698175 3360121832 8280057651 4382689427 4014549276 9229149454 5826854066 3680375034 0756904195 1567787201 1934824338 3485987392 6878318734 2092107308 2039098504 9665365638 2895001768 4629984172 0053378160 9781523451 9301500413 8959654862 6761876618 7407343990 8392272908 3365714028 6893869350 4992396534 2867228203 1810381048 0868985439 8785547442 7562959168 0385554598 6303225995 5226460015 1773139633 3799417057 2086273709 0630424979 4696314154 2626315098 7469143461 7114516702 5974954005 9226964552 7821531032 9022785644 0363421937 7763963193 9426903770 9787321611 4298951703 0141349110 1617450183 6544808085 1820442190 7694938372 6459540011 4225038530 0110721036 0578422355 1755554508 7550025704 1303978174 2067840577 2171744224 1298036848 4167083254 0454398818 6445122353 3713727444 1504139375 9022891134 4290883468 3844513653 2248821494 7743402396 1599184901 8334917323 6782480968 8839587124 6593290302 0701472871 1062032459 3073149004 8596662345 2983915399 9951883595 8467787257 4059123741 0151907810 1529069909 2172164159 9689681689 5462193072 8511314557 0633383642 5503768225 0068020456 0822876444 3878888708 4929810580 3690323706 8391031784 0194247406 4656442394 5889024296 2824687841 8497778837 0165449881 1480218078 2094226263 9920548375 2928178498 6748594457 7529493925 3876484188 6629546124 4827605974 2582299935 0648326902 4652586778 8150973001 4293997706 5267250498 2918600269 8532372465 3815638201 1414485258 2275767211 4786694482 7694973810 1261354933 3190303062 8029668911 5274584637 0096129531 0568675618 2002739760 9398526645 9676499873 6133226497 3931382658 4694339878 4097022541 0487127630 2762850899 6994056207 5907905374 9317589290 2801060942 9446716733 1129713893 5308538917 2209635409 3930586973 4586225066 6695489885 3996543730 9497159074 0486506837 0401219873 1620732948 4142799616 0179149058 0361074638 5425543039 3710455912 0161103477 1062035693 2670255065 8656324782 1418775495 9442745449 7796922260 7108591182 8613710902 6342710555 0784692549 8231434862 0807505928 1899844837.

With those constraints, the unique continued fraction is: {0, 2, 1, 6, 3, 45, 2, 1, 1, 1, 25, 1, 5, 1, 5, 2, 1, 1, 1, 1, 5, 1, 1, 1, 218, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 51, 2, 1, 3, 1, 1, 3, 6, 8, 3, 5, 1, 2, 3, 2, 2, 1, 3, 2, 1, 1, 2, 28, 1, 1, 2, 15, 1, 3, 2, 2, 2, 4, 2, 1, 3, 1, 7, 10, 3, 1, 74, 1, 1, 3, 7, 1, 3, 2, 4, 6, 7, 4, 8, 1, 2, 2, 8, 2, 1, 4, 1, 1, 4, 2, 15, 1, 2, 2, 71, 9, 5, 3, 3, 2, 2, 1, 30, 1, 2, 4, 24, 1, 1, 5, 1, 1, 6, 1, 6, 2, 1, 10, 1, 12, 53, 4, 1, 89, 1, 2, 1, 55, 4, 1, 6, 84, 1, 2, 1, 62, 24, 3, 3, 2, 1, 26, 25, 4, 1, 14, 2, 4, 1, 2, 1, 3, 2, 10, 1, 3, 1, 6, 11, 1, 1, 1, 10, 1, 1, 1, 12, 19, 1, 1, 1, 3, 13, 25, 2, 1, 6, 1, 7, 1, 8, 3, 1, 1, 2, 2, 5, 1, 1, 3, 5, 1, 206, 2, 2, 4, 23, 1, 1, 1, 1, 7, 7, 4, 1, 5, 1, 1, 1, 1, 1, 5, 2, 4, 3, 1, 4, 13, 3, 2, 44, 1, 1, 1, 1, 22, 1, 1, 2, 6, 7, 7, 9, 1, 47, 1, 9, 1, 16, 36, 4, 2, 4, 7, 3, 1, 4, 50, 1, 2, 3, 1, 13, 8, 1, 8, 3, 237, 233, 4, 8, 2, 11, 8, 2, 2, 1, 1, 1, 5, 1, 1, 7, 33, 1, 13, 18, 2, 4, 1, 3, 2, 4, 59, 1, 1, 1, 1, 1, 1, 1, 1, 1, 99, 1, 2, 1, 1, 9, 1, 1, 2, 5, 2097, 4, 1, 6, 10, 89, 5, 4, 1, 6, 2, 3, 3, 3, 11, 1, 7, 1, 1, 5, 41, 2, 4, 3, 1, 1, 28, 16, 24, 3, 24, 27, 1, 1, 2, 24, 28, 1, 2, 1, 1, 1, 1, 3, 1, 67, 1, 5, 2, 6, 3, 1, 26, 2, 1, 6, 2, 1, 12, 2, 5, 1, 2, 29, 3, 1, 4, 19, 1, 1, 2, 5, 3, 2, 1, 11, 1, 10, 5, 2, 1, 1, 4, 10, 3, 1, 72, 6, 3, 20, 1, 15, 2, 1, 1, 1, 2, 4, 56, 4, 1, 1, 13, 7, 1, 1, 1, 3, 1, 12, 1, 2, 3, 1, 2, 1, 2, 5, 32, 3, 3, 1, 2, 445, 2, 1, 3, 2, 3, 2, 2, 6, 4, 8, 2, 2, 2, 3, 4, 3, 1, 2, 2, 1, 1, 4, 2, 9, 2, 89, 334, 1, 27, 1, 2, 3, 40, 1, 2, 21, 1, 2, 4, 3, 2, 1, 2, 1, 3, 65, 5, 13, 3, 1, 1, 1, 23, 1, 1, 3, 1, 4, 3, 2, 2, 6, 1, 4, 3, 1, 7, 1, 4, 1, 3, 1, 1, 1, 1, 2235, 1, 5, 1, 12, 7, 12, 1, 4, 4, 1, 1, 2, 1, 2, 2, 1, 2, 5, 1, 2, 4, 7, 16, 2, 1, 1, 3, 72, 3, 1, 128, 2, 1, 16, 3, 9, 1, 5, 1, 1, 1, 786, 1, 4, 1, 23, 1, 1, 8, 9, 1, 1, 6, 2, 5, 1, 1, 4, 1, 1, 9, 1, 3, 1, 2, 1, 1, 1, 18, 3, 2, 4, 1, 10, 519, 2, 6, 2, 2, 54, 52, 3, 1, 1, 1, 1, 3, 1, 2, 2, 1, 4, 1, 16, 2, 1, 8, 2, 10, 4, 1, 14, 3, 1, 1, 4, 5, 1, 2, 4, 1, 18, 4, 2, 1, 1, 4, 1, 16, 6, 42, 5, 1, 4, 2, 1, 12, 7, 12, 4, 1, 1, 6, 1, 11, 1, 4, 1, 3, 1, 1, 2, 2, 1, 1, 4, 5, 1, 22, 3, 1, 3, 6, 2, 1, 1, 11, 2, 1, 3, 1, 5, 4, 1, 1, 2, 10, 1, 6, 5, 1, 6, 13, 75, 2, 1, 1, 1, 1, 11, 1, 1, 2, 3, 3, 9, 7, 2, 3, 2, 2, 3, 1, 2, 2, 12, 1, 1, 10, 4, 1, 23, 2, 1, 5, 2, 3, 1, 5, 2, 9, 1, 2, 5, 11, 3, 1, 4, 1, 1, 1, 12, 1, 2, 1, 1, 18, 1, 8, 1, 2, 4, 2, 2, 1, 2, 1, 28, 1, 2, 1, 2, 1, 1, 1, 6, 9, 3, 1, 3, 12, 1, 7, 12, 5, 1, 4, 5, 1, 1, 3, 3, 1, 2, 3, 2, 1, 4, 1, 1, 1, 2, 2, 3, 1, 5, 6, 77, 5, 1, 3, 1, 3, 2, 10, 2, 1, 1, 1, 26, 1, 14, 1, 17, 1, 3, 1, 1, 1, 1, 12, 1, 1, 3, 1, 17, 2, 1, 1, 2, 4, 2, 21, 5, 1, 41, 5, 6, 1, 1, 1, 1, 2, 3, 1, 5, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 4, 3, 1, 4, 4, 1, 3, 11, 1, 10, 1, 2, 1, 8, 2, 1, 12, 18, 1, 1, 1, 123, 1, 9, 1, 1, 11, 26, 1, 1, 21, 1, 20, 1, 1, 2, 5, 10, 1, 2, 85, 1, 3, 1, 6, 1, 1, 1, 60, 5, 1, 3, 1, 4, 3, 2, 2, 1, 1, 14, 2, 3, 1, 2, 35, 1, 38, 8, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 4, 4, 5, 2, 1, 1, 3, 3, 1, 1, 11, 1, 1, 2, 5, 2, 2, 1, 58, 1, 2, 2, 2, 1, 15, 4, 3, 20, 1, 3, 8, 1, 1, 1, 3, 8, 1, 7, 1, 21, 6, 2, 15, 21, 35, 3, 1, 310, 1, 80, 6, 9, 1, 2, 16, 3, 1, 1, 2, 2, 12, 3, 1, 1, 1, 10, 1, 1, 7, 2, 1, 4, 61, 1, 2, 1, 21, 1, 2, 1, 7, 1, 1, 1, 3, 2, 1, 3, 1, 2, 1, 1, 3, 2, 2, 2, 1, 1, 2, 1, 2, 3, 2, 1, 1, 5, 71, 2, 1, 2, 1, 30, 3, 2, 1, 79, 3, 2, 2, 3, 1, 1, 1, 1, 5, 1, 2, 1, 14, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 7, 6, 6, 3, 2, 1375, 43, 3, 7, 3, 1, 1, 3, 20, 1, 10, 1, 4, 7, 2, 2, 14, 1, 6, 1, 10, 1, 5, 3, 1, 4, 5, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 2, 14, 1, 44, 1, 43, 3, 1, 7, 19, 4, 20, 1, 8, 17, 1, 1, 1, 15, 1, 11, 5, 3, 11, 1, 3, 4, 1, 45, 3, 1, 2, 2, 1, 6, 33, 1, 6, 2, 1, 1, 3, 1, 1, 5, 1, 1, 4, 2, 9, 1, 3, 1, 1, 1, 7, 15, 2, 1, 2, 5, 29, 1, 5, 2, 1, 1, 1, 1, 263, 24, 1, 2, 1, 1, 1, 1, 7, 14, 1, 3, 1, 1, 1, 1, 1, 1, 4, 2, 1, 21, 1, 1, 1, 1, 1, 2, 3, 19, 1, 1, 6, 1, 4, 3, 1, 29, 1, 2, 1, 1, 2, 11, 1, 1, 5, 1, 8, 4, 1, 1, 1, 4, 2, 3, 1, 1, 1, 114, 12, 8, 2, 1, 17, 2, 1, 1, 12, 1, 1, 2, 2, 2, 1, 63, 1, 1, 3, 7, 2, 1, 1, 9, 1, 2, 3, 2, 3, 2, 1, 1, 2, 3, 2, 2, 3, 2, 7, 1, 1, 9, 1, 6, 2, 1, 2, 6, 5, 8, 4, 12, 1, 3, 1, 7, 1, 5, 2, 1, 3, 2, 4, 1, 3, 1, 1, 1, 1, 16, 2, 2, 1, 2, 6, 1, 3, 9, 2, 2, 2, 1, 1, 1, 1, 1, 6, 2, 5, 6, 1, 53, 1, 30, 1, 1, 1, 1, 3, 1, 1, 7, 2, 20, 1, 1, 14, 1, 11, 5, 1, 1, 1, 2, 1, 1, 68, 10, 5, 2, 36, 3, 1, 1, 1, 1, 14, 4, 57, 11, 6, 1, 8, 1, 17, 1, 4, 1, 69, 1, 1, 9, 1, 3, 2, 1, 4, 23, 4, 1, 2, 9, 2, 18, 4, 1, 1, 5, 22, 1, 20, 1, 2, 2, 2, 2, 1, 2, 2, 279, 1, 1, 1, 2, 8, 1, 1, 2, 5, 1, 2, 1, 1, 1, 3, 1, 3, 3, 2, 1, 1, 1, 8, 1, 129, 26, 2, 1, 3, 9, 2, 19, 1, 152, 1, 4, 1, 2, 1, 1, 4, 9, 2, 4, 1, 2, 1, 1, 4, 2, 2, 13, 9, 36, 2, 7, 2, 3, 3, 2, 6, 2, 6, 1, 36, 8, 5, 3, 2, 2, 84, 1, 3, 17, 2, 2, 10, 2, 2, 3, 1, 1, 2, 59, 4, 2, 3, 1, 2, 5, 2, 4, 48, 2, 1, 8, 1, 1, 4, 1, 9, 3, 2, 1, 4, 1, 17, 1, 1767, 3, 10, 1, 19, 2, 21, 18, 2, 42, 24, 1, 2, 5, 1, 2, 4, 1, 2, 2, 1, 3, 1, 1, 1, 10, 23, 8, 1, 2, 1, 1, 4, 2, 18, 6, 1, 11, 3, 3, 15, 1, 1, 7, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 9, 1, 1, 9, 1, 5, 2, 1, 1, 1, 1, 1, 10, 7, 3, 6, 1, 1, 27, 12, 2, 1, 1, 2, 4, 1, 3, 1, 5, 52, 1, 1, 4, 2, 1, 1, 4, 1, 1, 33, 1, 9, 1, 4, 1, 3, 2, 1, 18, 1, 7, 1, 1, 10, 2, 8, 1, 16, 194, 1, 1, 1, 1, 1, 1, 3, 7, 1, 7, 2, 11, 1, 2, 6, 1, 26, 5, 2, 16, 22, 4, 2, 15, 1, 1, 4, 1, 1, 1, 8, 8, 1, 1, 1, 4, 20, 1, 2, 5, 1, 2, 1, 2, 39, 1, 1, 1, 1, 1, 7, 2, 23, 1, 3, 1, 1, 1, 7, 16, 1, 2, 1, 2, 2, 5, 1, 3, 1, 5, 1, 11, 45, 4, 3, 1, 2, 2, 7, 2, 2, 1, 5, 1, 4, 2, 1, 6, 18, 1, 22, 1, 13, 2, 4, 2, 1, 1, 1, 3, 46, 1, 2, 1, 2, 2, 50, 16, 1, 5, 2, 2, 3, 1, 1, 66, 14, 4, 1, 4, 1, 1, 22, 1, 1, 4, 3, 8, 3, 1, 1, 11, 1, 2, 5, 1, 3, 1, 1, 9, 1, 1, 1, 3, 1, 2, 1, 28, 1, 7, 3, 1, 1, 9, 1, 1, 2, 31, 1, 6, 2, 1, 3, 1, 9, 8, 5, 1, 4, 10, 3, 1, 2, 1, 2, 1, 3, 3, 1, 15, 1, 36, 9, 1, 1, 1, 5, 15, 1, 1, 7, 5, 2, 3, 2, 2, 1, 1, 2, 1, 2, 4, 1, 1, 23, 21, 49, 1, 707, 8, 2, 1, 1, 5, 1, 74, 3, 11, 14, 1, 1, 1, 10, 1, 2, 12, 1, 5, 2, 21, 1, 10, 1, 3, 3, 4, 1, 8, 1, 1, 4, 2, 1, 1, 1, 1, 2, 3, 1, 1, 6, 2, 1, 1, 1, 2, 2, 10, 3, 1, 1, 3, 1, 29, 1, 9, 1, 1, 50, 1, 1, 5, 1, 1, 1, 1, 2, 1, 5, 3, 2, 9, 6, 2, 3, 1, 54, 1, 3, 9, 2, 9, 1, 1, 1, 1, 8, 3, 5, 1, 8, 3, 3, 1, 1, 4, 19, 3, 2, 18, 14, 1, 2, 2, 1, 4, 2, 4, 2, 1, 4, 1, 4, 3, 1, 8, 1, 4, 1, 1, 12, 26, 1, 1, 5, 1, 2, 1, 2, 22, 1, 7, 1, 1, 1, 2, 6, 2, 2, 1, 4, 1, 5, 1, 20, 6, 2, 11, 4, 1, 2, 1, 1, 7, 3, 1, 1, 2, 1, 2, 5, 13, 1, 26, 1, 5, 19, 1, 23, 32, 1, 1, 2, 2, 1, 4, 2, 1, 1, 45, 2, 8, 3, 9, 1, 60, 3, 1, 3, 1, 1, 25, 9, 31, 2, 4, 6, 15, 1, 34, 1, 3, 10, 1100 3279696493 4258590879 4455744053 3090228184 8167027661 6724698686 8419685903 5012467102 8594446353 4583067595 5009140781 4346821390 6112001174 1775159421 3212534153 3980406467 0379898375 7348446180 7806879999 6912671295 7307089115 4754788178 2898336863 0126519354 7485665258 3151568776 0884598048 8054557254 3152491840 3498512151 0395302459 8846662929 4621946869 5538855524 7758180398 0500701287 3266721952 7937891035 3045650438 2831613285 1489524968 1919226658 4295162699 3971243191 9483261899 7029340946 7048055705 8122559697 6689385917 5570793607 1246686344 6750092728 4156729766 8401940842 4408646293 1626151975 5507048394 9295334899 7786227954 4809661324 2378481598 9154759578 7849074070 9943940793 2190798734 1474941951 9242874645 0164138788 3107401625 9431646325 5944598335 1352246666 2981945212 0112454503 0468979106 3700983266 9095702985 2681110725 7552232405 2647801495 8703440967 0089652032 1768898996 8968686005 5972423170 8265416055 9683598415 9753334901 2603571344 4054936394 0835803524 4284792550 4738250651 0686794197 1688879496 5167413346 8110923416 6563024799 2218050484 9865486825 2894917861 8643393391 2605220246 2132022387 7326028160 6127419230 9672961677 3812187691 3977508772 4849446018 4787469988 1903991378 3740243015 1141270956 9831188183 8020778428 5780679597 5519690318 1845659468 0767482484 8304968546 7619177889 2897746512 6696048475 4089739456 4748341382 4282862093 7143890637 5644470763 1474592321 0633400268 2310877197 1017713150 6776351160 9917218443 3824900476 6654955596 0840653134 3145799256 1180956002 7176378976 8326319946 6797726071 8976288833 9420519933 8325973902 9754049481 8288553115 2623362199 6125625206 1919762538 4858179791 5997352790 3044652683 9728458854 3901766448 5954864505 1102237972 5451500679 4180500440 2518350756 3080687683 6667769257 4460083350 0325095503 9734899743 4663926357 4510089821 5937811899 7789952892 9270251117 5028244811 8190622281 1384337002 2412298497 6638592832 5651799578 9307371448 5974228022 7172727251 7895745170 9108623166 0985390211 8530518922 2712666543 4124041182 6960030639 9234706366 9424773231 1407439685 3798098870 0144177986 9735338310 0317841324 7083817730 2717398857 2689709892 4344822112 8397650336 2583122772 3797016495 8404102443 4661824904 5120094085 4869757165 4817067069 4517726523 3854248500 5832244976 7093267431 9349980534 2112730049 9819315125 0049637199 0474436397 0664911784 8731324833 0825530352 7885268261 6557495838 5348671835 5566924552 7596459956 0442425654 4677862351 4131866354 9224614002 9190231917 6143632741 3801293288 2879864948 5894150381 3406263730 1322541421 1863951595 0430051440 0457558456 7357563396 0207760180 0453801069 7990143229 5002647671 2144294711 0346068211 3498391650 9975161150 3849538103 5361247896 6295912275 0525743969 4358755366 0396397633 6097607216 2854807561 6587861560 8453537229 5491819525 0978746282 7713588529 1480023437 8835790569 5196397820 9846932834 9170934280 9796876707 2670085866 0533219970 7195527524 3242878017 5937401935 4798867865 7334270529 6727110609 8802094100 4028933213 1711009625 8537768611 7796235783 9260356307 4108418991 1163032634 3597267134 9689094253 0150683242 5965246727 6392959881 8349426990 2721377528 1830719327 7455029071 4357140245 2660314617 5473662399 2895263218 7677795549 5874020560 7711569044 2053762827 0042416772 8021300112 6797248983 0834571439, 118, 5, 2, 1, 5, 2, 2, 10, 1, 1, 100, 1, 44, 3, 1, 2, 2, 1, 2, 1, 4, 1, 2, 1, 14, 3, 1, 1, 2, 8, 2, 1, 1, 1, 1, 1, 34, 1, 1, 3, 1, 2, 1, 3, 1, 2, 20, 5, 2, 4, 1, 6, 5, 18, 1, 1, 1, 6, 1, 374, 1, 1, 18, 3, 2, 1, 2, 2, 4, 199, 1, 64, 1, 3, 3, 18, 1, 2, 2, 8, 41, 7, 1, 8, 2, 3, 1, 11, 1, 2, 3, 1, 15, 5, 1, 2, 1, 15, 15, 2, 4, 15, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 2, 11, 1, 33, 1, 2, 1, 2, 5, 7, 6, 3, 1, 5, 38, 2, 1, 4, 16, 1, 2, 1, 1, 1, 3, 3, 1, 1, 3, 1, 1, 2, 10, 1, 3, 1, 2, 1, 2, 3, 4, 1, 1, 36, 2, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 34, 3, 413, 3, 14, 1, 3, 2, 13, 3, 4, 1, 2, 24, 1, 1, 1, 6, 2, 2, 2, 1, 18, 1, 3, 1, 4, 1, 1, 1, 7, 1, 6, 99, 8, 1, 11, 2, 1, 1, 1, 3, 1, 4, 8, 2, 4, 13, 23, 3, 1, 3, 5, 2, 1, 7, 24, 64, 1, 4, 1, 2, 3, 2, 1, 6, 2, 1, 9, 1, 6, 5, 1, 4, 1, 1, 1, 10, 1, 6, 1, 3, 1, 1, 2, 3, 2, 3, 9, 29, 2, 8, 9, 17, 1, 2, 15, 1, 4, 1, 1, 1, 2, 4, 2, 1, 1, 2, 12, 1, 13, 1, 101, 4, 1, 1, 4, 3, 1, 6, 2, 10, 1, 5, 1, 40, 2, 1, 2, 12, 1, 1, 25, 4, 2, 1, 2, 2, 3, 2, 1, 6, 2, 3, 1, 1, 2973, 1, 1, 1, 1, 16, 5, 2, 1, 13, 3, 1, 1, 3, 1, 1, 2, 2, 1, 32, 3, 3, 4, 2, 1, 4, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 6, 1, 6, 4, 13, 4, 14, 1, 1, 1, 3, 3, 2, 3, 2, 13, 1, 1, 1, 1, 1, 2, 5, 2, 19, 1, 1, 45, 5, 33, 1, 1, 2, 3, 1, 3, 7, 5, 9, 4, 1, 1, 1, 1, 1, 1, 2, 1, 300, 3, 2, 1, 3, 21, 3, 2, 7, 1, 1, 2, 7, 1, 1, 5, 3, 2, 2, 2, 6, 1, 7, 1, 2, 1, 46, 30, 1, 3, 3, 1, 2, 9, 1, 5, 1, 21, 1, 2, 11, 1, 1, 1, 5, 2, 1, 2, 2, 1, 2, 2, 20, 1, 1, 90, 1, 2, 1, 3, 3, 1, 1, 1, 3, 1, 93, 2, 5, 1, 2, 13, 2, 1, 1, 9, 1, 2, 4, 4, 1, 4, 6, 8, 2, 1, 2, 2, 1, 3, 5, 2, 1, 1, 4, 1, 1, 3, 1, 5, 1, 1, 1, 1, 7, 5, 16, 2, 1, 3, 2, 7, 1, 15, 2, 1, 24, 2, 5, 6, 55, 1, 4, 1, 4, 1, 4, 6, 17, 3, 4, 1, 1, 3, 1, 7, 2, 16, 2, 1, 1, 1, 5, 3, 9, 5, 1, 1, 6, 5, 1, 2, 5, 5, 1, 22, 10, 1, 6, 49, 4, 4, 4, 1, 7, 1, 4, 1, 7, 1, 5, 1, 1, 1, 1, 4, 2, 2, 4, 1, 1, 4, 9, 1, 1, 170, 1, 3, 22, 6, 8, 2, 11, 1, 9, 1, 1, 1, 5, 2, 38, 1, 1, 4, 1, 1, 1, 13, 5, 1, 1, 2, 121, 54, 1, 102, 1, 3, 27, 2, 2, 4, 1, 1, 16, 6, 1, 7, 41, 6, 1, 3, 1, 1, 1, 1, 1, 12, 1, 1, 1, 16, 3, 1, 2, 1, 9, 1, 2, 1, 19, 1, 1, 1, 2, 1, 1, 1, 4, 1, 21, 1, 1, 1, 1, 3, 1, 2, 6, 1, 15, 4, 1, 4, 1, 2, 1, 1, 1, 3, 1, 4, 1, 10, 3, 1, 2, 2, 3, 3, 1, 1, 1, 5, 12, 3, 1, 1, 5, 2, 2, 1, 2, 1, 1, 2, 1, 12, 18, 1, 3, 1, 517, 2, 2, 1, 2, 1, 4, 1, 4, 1, 7, 29, 1, 4, 22, 1, 8, 1, 1, 2, 3, 1, 1, 1, 2, 1, 1, 1, 67, 4, 1, 2, 10, 4, 1, 5, 1, 30, 3, 1, 1, 7, 23, 1, 32, 4, 1, 3, 1, 1, 5, 2, 4, 11, 6, 1, 3, 3, 1, 21, 4, 2, 8, 2, 2, 6, 1, 3, 1, 1, 1, 6, 4, 10, 2, 8, 9, 12, 1, 4, 2, 1, 3, 1, 1, 4, 2, 2, 5, 1, 125, 3, 1, 1, 1, 115, 6, 1, 5, 1, 1, 4, 3, 5, 5, 1, 1, 1, 1, 6, 1, 5, 4, 6, 1, 5, 6, 2, 2, 3, 1, 1, 2, 9, 2, 2, 4, 1, 1, 8, 14, 1, 5, 1, 1, 1, 1, 1, 8, 1, 1, 3, 1, 57, 3, 2, 1, 1, 8, 1, 1, 1, 69, 3, 3, 1, 4, 4, 4, 1, 3, 1, 159, 3, 1, 16, 1, 7, 5, 1, 134, 1, 3, 20, 1, 1, 5, 1, 10, 14, 5, 1, 32, 2, 3, 2, 1, 1, 3, 1, 1, 7, 1, 1, 1, 24, 6, 1, 2, 2, 1, 1, 1, 2, 2, 34, 2, 3, 1, 8, 2, 1, 1, 1, 1, 7, 1, 10, 1, 1, 12, 1, 1, 1, 1, 19, 1, 4, 14, 1, 1, 7, 1, 4, 1, 3, 1, 3, 1, 12, 2, 14, 1, 1, 2, 5, 16, 1, 1, 5, 1, 1, 3, 7, 2, 1, 2, 3, 1, 3, 2, 1, 3, 2, 3, 1, 5, 135, 5, 2, 6, 1, 1, 2, 1, 2, 38, 1, 2, 6, 1, 2, 2, 8, 1, 6, 1, 11, 2, 19, 3, 1, 1, 1, 1, 2, 4, 5, 1, 34, 1, 1, 4, 8, 1, 2, 1, 4, 1, 52, 6, 1, 10, 1, 2, 1, 7, 1, 1, 8, 35, 1, 1, 5, 1, 4, 1, 21, 1, 1, 89, 1, 1, 14, 2, 109, 1, 6, 1, 3, 1, 3, 1, 3, 2, 2, 7, 1, 28, 1, 2, 3, 2, 8, 1, 1, 1, 1, 2, 1, 2, 6, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 14, 1, 3, 1, 2, 2, 4, 9, 3, 2, 4, 2, 4, 2, 1, 2, 5, 1, 2, 31, 1, 3, 1, 1, 1, 1, 1, 21, 1, 9, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12, 82, 1, 14, 1, 6, 2, 3, 2, 24, 1, 3, 1, 1, 1, 1, 1, 3, 23, 1, 20, 1, 3, 1, 4, 1, 5, 2, 1, 1, 2, 1, 1, 7, 1, 3, 1, 2, 4, 1, 5, 1, 2, 1, 1, 2, 2, 17, 2, 3, 43, 2, 1, 75, 3, 1, 2, 1, 2, 3, 1, 3, 2, 1, 2, 1, 8, 1, 2, 31, 1, 2, 2, 5, 4, 8, 4, 2, 11, 2, 1, 2, 7, 3, 1, 4, 4, 2, 2, 43, 1, 4, 4, 1, 1, 1, 2, 15, 13, 2, 10, 4, 7, 6, 1, 1, 1, 1, 2, 3, 14, 5, 1, 1, 1, 2, 5, 1, 18, 3, 2, 8, 1, 1, 16, 2, 2, 2, 2, 1, 3, 1, 1, 1, 1, 4, 1, 1, 2, 3, 5, 1, 6, 2, 9, 3, 1, 4, 1, 4, 1, 3, 2, 4, 2, 3, 4, 1, 1, 4, 1, 2, 60, 2, 3, 1, 14, 8, 1, 1, 4, 1, 22, 1, 1, 27, 2, 1, 2, 2, 3, 2, 63, 6, 1, 1, 12, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 1, 4, 1, 7, 1, 3, 5, 1, 1, 1, 2, 5, 2, 4, 7, 5, 10, 1, 27, 1, 282, 1, 28, 4, 5, 2, 2, 2, 9, 2, 4, 1, 20, 1, 1, 6, 1, 5, 1, 1, 7, 1201, 1, 1, 6, 1, 12, 14, 3, 5, 1, 33, 1, 12, 8, 2, 471, 24, 1, 37, 4, 53, 5, 2, 1, 5, 1, 7, 1, 2, 19, 2, 1, 7, 12, 5, 2, 1, 1, 2, 1, 8, 1, 1, 4, 4, 5, 2, 12, 21, 5, 4, 2, 1, 7, 4, 35, 4, 2, 2, 6, 1, 45, 1, 4, 4, 4, 19, 4, 12, 2, 228, 63, 2, 1, 1, 18, 3, 2, 2, 8, 1, 1, 3, 10, 3, 5, 2, 3, 2, 2, 1, 5, 32, 4, 1, 5, 2, 6, 1, 1, 6, 6, 3, 4, 2, 42, 2, 1, 1, 1, 1, 5, 1, 1, 1, 5, 3, 1, 1, 1, 3, 1, 1, 1, 11, 24, 3, 2, 1, 1, 1, 2, 14, 8, 4, 2, 2, 38, 1, 1, 3, 2, 6, 3, 42, 16, 1, 4, 5, 5, 3, 1, 1, 3, 4, 1, 2, 1, 1, 1, 1, 1, 7, 1, 10, 5, 2, 2, 1, 3, 2, 760, 2, 27, 6, 1, 26, 1, 1, 1, 3, 1, 5, 1, 18, 2, 1, 1, 2, 11, 4, 4, 2, 1, 2, 1, 54, 2, 2, 4, 1, 1, 1, 7, 14, 5, 1, 1, 1, 1, 6, 1, 17, 1, 21, 4, 1, 25, 1, 11, 3, 1, 4, 68, 1, 3, 3, 1, 1, 1, 5, 1, 13, 4, 2, 2, 1, 1, 2, 1, 3, 2, 9, 1, 2, 1, 2, 3, 6, 1, 14, 1, 1, 2, 1, 1, 3, 3, 1, 1, 8, 1, 29, 4, 1, 1, 1, 2, 7, 4, 2, 1, 1, 8, 2, 2, 1, 1, 2, 1, 133, 1, 15, 2, 2, 8, 7, 3, 1, 3, 3, 10, 4, 1, 1, 5, 1, 3, 7, 2, 1, 1, 1, 4, 1, 17, 3, 3, 6, 1, 22, 1, 1, 1, 2, 3, 1, 3, 1, 6, 6, 9, 3, 3, 2, 1, 2, 4, 1, 5, 2, 1, 3, 1, 4, 2, 4, 2, 1, 1, 11, 4, 2, 5, 3, 7, 2, 3, 1, 5, 3, 1, 2, 2, 11, 2, 1, 1, 1, 1, 10, 2, 14, 3, 5, 1, 11, 1, 4, 4, 1, 4, 2, 3, 1, 39, 2, 1, 3, 8, 9, 3, 2, 4, 1, 1, 1, 6, 4, 1, 3, 7, 1, 1, 3, 2, 8, 1, 16, 40, 7, 2, 1, 1, 2, 1, 1, 1, 2, 8, 2, 1, 1, 2, 6, 1, 2, 1, 2, 1, 11, 6, 2, 1, 9, 2, 1, 1, 4, 9, 66, 4, 1, 1, 6, 6, 5, 5, 2, 2, 8, 1, 13, 1, 6, 237, 1, 2, 1, 1, 6, 1, 2, 12, 1, 1, 1, 2, 1, 3, 1, 2, 9, 1, 3, 1, 1, 2, 1, 103, 1, 5, 3, 4, 2, 4, 1, 22, 1, 1, 1, 85, 1, 4, 2, 6, 5, 41, 2, 27, 1, 2, 62, 1, 9, 21, 1, 46, 1, 12, 1, 2, 23, 2, 1, 3, 1, 1, 2, 305, 1, 4, 2, 16, 8, 1, 5, 1, 3, 1, 1, 31, 8, 3, 4, 3, 1, 2, 2, 5, 1, 3, 2, 4, 1, 2, 21, 7, 6, 3, 3, 32, 2, 1, 1, 1, 1, 3, 1, 11, 1, 1, 7, 1, 3, 3, 3, 145, 10, 6, 24, 3, 4, 2, 45, 6, 2, 5, 1, 1, 2, 1, 6, 4, 4, 4, 1, 1, 6, 11, 50, 3, 54, 4, 17, 21, 3, 1, 12, 12, 2, 72, 1, 12, 4, 1, 6, 13, 3, 1, 3, 1, 7, 3, 3, 1, 3, 1, 1, 1, 2, 2, 3, 1, 3, 2, 6, 6, 2, 2, 5, 2, 1, 2, 1, 7, 3, 3, 1, 7, 1, 1, 1, 12, 3, 3, 1, 2, 49, 3, 55, 1, 11, 4, 11, 1, 3, 4, 5, 1, 18, 1, 4, 1, 1, 1, 1, 1, 1, 40, 1, 21, 2, 1, 1, 1, 1, 6, 1, 2, 1, 3, 1, 2, 1, 1, 1, 11, 1, 1, 1, 1, 2, 2, 9, 1, 1, 2, 4, 2, 1, 10, 1, 22, 1, 15, 1, 1, 6, 3, 4, 1, 1, 1, 25, 1, 9, 3, 13, 9, 2, 1, 8, 3, 2, 1, 1, 14, 1, 2, 2, 4, 7}, giving these values for u and v:

We also need to calculate d = floor(c4·v/F + 0.5) = 1 1527368464 9215734929 5848330278 2825578663 2079115770 4000685931 8775283338 1203057383 9351894456 9189992151 5605940029 4756238213 0600983284 2724884225 4600863850 2904456950 4727136635 8728406300 4727646372 6373159450 0726570366 4933585522 8330778768 5468059329 3993545173 6977486600 6079361599 5558918334 5589328658 4354843475 1389545147 4757918279 3534680751 0373642934 3465718732 0770077616 8415464485 6056020577 2078522022 3016063937 9580759043 5204336371 8605202515 6516090071 5638292913 4986083736 3344119736 1986257026 7537352580 8356286263 3440889352 5375923916 4302729538 6751444788 2924978781 3543122578 0115463620 7086557647 4684876067 1529346387 7128321936 6665758301 6898233477 0062812626 8661166274 3016673054 5824518003 2104651862 9827968901 7057381478 8892697373 8384855690 7050826629 3782990674 8777615780 0799056632 5970982179 5142197964 7456417914 2059344021 5511762999 7341560560 7877207766 4833042473 8507647738 5711859001 6626727480 2687989063 3683542512 6893933053 2614133087 3214955016 5224906353 2593226214 4567580754 4262879671 1569240820 6604081218 8594045950 1402355907 0138575866 7532265747 0457062910 0818429361 6999026263 8323962166 1533503310 5759143255 7616991051 6665305969 1681673223 4332149254 0186908584 5360935105 9495036346 3128841933 7914163991 9994691684 7573023147 4693865509 0386154626 5995216204 4659891332 6278873294 1312697319 2140541528 6878206502 8204263228 4658211577 3493610455 7580690494 9546273397 6803538318 6690730548 2298464006 1818111502 2165822340 4053570293 4476468785 9222951998 8346649955 9438914168 1347817002 0374214048 4799737375 1439937809 0461034584 7538113413 6932704925 5418262726 3210679449 0807276833 2727116731 3828725090 2322156944 1715676521 2519454013 2127455130 1729004043 1788964409 6982575274 0638764827 4243861852 0452747679 8846489530 8348981392 1830492510 2924154431 3090451194 2331641235 0484507582 3608174856 9238642885 2868115620 1524102692 9381774633 3180799876 8997212561 6781884305 3264736135 9606332638 8625062726 5373128049 4227968107 5531885104 9690181092 4066487024 4404604259 6867471940 5861696331 0296085292 3454523884 1317345723 0431533781 3997287270 4328272419 5418504995 7581861274 7589225340 2993311902 6478119712 5957335929 9776974754 4104333147 3204632985 9083074742 4814499957 8429575932 4687070456 9028468499 9004344192 8736380044 3627821225 5038234061 5915645107 4709121805 7443581428 9145405886 3136898960 5520255368 8668426634 0703439001 5291569567 0311671770 6899575026 8327712207 9490494430 9518519101 1990677651 5322999747 4238296531 8064375679 0989061061 2408395964 9807266852 4775312047 6584855053 1468662879 8501352956 1813670226 2638965875 5292847830 2077914829 0735640810 7520695680 7633679496 2184655319 9156766607 8813530682 3118956382 9425884901 5365259191 8013897706 5308620630 3669160528 0362679619 2488835529 6761383476 2072417052 4508726756 9208734972 8889981454 7138710053 7028454853 9271891685 7112577626 5024824782 8411178619 0487851739 1829724592 4942667198 3579656911 8226637591 7805030691 9885225802 1919694219 0272891834 8926774522 0294923109 0116038755 2860998949 9350867427 0750319488 9688070873 3766029479 7562223724 7235947930 4796499882 6056267199 4245438170 6201357104 4152758394 9050723431 3426302839 0125045118 8748637865 7007831610 1964325436 6497862977 6833015720 6293182151 3423905976 3881262074 4560021145 5956881217 0054041916 5251279984 1206322502 3771295315 6400893056 1256843770 4791956729 9891816239 5105925847 0236532339 0014654403 3713336373 8290224279 1379110514 0167136625 5897646185 8652769228 4984272212 5001777334 6460325542 8207311733 8919821500 4374364468 9784047547 2588561512 4986541128 9698366176 6183397611 0036617062 6987217390 0094447774 4343577973 2827586438 6584663467 1455052425 9963740261 0920043835 5985917201 6129217095 2372573418 5307843315 6183469240 9590021835 1843306129 1312267600 4054895283 5340525583 7577920827 3364816667 8305645538 4308021952 9677750204 2124311027 5316703125 3213046880 4645716966 8776601999 4473303071 3058019933 7252046035 9271861056 0096577877 8553185235 9524774665 4931759588 3834685517 6682884818 9014582879 8271502127 6147647396 9925604100 6854085183 8282343252 3482057827 5814455767 0707410980 9595718256 7903305452 5285170764 1193502890 2945247938 9813765860 9069207357 7255768890 1534255402 9252676930 3577704782 0845436245 2712197567 9261077645 2898970980 1947532170 3967204225 1538470785 2321011898 0197597174 5776307669 1737784182 6807552643 2200836631 5637968860 0878609369 6727171069 2492756795 1744692537 2064882210 4832073143 5684186073 0565618837 0073724461 1534308213 3174671719 6688545376 6895975239 9455963054 7765256086 7953798092 7903247859 8788310670 0115715569 9237121537 8430433135 7597063199 6236889826 6080830216 9982385415 0184265131 8007808372 4206298520 9659842108 8561856076 8201756816 7788036111 7349575302 8394958911 3989688096 4906190060 9470816767 1736621626 8851100411 8986327962 8986964715 2266818152 8298887919 2301675520 0233279272 0630588011 5419254897 0087579216 9960854805 8569680362 8227263542 7576285258 5839891195 3775461513 2853891656 4659053541 2646998588 8439593247 3814117367 0094557540 9425312647 8071077463 9165693809 8151318159 9347426783 6891413817 3544583903 9101315977 9409792728 1358847933 8298482164 6769738593 2845451931 2173896866 2976294877 2371675938 6200191965 9428664964 8553629727 8817640667 6071671827 3808000517 0426169348 1228896281 5802929640 4248484957 0805913543 8554925410 1154575855 1248959704 1488951748 7418900098 3630510642 5642340064 1021016309 9434813597 4615810039 8058269625 9021182698 0456304147 0909118282 6309743599 5657355556 3307263692 2283454405 7314832496 0963455628 0109178866 2194840482 4181123550 4452871993 2784588647 7446090142 8745694504 1371089570 5074821161 7882903042 7026976941 9919798935 5860819755 4370082287 2767707427 1740421603 5140331466 2500841087 6190151888 5219494502 0155341870 5753067893 2111311022 3521859259 5129596978 1566732220 3716895989 3273064289 4597581866 1711828703 3823973747 8295157273 6961152142 3179981140 8442868906 1844555969 7078117427 1059383741 0336059162 9603534835 2648497357 1199350254 6982778973 3589349436 6698287250 7737134684 5281848556 8911546771 6640567042 2339675839 6338784830 3397927002 4165609292 7030680554 3947793456 9966271151 1373197335 6430310394 8105126810 2289680963 8611418292 5009520601 0463457155 9050792688 1032429851 9680005709 9996691535 4260186267 2324098491 5136994738 4636029512 0934791666 2065278133 2335664662 1830819752 3194446486 7484224167 3218276571 9102433682 8460242956 2770550302 7802395996 1229987695 9138636750 3085303528 5646055399 4460687217 9887949913 0417322557 7204593896 8105707556 0886387493 2388529320 9209196945 5606521716 4825679482 4230506884 0203991826 3313688946 1608935844 2602618486 9064286813 7853845923 9172664898 2442680089 6611991188 5424191497 1538691674 6073116323 1317925948 4255031349 0811895812 7347467145 7093786654 6624470615 4000718705 1132972054 5807490516 4792850624 7178186804 4415445796 0089437844 2855091961 9832619732 9027557434 9271964076 1496826141 4407852311 6749922800 9999994051 3431764314 0146768737 4951938495 8666207460 8211978607 0615308658 2254647902 6967430397 9683441146 1087641357 9280730993 2833694426 8037086596 8538690431 8979597112 2502453978

Cubic Polynomial

We now consider the cubic P(x)= v·x3 + (u·F-c1·v)·x2 + (c4·v-d·F+u)·x - d, which we express as: z1·x3 + z2·x2 + z3·x + z4, where:

We need to prove that this cubic has no integer roots r such that r·F+1 is a non-trivial factor of N. Clearly r (if it exists) must lie between 1 and R.

P has a single real root at:

There are no integer roots of P in the interval (1,R), so the proof of primality is complete.