1
$\begingroup$

Hello world!

Now I'm implementing a stochastic (k-rounded) Fermat primality test for my annual scientific work. I know it is inefficient, but I do it for illustration only.

Well eventually I came up to a question: how inefficient it really is. So it does okay for a large amount of composites, but completely screws up for Carmichael numbers, except for the case when the randomly chosen witness occured to be a Carmichael number's factor.

And then the question was: how many factors do Carmichael numbers have? I mean, how does the number of factors grow with the length of the number? I haven't found any information on the topic, but it seems to be a curious question.

I'm not really a mathematician, so I kindly ask you to provide the answers as if they were addressed to a complete idiot.

3 Answers 3

1

There is a widely-believed (though not proved) hypothesis which implies that there are infinitely many Carmichael numbers with exactly $3$ prime factors (there are no Carmichael numbers with fewer than $3$ prime factors). In the other direction, as the answer from lhf suggests, undoubtedly there are Carmichaels with as many prime factors as you'd like.

1

As a first estimate, Carmichael numbers have as many factors as random numbers of similar size. You can use the Erdos-Kac theorem to estimate the number of prime factors, or simply use the mean: a number near $x$ has around $\log\log x$ prime factors on average.

Of course Carmichael numbers have at least three prime factors, so for small numbers you'll need to take that into account.

  • 0
    Note that $\log\log n\lt3$ for $n\lt500,000,000$, so some of those small numbers are pretty large. But do you have any support for the assertion that, this question of small numbers aside, Carmichael numbers have as many factors as random numbers of similar size?2011-07-05
  • 0
    @Gerry Myerson: For the first part, 'small' in this context is below, say, 10^15 where an appreciable fraction of numbers would otherwise have fewer than three prime factors.2011-07-05
  • 0
    @Gerry Myerson: For the second, I'll edit in some statistics tomorrow.2011-07-05
  • 0
    I take it then your support is statistical, not theoretical.2011-07-05
  • 0
    @Gerry Myerson: It would have to be, considering that AFAIK it's not even known that there are infinitely many Carmichael numbers with k prime factors for any given k.2011-07-05
0

Wikipedia says: Löh and Niebuhr in 1992 found some huge Carmichael numbers, including one with 1,101,518 factors and over 16 million digits. doi:10.1090/S0025-5718-96-00692-8