Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/Car_3.343dd.gp

Last active March 2, 2026 08:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Hermann-SW/7d32e298cb3e3ce234a4d534fae5e726 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Hermann-SW/7d32e298cb3e3ce234a4d534fae5e726 to your computer and use it in GitHub Desktop.
Download ZIP
3 prime factor Charmichael number examples for roughly every 3 decimal digits up to 343
Raw
Car_3.343dd.gp
assert(b)=if(!(b),error());
factmul(f1,f2)=matreduce(matconcat([f1,f2]~));
factval(F)=vecprod([v[1]^v[2]|v<-F~]);
{Redu=[0,25,0,25,110,291,51,146,131,511,111,95,1121,2685,820,12481,16175,1866,
4500,11525,8960,441,390,14796,1280,1651,1730,24140,21226,18555,43391,3716,2980,
46701,38580,15450,5560,19445,14376,83660,32560,7516,5060,23806,57806,44636,
28985,73445,60936,55146,91400,82190,54255,8016,25591,71945,259946,147035,11301,
3375,2371,18486,466191,436551,422806,6220,153406,493275,222755,1572896,453141,
5385,422511,663666,364225,84081,52590,916505,285466,827301,5671,137266,120160,
23755,202690,140935,503151,560981,1528285,2474481,527805,660190,391711,
1161251,2985,727031,984236,494371,311091,517321,289351,496466,143956,33130,
1394135,166086,484375,4787525,2336340,338141,50106,411670,822656,507900];}
Car_3_m=Redu;for(i=1,#Redu,Car_3_m[i]=10^(i-1)+Redu[i]);
Car_3_pqr=[pqr|m<-Car_3_m;p<-[6*m+1];q<-[12*m+1];r<-[18*m+1];pqr<-[[p,q,r]]];
Car_3_n=[n|pqr<-Car_3_pqr;n<-[pqr[1]*pqr[2]*pqr[3]]];
Car_3_npqr=[[n,p,q,r]|i<-[1..#Car_3_n];n<-[Car_3_n[i]];\
pqr<-[Car_3_pqr[i]];p<-[pqr[1]];q<-[pqr[2]];r<-[pqr[3]]];
Quick=Set(concat([1..38],\
[41,42,43,45,47,48,50,51,54,55,59,67,70,73,76,79,81,93,111,114]));
Carfactorint(i)={
if(i==80,
return([2,4;3,5;29,1;101,1;2879,1;3527,1;794593,1;154660403,1;1375778713,1;
82559127467,1;2191141520677,1;5244008545913,1;215523228663966371,1;
727945109737073604951121,1;3071482538062826439493217,1;
405473649637074755617787593281337701367,1;
357632907601311950933336045572973824205399821454828478880978313,1]
)
);
[n,p,q,r]=Car_3_npqr[i];
np=(n-1)/gcd(n-1,p-1);npq=np/gcd(np,q-1);npqr=npq/gcd(npq,r-1);
F=factmul(factorint((n-1)/npqr),factorint(npqr));
assert(n-1==factval(F));
F
};
@Hermann-SW
Copy link
Author

Hermann-SW commented Feb 25, 2026

I created this gist to have Carmichael numbers of reasonable size, that allow for fast factorization of n-1.
Not all of this gist Carmichael numbers allow for that.
Indices allowing fast (less than 3s) factorization (with npqr trick in Carfactorint()) are in vector Quick.
There are holes, but even for big numbers every 40 decimal digits a next fast to factor can be found:

? foreach(Quick,i,print1(#digits(Car_3_n[i])","))
4,8,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73,76,79,82,85,88,91,94,97,100,103,106,109,112,115,124,127,130,136,142,145,151,154,163,166,178,202,211,220,229,238,244,280,334,343,
?

Confirmation that factorization times are indeed less than 3000ms for all indices in Quick:

? foreach(Quick,i,gettime();Carfactorint(i);print1(gettime()","))
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,38,0,2,1,89,117,685,1,13,16,429,231,2364,1470,0,130,3,3,413,610,14,1795,316,0,9,80,52,327,565,1179,2028,523,426,0,1,2156,1408,
cpu time = 17,490 ms, real time = 17,491 ms.
?

@Hermann-SW
Copy link
Author

Hermann-SW commented Feb 26, 2026 •
edited
Loading

Nested infinite loops used to generate the compressed vector Redu entries.
Terminated after 2.5h real and 8.5h cpu time (PARI/GP isprime()is multithreaded):

good(m)=isprime(6*m+1)&&isprime(12*m+1)&&isprime(18*m+1);
for(d=0,oo,for(m=10^d,oo,if(good(m),print1(m-10^d,",");break)));

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 1, 2026 •
edited
Loading

Efforts to determine other factorizations of n-1 for Carmichael numbers n:
https://www.mersenneforum.org/node/1106355?p=1106709#post1106709

New index 80 fully factorized, 63 decimal digits prime is largest prime factor of 241 decimal digits n-1:

hermann@j4105:~$ gp -q Car_3.343dd.gp
? n=Car_3_n[80];
? #digits(n)
241
? F=Carfactorint(80);
? ##
  ***   last result computed in 0 ms.
? n-1==factval(F)
1
? for(i=1,#F-1,if(F[i,1]>=F[i+1,1],print("wrong "i)))
? [isprime(p)|p<-F[,1]]
time = 1,088 ms.
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
? print(Carfactorint(80))
[2, 4; 3, 5; 29, 1; 101, 1; 2879, 1; 3527, 1; 794593, 1; 154660403, 1; 1375778713, 1; 82559127467, 1; 2191141520677, 1; 5244008545913, 1; 215523228663966371, 1; 727945109737073604951121, 1; 3071482538062826439493217, 1; 405473649637074755617787593281337701367, 1; 357632907601311950933336045572973824205399821454828478880978313, 1]
?

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 2, 2026 •
edited
Loading

Chernick, Jack. “On Fermat's simple theorem.” Bulletin of the American Mathematical Society 45 (1939): 269-274.
https://www.ams.org/journals/bull/1939-45-04/S0002-9904-1939-06953-X/S0002-9904-1939-06953-X.pdf

There are more forms of Carmichael numbers with 3 primes:
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment