# Mathematical notation/name for the number of times a number can be divided by 2

I am using this simple snippet of code, variants of which I have seen in many places:

for(int k = 0 ; n % 2 == 0 ; k++)
n = n / 2;


This code repeatedly divides num by 2 until it is odd and on completion k contains the number of divisions performed.

I am wondering what the appropriate way to write this using mathematical notation is? Does this correspond to some named concept?

Of course, $lg\ n$ gives the appropriate $k$ when $n$ is a power of 2, but not for anything else. For example, $k = 1$ when $n = 6$ and $k = 0$ when $n$ is odd. So it looks it should be specified using a piece-wise function but there may be some mathematical concept or nomenclature here that I am not aware of...

-
how about just the largest $k$ such that $n=2^{k}\times n'$? – picakhu Aug 1 '11 at 15:43

If you want to be excessively fancy, you can call it the $2$-adic valuation $\nu_2(n)$.

-
What if I wanted to use a divisor that is not prime? (Say for example, substitute 8 for 2 in the code snippet above) – David Aug 1 '11 at 20:44
@David: well. That function doesn't behave as nicely as the $p$-adic valuation does. Can I ask what application you have in mind? – Qiaochu Yuan Aug 1 '11 at 20:49
@Qiaochu Powers of 2 is what I was interested in (I am using the code above), and I was just curious about other numbers. I was just trying to find a succinct mathematical way to describe what the code is doing. Thanks. – David Aug 1 '11 at 20:56
@David: well, even for composite $n$ you can talk about the $n$-adic valuation and people who know what $p$-adic valuation means will be able to guess what you mean, but again, it doesn't behave as nicely as the $p$-adic valuation. – Qiaochu Yuan Aug 1 '11 at 21:05
@David: Since a number factors uniquely into products of powers of primes, you can always talk about the $p$-adic valuation to yield the information you want. For instance, if you want to talk about the $8$-adic valuation, just note that $8 = 2^3$. Thus, $\mathop{ord}_8(n) = 3 \left\lfloor \frac{\mathop{ord}_2(n)}{3} \right\rfloor$. Unless $n$ has a lot of different prime factors, this should be fairly straightforward to deal with. – JavaMan Aug 3 '11 at 19:27

Number theorists use the notaton $\operatorname{ord}_p(n) = k$ to mean that $p^k$ is the largest power of $p$ that divides $n$. In other words, $p^k | n$, but $p^{k+1}$ does not. It is also of note that $\operatorname{ord}_p(0) = \infty$ for each $p$.

See here for more.

-

You might call it the "highest power of $2$ dividing $n$," but I'm not aware of any snazzy standalone term for such a thing. However, I have seen it notated succinctly as $2^k\|n$, which means $2^k$ divides into $n$ but $2^{k+1}$ does not.

-
Shows up here anyway, "104 Number Theory Problems - From the Training of the USA IMO Team" says $p^k$ fully divides $n$ is denoted $p^k\mid\mid n$ – ttt Aug 1 '11 at 16:09

For prime numbers in general it is sometimes called the multiplicity of the prime (implicitly meaning the multiplicity of the prime in the prime factorisation).

-