For a positive integer , denote with the maximum power of that divides .
Prove that for any positive integer that:
(FYROM)
For a positive integer , denote with the maximum power of that divides .
Prove that for any positive integer that:
(FYROM)
1. Lemma: is equal to the number of 's in the binary representation of .
2. Proof of Lemma: This is a direct application of Kummer's Theorem, which states that the power of a prime dividing a binomial coefficient is equal to the number of carries when and are added in base . For , this translates to the number of 's in the binary representation of .
3. Main Proof:
We need to prove that:
4. Using the lemma, we have:
5. According to the lemma, is the number of 's in the binary representation of . Therefore, we need to sum the number of 's in the binary representations of all integers from to .
6. The number of 's in the binary representation of numbers from to can be calculated as follows:
- For each bit position (from to ), there are numbers that have a in that position.
- Therefore, the total number of 's in the binary representations of numbers from to is:
7. However, we need to account for the fact that itself has exactly one in its binary representation, which adds an additional to the sum.
8. Therefore, the total sum is:
9. Hence, we have: