Number theoryDifficulty 5.1AIME, harderFind the answerUnited States
Problem:
Mark writes the expression d for each positive divisor d of 8! on the board. Seeing that these expressions might not be worth points on HMMT, Rishabh simplifies each expression to the form ab, where a and b are integers such that b is not divisible by the square of a prime number. (For example, 20, 16, and 6 simplify to 25, 41, and 16, respectively.) Compute the sum of a+b across all expressions that Rishabh writes.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Solution:
Let n simplify to anbn. Notice that both an and bn are multiplicative. Thus, ∑d∣nad and ∑d∣nbd are multiplicative.
We consider the sum ∑d∣pkad and ∑d∣pkbd. Notice that for d=pl, ad=p⌊l/2⌋ and bd=p2{l/2}, so d∣pk∑ad=2(p−1p(k+1)/2−1) and d∣pk∑bd=2(p+1)(k+1) for odd k, while d∣pk∑ad=(p−1p(k+2)/2+pk/2−2) and d∣pk∑bd=2(p+1)k+1 for even k.
Notice 8!=27⋅32⋅5⋅7, so d∣8!∑ad=(2−12(16−1))(3−19+3−2)(1+1)(1+1)=30⋅5⋅2⋅2=600 and d∣8!∑bd=(23⋅8)(1+24⋅2)(1+5)(1+7)=12⋅5⋅6⋅8=2880 so the sum of ad+bd would be 600+2880=3480.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.