Prime factorization of N-1 having exactly 3 prime factors, for Carchmichael numbers N ≤ 10^24

Car_n-1_3_prime_factors.gp

{[ [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] ];}

Creation of GP file with all Carmichael numbers can be done on computer with 4GB RAM:

(327649324 bytes)
wget https://oeis.org/A002997/a002997.7z
7zr x a002997.7z

pi@raspberrypi5:~ $ du -sb carm10e22.txt 
1158158753	carm10e22.txt
0000000 1a
0000001
pi@raspberrypi5:~ $ head --bytes 1158158752 carm10e22.txt > carm10e22.gp 
pi@raspberrypi5:~ $ dos2unix -f carm10e22.gp 
dos2unix: converting file carm10e22.gp to Unix format...
pi@raspberrypi5:~ $ sed -i "s/$/,/" carm10e22.gp 
pi@raspberrypi5:~ $ sed -i "s/^9999999972168827821201,$/9999999972168827821201];}/" carm10e22.gp
pi@raspberrypi5:~ $ sed -i "s/^561,$/{[561/" carm10e22.gp
pi@raspberrypi5:~ $ wc --lines carm10e22.gp 
49679870 carm10e22.gp
pi@raspberrypi5:~ $

That file is 1.1GB in size, but when loaded with

hermann@7950x:~$ gp -q 
? b=read("carm10e22.gp");
? ##
  ***   last result: cpu time 35,996 ms, real time 40,648 ms.
