Last active
March 5, 2026 15:18
-
-
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)
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
| 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; | |
| ); | |
| ); | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
Runtime for up to 10^60 was 13 minutes:
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