2-Adic Valuation

The 2-adic valuation, denoted $ v_2 $, is the function that measures the power of 2 dividing a number. For a non-zero integer $ n $, $ v_2(n) $ is the exponent of 2 in its prime factorization.

More generally, $ v_2(n) $ indicates how many times $ n $ is divisible by 2. By convention, $ v_2(0) = +\infty $ and $ v_2(-n) = v_2(n) $

For a natural number $ n > 0 $, perform successive divisions by 2 and count the number of exact divisions before obtaining an odd quotient. This number is $ v_2(n) $. Equivalently, $ v_2(n) $ is the largest integer $ k $ such that $ 2^k $ divides $ n $.

An even number satisfies $ v_2(n) \geq 1 $, while an odd number satisfies $ v_2(n) = 0 $

For a non-zero positive integer, write the number in base 2 and count the trailing zeros, i.e., the zeros located to the right of the binary representation. This number is exactly $ v_2(n) $.

For a non-zero rational $ a/b $, with $ a \neq 0 $ and $ b \neq 0 $, extend the valuation by the formula $ v_2(a/b) = v_2(a) - v_2(b) $. This definition does not depend on the chosen representation of the rational.

Use Legendre's formula $ v_2(n!) = \sum_{k\geq1} \left\lfloor n/2^k \right\rfloor $

The sum stops as soon as $ 2^k > n $

Another useful formula is $ v_2(n!) = n-s_2(n) $, where $ s_2(n) $ is the number of 1 digits of $ n $ written in base 2