Difference between revisions of "2021 GMC 10B Problems/Problem 18"
(Created page with "==Problem== Let <math>f(n)</math> be the largest possible power of <math>2</math> that divides <math>n</math>. Find <math>f((3^2-3)(4^2-4)(5^2-5)(6^2-6)(7^2-7)(8^2-8)...(99^2-...") |
m (→Solution) |
||
Line 5: | Line 5: | ||
==Solution== | ==Solution== | ||
− | Note that <math>f(n) = \nu_2 (n)</math>, where <math>\nu_2(k)</math> is the <math>2</math>-adic valuation of <math>k</math>. By LTE | + | Note that <math>f(n) = \nu_2 (n)</math>, where <math>\nu_2(k)</math> is the <math>2</math>-adic valuation of <math>k</math>. By [[Lifting_the_Exponent_Lemma|LTE]], |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
f((3^2-3)\dotsm(100^2-100)) &= f(3^2 - 3)+\dotsb + f(100^2 - 100) \ | f((3^2-3)\dotsm(100^2-100)) &= f(3^2 - 3)+\dotsb + f(100^2 - 100) \ |
Revision as of 18:38, 7 March 2022
Problem
Let be the largest possible power of that divides . Find .
Solution
Note that , where is the -adic valuation of . By LTE,
To evaluate the sum, we use casework on the divisibility of over For example, for , we count the numbers from to which are divisible by . : numbers, : numbers, : numbers, : numbers, : numbers, : number, so adding, we get , and finishing, ~pineconee