Algorithms for Carmichael numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917197536821248 |
|---|---|
| author | Shallue, Andrew Webster, Jonathan |
| author_facet | Shallue, Andrew Webster, Jonathan |
| contents | Our primary concern is the computational complexity of algorithms that find all Carmichael numbers less than some specified bound $B$. We have three related results. First, we show CARMICHAELS is in $\textbf{P}$, where only the run-time is conditioned on the ERH. Second, we state a heuristically optimal tabulation algorithm, which is the first asymptotic improvement to tabulation algorithms in the $50$ years since Swift first described the prime-by-prime approach. Third, we implemented a related algorithm that tabulated $100$ times further while only doing about $5$ times the work of the prior tabulation. We found $308,279,939$ Carmichael numbers less than $10^{24}$ and we provide some statistics on these numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for Carmichael numbers Shallue, Andrew Webster, Jonathan Number Theory 11Y16 F.2 Our primary concern is the computational complexity of algorithms that find all Carmichael numbers less than some specified bound $B$. We have three related results. First, we show CARMICHAELS is in $\textbf{P}$, where only the run-time is conditioned on the ERH. Second, we state a heuristically optimal tabulation algorithm, which is the first asymptotic improvement to tabulation algorithms in the $50$ years since Swift first described the prime-by-prime approach. Third, we implemented a related algorithm that tabulated $100$ times further while only doing about $5$ times the work of the prior tabulation. We found $308,279,939$ Carmichael numbers less than $10^{24}$ and we provide some statistics on these numbers. |
| title | Algorithms for Carmichael numbers |
| topic | Number Theory 11Y16 F.2 |
| url | https://arxiv.org/abs/2506.09903 |