Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Last active March 5, 2026 15:18
Show Gist options
  • Select an option

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

Select an option

Save Hermann-SW/7615a6e6121d5f743bf7a4086ccc5672 to your computer and use it in GitHub Desktop.
There are no further Carmichael numbers N=2^a*3^b+1 below 10^70 (than 1729=2^6*3^3+1 and 46656=2^6*3^6+1)
is_carmichael_minus_1(f)={
n=factorback(f)+1;
v=[d+1|d<-divisors(n-1),n%(d+1)==0&&isprime(d+1)];
vecprod(v)==n; \\ Korselt's criterion
}
m=10^70;
{
for(a=1,oo,
if(2^a<=m,
for(b=1,oo,
if(2^a*3^b<=m,
f=Mat([2,a;3,b]);
n=factorback(f)+1;
if(issquarefree(n)&&#factorint(n)[,1]>2,
if(is_carmichael_minus_1(f),print(factorback(f)" "f));
),
break;
);
),
break;
);
);
}
@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 5, 2026

Only 91 minutes single core at 5.5GHz boost frequency of AMD 7950X CPU, since the number of N-1 divisors is not that big:

hermann@7950x:~$ time gp -q < 23.gp 
1728 [2, 6; 3, 3]
46656 [2, 6; 3, 6]

real	90m16,672s
user	90m16,367s
sys	0m0,015s
hermann@7950x:~$ 

Runtime for up to 10^60 was 13 minutes:

hermann@7950x:~$ time gp -q < 23.gp 
1728 [2, 6; 3, 3]
46656 [2, 6; 3, 6]

real	12m25,485s
user	12m25,411s
sys	0m0,033s
hermann@7950x:~$

There are no other Carmichael numbers N with N=2^a*x^b+1 below 10^22:
https://gist.github.com/Hermann-SW/f25c10f76b5eb1f589b7eb8716608140?permalink_comment_id=6012806#gistcomment-6012806

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