Quick way to find the highest multiplicity of a divisor of a number?

Question

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?

Answer 1

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.

Answer 2

Here's a relatively simple approach with fewer division operations.

Start with number $n$ and possible divisor $d$.

Divide $n$ by $d$ to get $n_1$; divide $n_1$ by $d^2$ to get $n_2$; divide $n_2$ by $d^4$ to get $n_3$; and so forth, each time squaring the power of $d,$ until you find a number $n_k$ that is not divisible by $d^{2^k}.$

At this point you know that $n = d^{2^k - 1} n_k$ and that the multiplicity of the divisor $d$ in $n_k$ is at most $2^k - 1.$

Let $p_k = 0.$ Let $m_k = n_k.$ For $i = k, k-1, k-2, \ldots, 1$ in turn, let $m_{i - 1} = m_i/d^{2^{i - 1}}$ and let $p_{i - 1} = p_i + 2^{i - 1}$ if $m_i$ is divisible by $d^{2^{i - 1}}$; otherwise let $m_{i - 1} = m_i$ and let $p_{i - 1} = p_i.$

When you have computed $m_0,$ then $p_0$ will be the multiplicity of $d$ as a divisor of $n_k.$

Then the multiplicity of $d$ as a divisor of $n$ is $2^k - 1 + p_0.$

The number of divisions that must be performed is $O(\log(p))$ where $p$ is the multiplicity of $d$ as a divisor of $n,$ so the number of divisions is $O(\log\log(n)).$

I think you may be able to get similar big-O performance from the Euclidean algorithm mentioned in another answer if you use that technique to perform a binary search for the largest power of $d$ that divides $n.$ I just think this method is a bit simpler and may have a lower constant factor.