Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Last active March 2, 2026 08:19
Show Gist options
  • Select an option

  • Save Hermann-SW/7d32e298cb3e3ce234a4d534fae5e726 to your computer and use it in GitHub Desktop.

Select an option

Save Hermann-SW/7d32e298cb3e3ce234a4d534fae5e726 to your computer and use it in GitHub Desktop.
3 prime factor Charmichael number examples for roughly every 3 decimal digits up to 343
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 Mar 2, 2026

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