Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
    
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
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.