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$?
No comments:
Post a Comment