0
$\begingroup$

This is a variation of this question. I want to find the number of factors for a given large integer that I already know to be a power of 2.

Given that the number is a power of 2, does that help by eliminating most scenarios e.g.

  • factors cannot be odd.
  • at least one number of a factor pair has to be a power of 2 itself.

Question:

  • What other properties does the power series of 2 have that I can use to find factors more efficiently?
  • How can I represent the same in the form of an equation or function?
  • 0
    @GerryMyerson: I am not familiar with that and am looking it up.2012-08-05

2 Answers 2

6

If you already know the number is a power of 2, then all the factors are also powers of 2. So, if $n=2^k$, then the factors are $1, 2, 2^2, \dots 2^k$, and there are exactly $k+1$ of them.

  • 0
    I suppose you might not know which power of $2$ your integer is, but it's pretty easy to find out quickly.2012-08-05
2

This is trivial. The prime factors are just 2, repeated. The divisors are $2^m$ for $0 \le m \le \lg(n)$, where $n$ is the power of 2 to be factored. The number of such divisors is then $\lg(n) + 1$. (Here, $\lg$ is the base-2 logarithm.)