? #b
49679870
? b[1]
561
? b[#b]
9999999972168827821201
? 

it makes GP using 17.3GB resident RAM.
Also a fast CPU like AMD 7950X is preferable when processing that file.

Carmichael numbers N are odd, so N-1 is even and 2 is always a prime factor of N-1.
Only two Carmichael numbers up to 10^22 have exactly 2 prime factors of N-1:

hermann@7950x:~$ gp -q 
? b=read("carm10e22.gp");
? foreach(b,c,if(#factorint(c-1)[,1]==2,print(c-1" "factorint(c-1))))
1728 [2, 6; 3, 3]
46656 [2, 6; 3, 6]
? ##
  ***   last result: cpu time 9min, 22,177 ms, real time 9min, 22,190 ms.
?

This is computed output that converted created this gist script.
Only the 48 Carmichael numbers N from 49,679,870 less than 10^22 have exactly three prime factors of N-1:

? foreach(b,c,if(#factorint(c-1)[,1]==3,print(c-1" "factorint(c-1))))
560 [2, 4; 5, 1; 7, 1]
1104 [2, 4; 3, 1; 23, 1]
2464 [2, 5; 7, 1; 11, 1]
10584 [2, 3; 3, 3; 7, 2]
63972 [2, 2; 3, 2; 1777, 1]
126216 [2, 3; 3, 2; 1753, 1]
748656 [2, 4; 3, 3; 1733, 1]
997632 [2, 8; 3, 2; 433, 1]
1082808 [2, 3; 3, 5; 557, 1]
2628072 [2, 3; 3, 3; 23, 3]
3224064 [2, 9; 3, 1; 2099, 1]
19683000 [2, 3; 3, 9; 5, 3]
26921088 [2, 7; 3, 2; 23369, 1]
67371264 [2, 8; 3, 6; 19, 2]
69331968 [2, 10; 3, 2; 7523, 1]
367939584 [2, 12; 3, 4; 1109, 1]
11113519104 [2, 11; 3, 2; 602947, 1]
40004546112 [2, 6; 3, 3; 23150779, 1]
53282340864 [2, 21; 3, 3; 941, 1]
110592000000 [2, 18; 3, 3; 5, 6]
230864201600 [2, 7; 5, 2; 72145063, 1]
27794054330496 [2, 7; 3, 4; 2680753697, 1]
62535068311104 [2, 6; 3, 5; 4021030627, 1]
80725723160256 [2, 6; 3, 4; 15572091659, 1]
129129895484064 [2, 5; 3, 6; 5535403613, 1]
413845172037504 [2, 7; 3, 4; 39915622303, 1]
3364153088477616 [2, 4; 3, 7; 96140634673, 1]
8442446194188288 [2, 13; 3, 5; 4241037223, 1]
11656650616222464 [2, 8; 3, 4; 562145573699, 1]
24283361157780096 [2, 7; 3, 5; 780715057799, 1]
288196549352923392 [2, 8; 3, 7; 514754353411, 1]
518960057803186176 [2, 13; 3, 4; 782094030013, 1]
736823627292321792 [2, 11; 3, 6; 493521483901, 1]
770522162068767744 [2, 10; 3, 2; 83607005432809, 1]
2389203765705859776 [2, 6; 3, 7; 17069642816257, 1]
3766420065488110848 [2, 8; 3, 4; 181636770133493, 1]
9885411887926908672 [2, 8; 3, 7; 17656557012901, 1]
16598283338597359104 [2, 9; 3, 4; 400228668465407, 1]
25484675162160826368 [2, 11; 3, 6; 17069532296329, 1]
33420122657338444416 [2, 7; 3, 6; 358154606667293, 1]
64276231433143025664 [2, 15; 3, 3; 72650182012649, 1]
76324561443175108608 [2, 12; 3, 8; 2840104577593, 1]
81962417224575173376 [2, 8; 3, 8; 48798307008611, 1]
121962626066107400256 [2, 6; 3, 9; 96817864770763, 1]
134097997271700572928 [2, 8; 3, 8; 79838485267883, 1]
152649046203603664896 [2, 14; 3, 5; 38341392536833, 1]
3591391068323960459904 [2, 7; 3, 7; 12829329090663439, 1]
7064879736540168527616 [2, 8; 3, 11; 155786925383213, 1]
? ##
  ***   last result: cpu time 9min, 22,090 ms, real time 9min, 22,157 ms.
?

For validation with numbers of Carchmichael numbers less than 10^n from https://oeis.org/A055553

? for(n=1,22,print1(#[c|c<-b,c<=10^n]","))
0,0,1,7,16,43,105,255,646,1547,3605,8241,19279,44706,105212,246683,585355,1401644,3381806,8220777,20138200,49679870,
? ##
  ***   last result: cpu time 2min, 1,035 ms, real time 2min, 1,049 ms.
? 

factval() allows to easily determine N-1 from a factorization:

pi@raspberrypi5:~ $ gp -q
? b=read("Car_n-1_3_prime_factors.gp");
? #b
48
? factval(F)=vecprod([v[1]^v[2]|v<-F~]);
? b[#b]

[              2  8]

[              3 11]

[155786925383213  1]

? factval(b[#b])
7064879736540168527616
? factval(b[1])
560
? 

Only 3 of the 48 factorizations do not have 3 as prime factor of N-1:

? [f|f<-b,f[2,1]!=3]
[[2, 4; 5, 1; 7, 1], [2, 5; 7, 1; 11, 1], [2, 7; 5, 2; 72145063, 1]]
? 

For comparison of Carmichael numbers up to 10^n with 3 prime factors of n or n-1:

$ paste <(tail -25 a055553.txt | cut -b-37) n-1_3_3-22.txt
Here is a tally of the number of carm    
    
#           tot          2          3    |=
  3           1          0          1    |1
  4           7          0          7    |3
  5          16          0         12    |5
  6          43          0         23    |8
  7         105          0         47    |11
  8         255          0         84    |15
  9         646          0        172    |16
 10        1547          0        335    |16
 11        3605          0        590    |19
 12        8241          0       1000    |21
 13       19279          0       1858    |21
 14       44706          0       3284    |24
 15      105212          0       6083    |26
 16      246683          0      10816    |28
 17      585355          0      19539    |30
 18     1401644          0      35586    |34
 19     3381806          0      65309    |37
 20     8220777          0     120625    |43
 21    20138200          0     224763    |46
 22    49679870          0     420658    |48
    
Claude Goutier (C) 2024.    
$

Only 5 of the 48 factorizations have largest prime factor exponent >1:

? factval(F)=vecprod([v[1]^v[2]|v<-F~]);
? foreach([c|c<-b,c[3,2]!=1],f,print(factval(f)" "f))
10584 [2, 3; 3, 3; 7, 2]
2628072 [2, 3; 3, 3; 23, 3]
19683000 [2, 3; 3, 9; 5, 3]
67371264 [2, 8; 3, 6; 19, 2]
110592000000 [2, 18; 3, 3; 5, 6]
? f=b[#b];print(factval(f)" "f);
7064879736540168527616 [2, 8; 3, 11; 155786925383213, 1]
?

Number of prime factors of n for above 48 Carmichael number n-1 values:

? [#factorint(factval(c)+1)[,1]|c<-b]
[3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 6, 8, 7, 6, 7, 8, 7, 8, 7, 6, 10, 8, 9, 6, 9, 8, 8, 8, 7, 8, 6, 10, 7, 10, 6]
? 

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.
? 

All 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
?