Maths Olympiad Prep

Library / /480 of 841

Number theory Difficulty 5.2 AIME, harder Find the answer

For positive integers nn and kk, let (n,k)\mho(n, k) be the number of distinct prime divisors of nn that are at least kk. Find the closest integer to n=1k=1(n,k)3n+k7\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} \frac{\mho(n, k)}{3^{n+k-7}}

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

A prime pp is counted in (n,k)\mho(n, k) if pnp \mid n and kpk \leq p. Thus, for a given prime pp, the total contribution from pp in the sum is 37m=1k=1p13pm+k=37ip+113i=37p23^{7} \sum_{m=1}^{\infty} \sum_{k=1}^{p} \frac{1}{3^{p m+k}}=3^{7} \sum_{i \geq p+1} \frac{1}{3^{i}}=\frac{3^{7-p}}{2} Therefore, if we consider p{2,3,5,7,}p \in\{2,3,5,7, \ldots\} we get n=1k=1(n,k)3n+k7=352+342+322+302+ε=167+ε\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} \frac{\mho(n, k)}{3^{n+k-7}}=\frac{3^{5}}{2}+\frac{3^{4}}{2}+\frac{3^{2}}{2}+\frac{3^{0}}{2}+\varepsilon=167+\varepsilon where ε<i=1137i2=110812\varepsilon<\sum_{i=11}^{\infty} \frac{3^{7-i}}{2}=\frac{1}{108} \ll \frac{1}{2}. The closest integer to the sum is 167.

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.