Factors of Generalized Fermat Numbers
- Alpertron
- Math problems
- Factors of Generalized Fermat Numbers
These numbers have the form 23n + 1 and 23n - 1.
The problem here is to find factors of these numbers.
Since 23n+1 + 1 = (23n + 1) (43n - 23n + 1)
the first factor of the RHS has the same form of the LHS, so we are interested on factors of the second expression.
In the same way 23n+1 - 1 = (23n - 1) (43n + 23n + 1)
Notice that 43n - 23n + 1 is always multiple of 3, because 43n = 13n = 1 (mod 3), 23n = 2odd = 2 (mod 3), so 1 - 2 + 1 = 0 (mod 3).
The numbers 43n + 23n + 1 are known as Generalized Fermat Number Fn,2.
| Exponent | Prime factors | Discoverer |
|---|---|---|
| 0 | No prime factors | |
| 1 | 2*32+1 = 19 | |
| 2 | 3230*33+1 = 87211 | |
| 3 | 2*34+1 = 163 | |
| 1672*34+1 = 135433 | ||
| 3358160*34+1 = 272010961 | ||
| 4 | 6*35+1 = 1459 | |
| 574*35+1 = 139483 | ||
| 4291937 2147783270*35+1 = 1042940743 1911334611 | ||
| 377829239 3426209464*35+1 = 9 1812505160 2568899753 | ||
| 5 | 312568*36+1 = 227862073 | |
| 4267065754*36+1 = 3110690934667 | ||
| 2 9752059431 0685684488*36+1 = 2168 9251325248 9863991753 | ||
| 15 1179583137 9924450952*36+1 = 11020 9916107596 4924744009 | ||
| Prime cofactor with 78 digits | ||
| 6 | 8*37+1 = 17497 | |
| 2478*37+1 = 5419387 | ||
| 2766*37+1 = 6049243 | ||
| 11338334*37+1 = 2 4796936459 | ||
| 84279294*37+1 = 1 84318815979 | ||
| 504889554 2903149065 7884451200 5439490118*37+1 = 110 4193455232 9187006879 3294775589 6164888067 | Eric Jeancolas (14 Nov 2022) | |
| 2892851800 1521723769 6354515718 1899996240*37+1 = 632 6666886932 8009884192 7325875681 5291776881 | Eric Jeancolas (14 Nov 2022) | |
| 7 | 8*38+1 = 52489 | |
| 4410*38+1 = 28934011 | ||
| 80183520*38+1 = 526084074721 | ||
| 440 5633237922*38+1 = 2890535 9674006243 | Philippe Strohl (7/2003) | |
| 1107 8656127098*38+1 = 7268706 2849889979 | Philippe Strohl (7/2003) | |
| 8 | 62*39+1 = 1220347 | |
| 141 0521316064*39+1 = 2776329 1064087713 | Philippe Strohl (7/2003) | |
| 9 | 400455322*310+1 = 2364 6486308779 | Dario Alpern |
| 13 | 760*314+1 = 3635056441 | Dario Alpern |
| 33493592*314+1 = 16019 8812234649 | Dario Alpern | |
| 14 | 5659504816*315+1 = 8120770 8270836113 | Dario Alpern (10/2005) |
| 27622252160*315+1 = 39634912 7374389121 | Dario Alpern (12/2005) | |
| 15 | 2*316+1 = 86093443 | Dario Alpern |
| 16 | 38480104*317+1 = 4969326902816953 | Dario Alpern |
| 17 | 64074*318+1 = 24823580412187 | Dario Alpern |
| 18 | 33158976*319+1 = 3853940 0089977793 | Dario Alpern |
| 134770686*319+1 = 15663877 5218956363 | Dario Alpern | |
| 20 | 40749616*321+1 = 42625537 6246620049 | Dario Alpern |
| 23 | 228978058*324+1 = 6467016678 5259533899 | Dario Alpern (10/2005) |
| 27 | 578221330*328+1 = 1 322784935944 1514518131 | Dario Alpern (10/2005) |
| 28 | 6*329+1 = 41178 2264189299 | Dario Alpern |
| 101256*329+1 = 694923749 0458593049 | Dario Alpern | |
| 29 | 1373422682*330+1 = 2827 7555084144 9107428619 | Dario Alpern (10/2005) |
| 30 | 3028366*331+1 = 18 7054111241 0831440603 | Dario Alpern (10/2005) |
| 31 | 32*332+1 = 5929664 6043258913 | Dario Alpern |
| 3200*332+1 = 592966460 4325891201 | Dario Alpern | |
| 32 | 6912*333+1 = 3842422663 6031774977 | Dario Alpern |
| 5 3257453584*333+1 = 2960614 1009397550 8931344433 | Dario Alpern (1/2006) | |
| 33 | 234402*334+1 = 39 0916474476 5243106739 | Dario Alpern |
| 39 | 15098*340+1 = 1835 5643310084 1511037499 | Dario Alpern |
| 42 | 110*343+1 = 361 0826641339 9078538971 | Dario Alpern |
| 43 | 6152*344+1 = 60583 1059023357 6304683913 | Dario Alpern |
| 46 | 96*347+1 = 25525 2617845992 0315627553 | Dario Alpern |
| 47 | 61406648*348+1 = 4 8981898922 3354715405 5937023929 | Dario Alpern (10/2005) |
| 50 | 54*351+1 = 1162994 7400608011 9380780339 | Dario Alpern |
| 51 | 8*352+1 = 516886 5511381338 6391457929 | Dario Alpern |
| 53 | 12202*354+1 = 7095430909 1109480834 2140842139 | Dario Alpern |
| 54 | 2544*355+1 = 4437987928 0720173555 7057769809 | Dario Alpern |
| 55 | 211435592*356+1 = 110654 3166109387 2738317683 8841455433 | Dario Alpern (10/2005) |
| 56 | 14*357+1 = 219806005 8714914256 2967483883 | Dario Alpern |
| 24*357+1 = 376810295 7796995867 9372829513 | Dario Alpern | |
| 57 | 4663458*358+1 = 21965 4873542025 7844537383 2096296563 | Dario Alpern (10/2005) |
| 58 | 6*359+1 = 847823165 5043240702 8588866403 | Dario Alpern |
| 59 | 62080*360+1 (34 digits) | Dario Alpern |
| 3587982080*360+1 (39 digits) | Dario Alpern (10/2005) | |
| 65 | 860704*366+1 (38 digits) | Dario Alpern |
| 75 | 8*376+1 (38 digits) | Dario Alpern |
| 84 | 203214*385+1 (46 digits) | Dario Alpern |
| 85 | 60037080*386+1 (49 digits) | Dario Alpern (10/2005) |
| 87 | 62192*388+1 (47 digits) | Dario Alpern |
| 93 | 19388858*394+1 (53 digits) | Dario Alpern (10/2005) |
| 94 | 23922928*395+1 (53 digits) | Dario Alpern (10/2005) |
| 99 | 260280*3100+1 (54 digits) | Dario Alpern |
| 110 | 30*3111+1 (55 digits) | Dario Alpern |
| 111 | 32*3112+1 (55 digits) | Dario Alpern |
| 118 | 92774*3119+1 (62 digits) | Dario Alpern |
| 125 | 8800130*3126+1 (68 digits) | Dario Alpern (10/2005) |
| 130 | 6*3131+1 (64 digits) | Dario Alpern |
| 136 | 1190881376*3137+1 (75 digits) | Dario Alpern (3/2006) |
| 144 | 14*3145+1 (71 digits) | Dario Alpern |
| 161 | 616400864*3162+1 (87 digits) | Dario Alpern (5/2006) |
| 163 | 104620466*3164+1 (87 digits) | Dario Alpern (11/2005) |
| 166 | 150*3167+1 (82 digits) | Dario Alpern |
| 167 | 56*3168+1 (82 digits) | Dario Alpern |
| 175 | 407078202*3176+1 (93 digits) | Dario Alpern (6/2006) |
| 176 | 54*3177+1 (87 digits) | Dario Alpern |
| 184 | 6222*3185+1 (93 digits) | Dario Alpern |
| 202 | 96*3203+1 (99 digits) | Dario Alpern |
| 206 | 82880766*3207+1 (107 digits) | Dario Alpern (8/2006) |
| 208 | 4104*3209+1 (104 digits) | Dario Alpern |
| 2148256*3209+1 (107 digits) | Dario Alpern (10/2005) | |
| 211 | 11128*3212+1 (106 digits) | Dario Alpern |
| 214 | 1062270*3215+1 (109 digits) | Dario Alpern (10/2005) |
| 221 | 2208*3222+1 (110 digits) | Dario Alpern |
| 222 | 78*3223+1 (109 digits) | Dario Alpern |
| 238 | 968*3239+1 (118 digits) | Dario Alpern |
| 281 | 723538*3282+1 (141 digits) | Dario Alpern (10/2005) |
| 285 | 9960*3286+1 (141 digits) | Dario Alpern |
| 286 | 1127030*3287+1 (143 digits) | Dario Alpern (10/2005) |
| 308 | 81816*3309+1 (153 digits) | Dario Alpern |
| 314 | 5826134*3315+1 (158 digits) | Dario Alpern (10/2005) |
| 319 | 2*3320+1 (153 digits) | Dario Alpern |
| 325 | 16950610*3326+1 (163 digits) | Dario Alpern (1/2006) |
| 330 | 24*3331+1 (160 digits) | Dario Alpern |
| 333 | 3108970*3334+1 (166 digits) | Dario Alpern (1/2006) |
| 362 | 109064*3363+1 (179 digits) | Dario Alpern |
| 398 | 528*3399+1 (194 digits) | Dario Alpern |
| 405 | 413610*3406+1 (200 digits) | Dario Alpern (10/2005) |
| 499 | 316072*3500+1 (245 digits) | Dario Alpern (10/2005) |
| 525 | 168074*3526+1 (257 digits) | Dario Alpern |
| 560 | 3522382*3561+1 (275 digits) | Eric Jeancolas (9 Dec 2022) |
| 679 | 14922*3680+1 (329 digits) | Dario Alpern (10/2005) |
| 694 | 6*3695+1 (333 digits) | Dario Alpern |
| 706 | 1974806*3707+1 (344 digits) | Dario Alpern (1/2006) |
| 724 | 38102*3725+1 (351 digits) | Dario Alpern (10/2005) |
| 781 | 2*3782+1 (374 digits) | Dario Alpern |
| 797 | 4650*3798+1 (385 digits) | Dario Alpern (10/2005) |
| 820 | 6*3821+1 (393 digits) | Dario Alpern |
| 936 | 7262*3937+1 (451 digits) | Dario Alpern (10/2005) |
| 979 | 8*3980+1 (469 digits) | Dario Alpern |
| 1223 | 26*31224+1 (586 digits) | Dario Alpern |
| 1251 | 2*31252+1 (598 digits) | Dario Alpern |
| 1366 | 14*31367+1 (654 digits) | Dario Alpern |
| 1407 | 48*31408+1 (674 digits) | Dario Alpern |
| 1453 | 2*31454+1 (695 digits) | Dario Alpern |
| 1530 | 558*31531+1 (734 digits) | Dario Alpern (10/2005) |
| 1870 | 29758*31871+1 (898 digits) | Donovan Johnson (9 Nov 2007) |
| 2056 | 1296*32057+1 (985 digits) | Dario Alpern (10/2005) |
| 2183 | 458*32184+1 (1045 digits) | Dario Alpern (10/2005) |
| 2252 | 2512*32253+1 (1079 digits) | Dario Alpern (11/2005) |
| 2408 | 14*32409+1 (1151 digits) | Dario Alpern |
| 2451 | 48*32452+1 (1172 digits) | Dario Alpern |
| 2623 | 32*32624+1 (1254 digits) | Dario Alpern |
| 2703 | 210*32704+1 (1293 digits) | Dario Alpern (11/2005) |
| 2789 | 210*32790+1 (1334 digits) | Dario Alpern (11/2005) |
| 4047 | 3872*34048+1 (1935 digits) | Eric Jeancolas (22 Nov 2022) |
| 4599 | 8*34600+1 (2196 digits) | Dario Alpern (11/2005) |
| 5479 | 2*35480+1 (2615 digits) | Dario Alpern (12/2005) |
| 5828 | 1606*35829+1 (2785 digits) | Eric Jeancolas (3 Dec 2022) |
| 6313 | 362*36314+1 (3016 digits) | Eric Jeancolas (22 Nov 2022) |
| 7840 | 6*37841+1 (3742 digits) | Dario Alpern (12/2005) |
| 8851 | 338*38852+1 (4227 digits) | Eric Jeancolas (22 Nov 2022) |
| 9409 | 160*39410+1 (4492 digits) | Dario Alpern (1/2006) |
Exponents 0 to 5 are completely factored.
For exponent 6 to 9 I ran 300 ECM curves with B1 = 50000 and 700 with B1 = 250000.
For exponents 10 and 11 I ran 250 ECM curves with B1 = 50000.
All cofactors for exponents 6 to 12 were found composite by Donovan Johnson on 9 November 2007.
The limits in the search for factors are:
- Exponents 11 to 37: 2*1011
- Exponents 38 to 64: 2*1010
- Exponents 65 to 200: 5*109
- Exponents 201 to 283: 2*108
- Exponents 284 to 400: 2*107
- Exponents 401 to 801: 2000000
- Exponents 802 to 1400: 200000
- Exponents 1401 to 2900: 20000
- Exponents 2901 to 5000: 2000
- Exponents 5001 to 10000: 200
Factors found so far: 144
| Exponent | Prime factors | Discoverer |
|---|---|---|
| 0 | 2*31+1 = 7 | |
| 1 | 8*32+1 = 73 | |
| 2 | 9728*33+1 = 262657 | |
| 3 | 32*34+1 = 2593 | |
| 878*34+1 = 71119 | ||
| 1205998*34+1 = 97685839 | ||
| 4 | 2*35+1 = 487 | |
| 68 945611600*35+1 = 1675 3783618801 | ||
| 794 122245632*35+1 = 19297 1705688577 | ||
| 1527979 4910498594*35+1 = 371299016 3251158343 | ||
| 5 | 110*36+1 = 80191 | |
| 134*36+1 = 97687 | ||
| 520*36+1 = 379081 | ||
| 911835396 9088590993 8096624124 8655269152*36+1 | Robert Silverman | |
| Prime cofactor with 90 digits | Robert Silverman | |
| 6 | 18*37+1 = 39367 | |
| 3477936*37+1 = 7606246033 | ||
| 120345960*37+1 = 26 3196614521 | ||
| 241912920*37+1 = 52 9063556041 | ||
| 7 | 32*38+1 = 209953 | |
| 198*38+1 = 1299079 | ||
| 1067874826 9716005072*38+1 = 700 6326739760 6709277393 | ||
| 8 | 7192*39+1 = 141560137 | |
| 298 0726001840*39+1 = 5866962 9894216721 | ||
| 14 8184916806 7520103946 5100468042*39+1 | Dario Alpern (9/2005) | |
| 9 | 8*310+1 = 472393 | |
| 686184*310+1 = 40518479017 | ||
| 1151958*310+1 = 6 8021967943 | Yannick Saouter (1995) | |
| 2819752928*310+1 = 16650 3590645473 | Donovan Johnson (9 Nov 2007) | |
| 10 | 6175 5910828066*311+1 = 1093987433 5459407703 | Donovan Johnson (9 Nov 2007) |
| 11 | 166*312+1 = 88219207 | Yannick Saouter (1995) |
| 12 | 2735946*313+1 = 436 1981634559 | Yannick Saouter (1995) |
| 13 | 3 5198840558*314+1 = 16835496 3224856703 | Dario Alpern (11/2005) |
| 14 | 18*315+1 = 258280327 | Yannick Saouter (1995) |
| 16 | 26*317+1 = 3357644239 | Yannick Saouter (1995) |
| 1698664*317+1 = 21936 5745842233 | Yannick Saouter (1995) | |
| 17 | 31078*318+1 = 1204 0253957143 | Yannick Saouter (1995) |
| 19 | 190*320+1 = 66 2489036191 | Yannick Saouter (1995) |
| 1677086*320+1 = 584763 7303935487 | Yannick Saouter (1995) | |
| 21 | 8*322+1 = 25 1048476873 | Yannick Saouter (1995) |
| 23 | 126*324+1 = 3558 6121596607 | Yannick Saouter (1995) |
| 26 | 1386*327+1 = 1056907 8114191983 | Yannick Saouter (1995) |
| 29 | 2483478*330+1 = 5 1132609695 2154709223 | Yannick Saouter (1995) |
| 1 3802075504*330+1 = 28417 2495077438 3172378097 | Dario Alpern (10/2005) | |
| 5 7791187848*330+1 = 118986 9309111924 2074625353 | Dario Alpern (1/2006) | |
| 30 | 298*331+1 = 18406667 2092616207 | Yannick Saouter (1995) |
| 33 | 288*334+1 = 480302832 9503971873 | Yannick Saouter (1995) |
| 34 | 19 5296351960*335+1 = 97709782 4075685982 2208875721 | Dario Alpern (1/2006) |
| 39 | 128*340+1 = 15 5618117875 9286886529 | Yannick Saouter (1995) |
| 15152*340+1 = 1842 1294703563 0585192753 | Yannick Saouter (1995) | |
| 42 | 88*343+1 = 288 8661313071 9262831177 | Dario Alpern |
| 44 | 287122*345+1 = 8482481 7293028847 3221775447 | Dario Alpern |
| 45 | 539382*346+1 = 47805092 8885440534 6124375879 | Dario Alpern |
| 46 | 40160*347+1 = 10678067 8465573333 2037525921 | Dario Alpern |
| 47 | 6288*348+1 = 5015713 9406737434 2020813969 | Dario Alpern |
| 50 | 1289566968*351+1 = 2777 3325939632 5098361020 2554605097 | Dario Alpern (10/2005) |
| 55 | 6*356+1 = 31400857 9816416322 3281069127 | Dario Alpern |
| 57 | 2304*358+1 = 10 8521365184 5534809965 9374899457 | Dario Alpern |
| 64 | 2*365+1 = 20 6021029217 5507490794 7094535687 | Dario Alpern |
| 602*365+1 = 6201 2329794482 7754729207 5455241487 | Dario Alpern (10/2005) | |
| 75 | 923680232*376+1 (46 digits) | Dario Alpern (11/2005) |
| 76 | 26*377+1 (39 digits) | Dario Alpern |
| 81 | 59425822*382+1 (47 digits) | Dario Alpern (10/2005) |
| 87 | 1140517862*388+1 (52 digits) | Dario Alpern (1/2006) |
| 94 | 26*395+1 (47 digits) | Dario Alpern |
| 95 | 22*396+1 (48 digits) | Dario Alpern |
| 99 | 14008*3100+1 (52 digits) | Dario Alpern |
| 102 | 3883390160*3103+1 (59 digits) | Dario Alpern (2/2006) |
| 103 | 161129448*3104+1 (58 digits) | Dario Alpern (10/2005) |
| 115 | 537432*3116+1 (62 digits) | Dario Alpern (10/2005) |
| 118 | 14010*3119+1 (61 digits) | Dario Alpern |
| 120 | 354*3121+1 (61 digits) | Dario Alpern |
| 121 | 762630*3122+1 (65 digits) | Dario Alpern (10/2005) |
| 129 | 8*3130+1 (63 digits) | Dario Alpern |
| 136 | 379406664*3137+1 (74 digits) | Dario Alpern (3/2006) |
| 158 | 2266*3159+1 (80 digits) | Dario Alpern |
| 161 | 70*3162+1 (80 digits) | Dario Alpern |
| 204 | 1362*3205+1 (101 digits) | Dario Alpern |
| 282154*3205+1 (104 digits) | Dario Alpern (10/2005) | |
| 221 | 54264*3222+1 (111 digits) | Dario Alpern |
| 225 | 247968*3226+1 (114 digits) | Dario Alpern (10/2005) |
| 227 | 192*3228+1 (112 digits) | Dario Alpern |
| 246 | 1223920*3247+1 (124 digits) | Dario Alpern (10/2005) |
| 273 | 10152*3274+1 (135 digits) | Dario Alpern |
| 288 | 10*3289+1 (139 digits) | Dario Alpern |
| 315 | 626280*3316+1 (157 digits) | Dario Alpern (10/2005) |
| 329 | 24*3330+1 (159 digits) | Dario Alpern |
| 363 | 32*3364+1 (176 digits) | Dario Alpern |
| 430 | 7136*3431+1 (210 digits) | Dario Alpern |
| 432 | 31890*3433+1 (212 digits) | Dario Alpern |
| 571 | 32*3572+1 (275 digits) | Dario Alpern |
| 575 | 2272*3576+1 (279 digits) | Dario Alpern |
| 626 | 766514*3627+1 (306 digits) | Dario Alpern (1/2006) |
| 630 | 50*3631+1 (303 digits) | Dario Alpern |
| 653 | 224*3654+1 (315 digits) | Dario Alpern |
| 666 | 2408*3667+1 (322 digits) | Dario Alpern |
| 56976*3667+1 (323 digits) | Dario Alpern (10/2005) | |
| 761 | 30*3762+1 (366 digits) | Dario Alpern |
| 780 | 32*3781+1 (375 digits) | Dario Alpern |
| 788 | 1069946*3789+1 (383 digits) | Dario Alpern (1/2006) |
| 895 | 6*3896+1 (429 digits) | Dario Alpern |
| 1000 | 34*31001+1 (480 digits) | Dario Alpern |
| 1005 | 1422*31006+1 (484 digits) | Dario Alpern (10/2005) |
| 1068 | 26*31069+1 (512 digits) | Dario Alpern |
| 1154 | 2544*31155+1 (555 digits) | Dario Alpern (10/2005) |
| 1206 | 96*31207+1 (578 digits) | Dario Alpern |
| 1257 | 387478*31258+1 (606 digits) | Eric Jeancolas (6 Dec 2022) |
| 1280 | 24*31281+1 (613 digits) | Dario Alpern |
| 1556 | 267322*31557+1 (749 digits) | Eric Jeancolas (6 Dec 2022) |
| 1558 | 4336*31559+1 (748 digits) | Dario Alpern (10/2005) |
| 1654 | 8*31655+1 (791 digits) | Dario Alpern |
| 1734 | 178*31735+1 (831 digits) | Dario Alpern |
| 2120 | 26*32121+1 (1014 digits) | Dario Alpern |
| 2343 | 6822*32344+1 (1123 digits) | Dario Alpern (11/2005) |
| 2505 | 8934*32506+1 (1200 digits) | Dario Alpern (11/2005) |
| 2812 | 4616*32813+1 (1346 digits) | Dario Alpern (11/2005) |
| 3709 | 302*33710+1 (1773 digits) | Dario Alpern (11/2005) |
| 4216 | 2*34217+1 (2012 digits) | Dario Alpern (11/2005) |
| 5088 | 274*35089+1 (2431 digits) | Eric Jeancolas (22 Nov 2022) |
| 5271 | 32*35272+1 (2517 digits) | Dario Alpern (12/2005) |
| 5719 | 70*35720+1 (2731 digits) | Dario Alpern (12/2005) |
| 6222 | 18*36223+1 (2971 digits) | Dario Alpern (12/2005) |
| 8757 | 198*38758+1 (4181 digits) | Dario Alpern (1/2006) |
Exponents 0 to 5 are completely factored.
For exponent 6 to 9 I ran 300 ECM curves with B1 = 50000 and 700 with B1 = 250000.
For exponent 10 I ran 300 ECM curves with B1 = 50000.
All cofactors for exponents 6 to 12 were found composite by Donovan Johnson on 9 November 2007.
The limits in the search for factors are:
- Exponents 11 to 37: 2*1011
- Exponents 38 to 64: 2*1010
- Exponents 65 to 200: 5*109
- Exponents 201 to 283: 2*108
- Exponents 284 to 400: 2*107
- Exponents 401 to 801: 2000000
- Exponents 802 to 1400: 200000
- Exponents 1401 to 2900: 20000
- Exponents 2901 to 5000: 2000
- Exponents 5001 to 10000: 200
Factors found so far: 123
If you have a number that can be in these tables or you have any comment please fill the form.
In October 2005 I wrote a program to find factorizations of numbers of the form (2^pe+1)-1)/(2^pe-1) and (2^pe+1+1)/(2^pe+1). The numbers in this page can be factored using p=3. In December 2022 I changed it to execute on 64-bit processors, dropping support for 32-bit operating systems. You can download it here. It includes both the source code and the Windows executable. The source code can be compiled in Linux also by typing:
gcc -O2 genferm.c montmult.s -o genferm -lm
Last updated on December 16th, 2022.