Maths Olympiad Prep

Library / /483 of 860

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. Spacing and $ signs are ignored.

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 and solution reproduced as published; topic and difficulty added by this site.