The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so would appreciate a verbose description of equations.

The Problem:

The integer in question will ALWAYS be a power of N and will be known to us to calculate against. So let's assume N = 2 for example. That will give us a sequence of numbers like:

2, 4, 8, 16... up to hundreds of thousands of digits.

I need to find all possible factors (odd, even, prime, etc.) as efficiently as possible.

The Question:

What is the solution and how could I understand this from mathematical and computational perspectives?


Does the fact that each number to be factored is a power of 2 help in eliminating any complexity or computational time?


If $N = 2$ (or any prime) and you can get $k$ as Ross indicated, then the divisors of $A$ are $\{1, N, N^2, \ldots, N^i, \ldots, N^{k} \}.$ If $N$ is a composite, then you will incur extra time complexity in computing the prime factorization of $N = \prod_{i = 1}^{\ell} p_i^{e_i}$ and the divisors of $A$ are all possible numbers of the form $\prod_{i=1}^{\ell} p_i^{r_i}$ where $\mathbf{0} \le r_i \le ke_i.$ Notice $r_i$ can be zero for some terms. There are $\prod_{i=1}^{\ell}(ke_i + 1)$ such possible divisors.

  • $\begingroup$ Given 2^100 = 1,267,650,600,228,229,401,496,703,205,376, would that mean there are 100 possible factors? $\endgroup$ – Raheel Khan Jul 29 '12 at 21:08
  • 1
    $\begingroup$ $101$ ${}{}{}{}{}{}{}{}{}$ $\endgroup$ – André Nicolas Jul 29 '12 at 21:17
  • $\begingroup$ @RaheelKhan Simpler example: $2^5.$ There are 6 divisors: $2^0 = 1,$ $2^1 = 2,$ $2^2 = 4,$ $2^3 = 8,$ $2^4 = 16,$ and $2^5 = 32.$ The numbers $1$ and $2^k$ itself are counted in. $\endgroup$ – user2468 Jul 29 '12 at 21:22
  • $\begingroup$ Thanks. I'm presuming 101 includes the number 1. $\endgroup$ – Raheel Khan Jul 29 '12 at 21:23
  • $\begingroup$ Yes, $101$ includes both $1$ and $2^{100}.$ $\endgroup$ – user2468 Jul 29 '12 at 21:23

If the number in question is known to be a power of 2, you are just trying to find $n$ such that $N=2^n$. If the input number is in decimal notation, just count the digits, subtract 1, multiply by 3.3219, and round up. Then add 1 if the initial digit is 2 or 3, 2 if the initial digit is 4, 5, 6, or 7, and 3 if the initial digit is 8 or 9.

For example, suppose $N=1267650600228229401496703205376$. This has 31 digits; $30\cdot3.3219 = 99.657$, so $N=2^{100}$. Or take $N=$


which has 246 digits. $245\cdot3.3219 = 813.872383$; we round up to 814, add 2 because the first digit is 4, so this number is $2^{816}$.

The magic constant 3.3219 is actually $\log 10 / \log 2$. For input numbers in the hundreds of thousands of digits you will need a more accurate version, say 3.3219281.


Are you given $N$? Then if the number to be factored is $A$, you have $A=N^k$ and only have to find $k$. Taking logs, $k=\frac {\log A}{\log N}$. So, yes, if you know $N$ it helps a lot.

If $N$ is prime, all the possible factors of $A$ are of the form $N^m$ for $0 \le m \le k$ so you have them. If $N$ is composite, factor it as $N=p_1^{q_1}p_2^{q_2}\ldots p_n^{q_n}$. Then all the factors are of the form $p_1^{m_1}p_2^{m_2}\ldots p_n^{m_n}$ where $0 \le m_1 \le kq_1$ etc.

  • $\begingroup$ Yes we will know N and can assume it to be 2 in this case. $\endgroup$ – Raheel Khan Jul 29 '12 at 20:34

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.