1
$\begingroup$

Suppose we know that $n$, a number of a hundred digits or more, is composite. It must have at least two prime factors (not necessarily distinct), but no more than $\lfloor \log_2 n \rfloor$ prime factors.

Depending on how $n$ was found, whether by a pseudorandom or truly random process, it seems unlikely to be a power of $2$. It is far more likely to be the square of a prime, but even so it seems far more likely to have $\lfloor \frac{\log_2 n}{2} \rfloor$ factors.

For instance, if $n = 10^{100} + 11$, it's obviously not a power of $2$. It is also easy to see that it is divisible by $3$, which effectively rules out the possibility that it could be the square of a prime. Wolfram Alpha tells me that this specific number has at least four prime factors, two of which are $7549$ and $9604831$, but it could just as easily have fifty prime factors (that's just a wild guess on my part).

Is it possible to refine this guessing function so that it's not too far off from $\Omega(n)$, and if it is way off, it is at least a good guess for many neighboring numbers, like $n - 3$ and $n + 2$?

$\endgroup$
3

1 Answer 1

4
$\begingroup$

The Erdos-Kac theorem says that, given large $n,$ you should guess $$ \log \log n $$ prime factors.

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem

There is a less precise statement proved in Hardy and Wright, that the "normal order" of both $\omega(n)$ and $\Omega(n)$ is $\log \log n.$ This is Theorem 431, in my edition page 356.

Alright, Kac does the Theorem on page 75 of his little book. The statement the $\omega(n)$ is normally distributed with mean $\log \log n$ and standard deviation $\sqrt {\log \log n}$ is formula (5.4) on page 75. Then, on page 79, Problem 1. is simply to show that (5.4) holds for $\Omega(n),$ that is, counting multiplicities. His notation is a little different.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .