Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

4 Answers 4

up vote 9 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer
    
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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.