1
$\begingroup$

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?

  • 0
    It doesn't have to be a power of$2$necessarily -- could be any divisor2012-04-21

1 Answers 1

2

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.

  • 0
    Based on the current approach of multiple divisions, I think the gcd formula is basically doing something similar anyway.2012-04-21