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
    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.2012-04-21
  • 0
    For a program (extra chars)2012-04-21
  • 0
    If it's natural to represent the number as binary, then count the number of rightmost zeros.2012-04-21
  • 0
    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.$2012-04-21
  • 1
    @Weaam You beat me to it :)2012-04-21
  • 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