Last active
March 10, 2026 22:44
-
-
Save Hermann-SW/f25c10f76b5eb1f589b7eb8716608140 to your computer and use it in GitHub Desktop.
Prime factorization of N-1 having exactly 3 prime factors, for Carchmichael numbers N ≤ 10^24
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {[ [2, 4; 5, 1; 7, 1], | |
| [2, 4; 3, 1; 23, 1], | |
| [2, 5; 7, 1; 11, 1], | |
| [2, 3; 3, 3; 7, 2], | |
| [2, 2; 3, 2; 1777, 1], | |
| [2, 3; 3, 2; 1753, 1], | |
| [2, 4; 3, 3; 1733, 1], | |
| [2, 8; 3, 2; 433, 1], | |
| [2, 3; 3, 5; 557, 1], | |
| [2, 3; 3, 3; 23, 3], | |
| [2, 9; 3, 1; 2099, 1], | |
| [2, 3; 3, 9; 5, 3], | |
| [2, 7; 3, 2; 23369, 1], | |
| [2, 8; 3, 6; 19, 2], | |
| [2, 10; 3, 2; 7523, 1], | |
| [2, 12; 3, 4; 1109, 1], | |
| [2, 11; 3, 2; 602947, 1], | |
| [2, 6; 3, 3; 23150779, 1], | |
| [2, 21; 3, 3; 941, 1], | |
| [2, 18; 3, 3; 5, 6], | |
| [2, 7; 5, 2; 72145063, 1], | |
| [2, 7; 3, 4; 2680753697, 1], | |
| [2, 6; 3, 5; 4021030627, 1], | |
| [2, 6; 3, 4; 15572091659, 1], | |
| [2, 5; 3, 6; 5535403613, 1], | |
| [2, 7; 3, 4; 39915622303, 1], | |
| [2, 4; 3, 7; 96140634673, 1], | |
| [2, 13; 3, 5; 4241037223, 1], | |
| [2, 8; 3, 4; 562145573699, 1], | |
| [2, 7; 3, 5; 780715057799, 1], | |
| [2, 8; 3, 7; 514754353411, 1], | |
| [2, 13; 3, 4; 782094030013, 1], | |
| [2, 11; 3, 6; 493521483901, 1], | |
| [2, 10; 3, 2; 83607005432809, 1], | |
| [2, 6; 3, 7; 17069642816257, 1], | |
| [2, 8; 3, 4; 181636770133493, 1], | |
| [2, 8; 3, 7; 17656557012901, 1], | |
| [2, 9; 3, 4; 400228668465407, 1], | |
| [2, 11; 3, 6; 17069532296329, 1], | |
| [2, 7; 3, 6; 358154606667293, 1], | |
| [2, 15; 3, 3; 72650182012649, 1], | |
| [2, 12; 3, 8; 2840104577593, 1], | |
| [2, 8; 3, 8; 48798307008611, 1], | |
| [2, 6; 3, 9; 96817864770763, 1], | |
| [2, 8; 3, 8; 79838485267883, 1], | |
| [2, 14; 3, 5; 38341392536833, 1], | |
| [2, 7; 3, 7; 12829329090663439, 1], | |
| [2, 8; 3, 11; 155786925383213, 1], | |
| [2, 10; 3, 4; 142032830015359091, 1], | |
| [2, 7; 3, 6; 156571901477558353, 1], | |
| [2, 9; 3, 4; 432801471854392247, 1], | |
| [2, 9; 3, 6; 71756980695657203, 1], | |
| [2, 8; 3, 6; 359093858855075987, 1], | |
| [2, 12; 3, 4; 316500219522836431, 1], | |
| [2, 9; 3, 4; 4105893583754854337, 1], | |
| [2, 14; 3, 5; 64782221130991697, 1], | |
| [2, 7; 3, 6; 3014409912028722463, 1], | |
| [2, 12; 3, 4; 1369623407688029387, 1], | |
| [2, 8; 3, 6; 2835263821321369709, 1], | |
| [2, 13; 3, 6; 153631631935525553, 1], | |
| [2, 12; 3, 8; 37086671809110899, 1] ];} |
Author
Author
I learned about file with Carmichael numbers up to 10^24 on this website:
https://blue.butler.edu/~jewebste/
Downloaded the 184GB text file, did strip Carmichael factorizations and took Carmichael numbers only.
Reading the (7.5GB file) vector with 308,279,939 Carmichael numbers less than 10^24 took 13 minutes (111GB resident gp memory).
The parforeach() did output the known entries in non-ascending order, and then below new entries.
Now the gist has all 48+13=61 factorizations with 3 prime factors of N-1 for Carmichael numbers N less than 10^24:
hermann@E5-2680v4:~$ gp -q
? b=read("carm10e24.gp");
? ##
*** last result: cpu time 11min, 6,811 ms, real time 13min, 2,970 ms.
? #b
308279939
?
? parforeach(b,c,if(#factorint(c-1)[,1]<=3,print(c-1" "factorint(c-1))))
...
11780771052793944443904 [2, 10; 3, 4; 142032830015359091, 1]
14610037270673925035136 [2, 7; 3, 6; 156571901477558353, 1]
17949142640745355267584 [2, 9; 3, 4; 432801471854392247, 1]
26783149530692659705344 [2, 9; 3, 6; 71756980695657203, 1]
67015532314969700997888 [2, 8; 3, 6; 359093858855075987, 1]
105007176832408579731456 [2, 12; 3, 4; 316500219522836431, 1]
170279618705481319064064 [2, 9; 3, 4; 4105893583754854337, 1]
257918234375470815166464 [2, 14; 3, 5; 64782221130991697, 1]
281280617711224150467456 [2, 7; 3, 6; 3014409912028722463, 1]
454408175709103637901312 [2, 12; 3, 4; 1369623407688029387, 1]
529128275390279300572416 [2, 8; 3, 6; 2835263821321369709, 1]
917483189706736665698304 [2, 13; 3, 6; 153631631935525553, 1]
996661877717305787756544 [2, 12; 3, 8; 37086671809110899, 1]
? ##
*** last result: cpu time 5h, 11min, 34,911 ms, real time 13min, 30,284 ms.
?
Author
All 308 million Carmichael numbers up to 10^24 can be read fast and fit into only 25GB RAM:
https://stamm-wilbrandt.de/en/#Carmichael
hermann@7950x:~$ gp -q
? #
timer = 1 (on)
? b=read("carm10e24.bin");0
cpu time = 3,751 ms, real time = 17,627 ms.
0
? #b
308279939
? b[#b]
999999999855878641139521
?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Number of prime factors of n for above 48 Carmichael number n-1 values: