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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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