5
$\begingroup$

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...

  • 0
    how about just the largest $k$ such that $n=2^{k}\times n'$?2011-08-01

4 Answers 4

9

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

  • 0
    @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.2011-08-03
7

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.

2

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.

  • 0
    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$2011-08-01
0

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).