# Factoring for extremely large numbers that are a power of 2.

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?
-
Are you familiar with the Unique Factorization Theorem? It's a must for anyone interested in factoring integers. –  Gerry Myerson Aug 5 '12 at 10:43
What do you mean by the "power series of 2"? –  mike4ty4 Aug 5 '12 at 11:38
@mike, I take it Raheel just means the series of powers of 2. –  Gerry Myerson Aug 5 '12 at 12:07
@mike4ty4: Gerry's comment is correct. I meant any number that is a power of 2. –  Raheel Khan Aug 5 '12 at 14:05
@GerryMyerson: I am not familiar with that and am looking it up. –  Raheel Khan Aug 5 '12 at 14:06

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.

-
I suppose you might not know which power of $2$ your integer is, but it's pretty easy to find out quickly. –  Geoff Robinson Aug 5 '12 at 11:25

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.)

-