Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
    
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? –  Gerry Myerson Jul 5 '11 at 4:13
    
@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. –  Charles Jul 5 '11 at 4:20
    
@Gerry Myerson: For the second, I'll edit in some statistics tomorrow. –  Charles Jul 5 '11 at 5:08
    
I take it then your support is statistical, not theoretical. –  Gerry Myerson Jul 5 '11 at 5:46
    
@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. –  Charles Jul 5 '11 at 5:59

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.