1. Tabulating Carmichael numbers n=Pqr with small P.
- Author
-
Shallue, Andrew and Webster, Jonathan
- Subjects
- *
PRIME numbers , *INTEGERS , *MATHEMATICS , *DIVISOR theory - Abstract
We revisit the problem of tabulating Carmichael numbers. Carmichael numbers have been tabulated up to 10 21 using an algorithm of Pinch (Math Comp 61(203):381–391, 1993). In finding all Carmichael numbers with d prime factors, the strategy is to first construct pre-products P with d - 2 prime factors, then find primes q and r such that Pqr satisfies the Korselt condition. We follow the same general strategy, but propose an improvement that replaces an inner loop over all integers in a range with a loop over all divisors of an intermediate quantity. This gives an asymptotic improvement in the case where P is small and expands the number of cases that may be accounted as small. In head-to-head timings this new strategy is faster over all pre-products in a range, but is slower on prime pre-products. A hybrid approach is shown to improve even the case of prime pre-products. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF