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.

Not sure if worded properly.

For instance, the highest multiplicity of 2 in 60 is 2 because the prime factorization of 60 is 2^2*3*5.

For 16, the highest multiplicity of 2 would be 4, etc. Is there a good way to find this without constantly dividing 60 by 2 and counting how many times you end up with a whole number?

share|improve this question
    
What is the application? Just doing this by hand for some numbers less than a trillion, or are you writing a computer program to do this for bigger numbers? If by hand, what you have said is probably the best way, and isn't even that bad. This problem is closely related to finding the prime factorization of a number, which isn't very quick even for computers. –  Ragib Zaman Apr 21 '12 at 14:42
    
For a program (extra chars) –  John Smith Apr 21 '12 at 14:46
    
If it's natural to represent the number as binary, then count the number of rightmost zeros. –  Weaam Apr 21 '12 at 14:55
    
Notice also that $2$ specifically is nice for computers. In binary, count the number of zeros to the right. Example: $60 \equiv 111100.$ So we have $2$ zeros, which is equivalent to saying $2^2 \mid 60.$ –  user2468 Apr 21 '12 at 14:56
1  
@Weaam You beat me to it :) –  user2468 Apr 21 '12 at 14:56

1 Answer 1

up vote 2 down vote accepted

Problem: Given $x,$ find whether 2^d is a factor of $x.$

Using the Euclidean algorithm, which is fast (see: 1, 2, 3), we have

$$\gcd(x, 2^{\lceil{\log_2{x}}\rceil}) = \begin{cases} 2^d & \text{if } 2^d \mid x \\ 1 & \text{if } 2^d \not\mid x \end{cases}$$

Edit for clarification:

If $2^d$ is a factor $x$, then $x = y 2^d$, where $y$ is the rest of factors. Then we can clearly see that $\gcd(y2^d, 2^d) = 2^d).$ If $2^d$ is not a factor of $x,$ then $\gcd = 1.$

The ceiling business makes sure that we cover the largest possible $d.$ I.e., find a bound $b$ such that $x \le 2^b.$ Take $\log$ both sides.. rest is exercise.

share|improve this answer
    
Based on the current approach of multiple divisions, I think the gcd formula is basically doing something similar anyway. –  John Smith Apr 21 '12 at 14:47

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.