2
$\begingroup$

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them?

Even an estimation would help as long as it has some relevance to the number in question.

$\endgroup$
  • 1
    $\begingroup$ A very crude upper bound for the number of factors of $n$ is$\lfloor \ln_2(n) \rfloor$ (here $\lfloor . \rfloor$ denotes the floor function) : since $n = 2^{\ln_2(n)}$ and each factor of $n$ is $\ge 2$, there can be no more than $\lfloor \ln_2(n) \rfloor$ factors. The only lower bound that works for every number is $1$ (if $n$ is prime, this bound is sharp). $\endgroup$ – Joel Cohen Jul 29 '12 at 20:50
  • $\begingroup$ Note that in my previous comment, I took "factor" to mean "prime factor" and not "divisor". $\endgroup$ – Joel Cohen Jul 29 '12 at 20:59
  • $\begingroup$ @JoelCohen: I do not want to discriminate. I'm looking for all possible integer divisors (odd, even, prime, etc.). $\endgroup$ – Raheel Khan Jul 29 '12 at 21:07
  • 1
    $\begingroup$ see mathoverflow.net/questions/43103/… Meanwhile if you email me, you can have a pdf of the 1988 survey by J.-L. Nicolas with these results and explanations. $\endgroup$ – Will Jagy Jul 29 '12 at 21:11
  • $\begingroup$ @WillJagy: Where should I email you? $\endgroup$ – Raheel Khan Jul 30 '12 at 16:54
3
$\begingroup$

As others have noted, there are bounds. But you can have, say, two 1000-digit numbers, differing only in their 778th digit, one of the numbers having zillions of factors, the other being prime, or a product of two primes. There is, in general, no way to get much information about the number of possible factors (or odd factors, or even factors, or prime factors, or repeated factors, etc., etc.) without factoring the number.

$\endgroup$
3
$\begingroup$

If the prime factorization of $N$ is $p_1^{d_1} \ldots, p_n^{d_n}$, then $N$ has $(d_1+1)\ldots(d_n+1)$ divisors. This number of divisors is denoted $d(N)$. A crude upper bound on $d(n)$ is $2 \sqrt{ n}$. A better estimate is

$\log d(n) \le \dfrac{\log n}{\log \log n} (\log 2 + O(1/\log\log n))$

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