HMMT February, 2020

Number theory Difficulty 5.2 AIME, harder Find the answer United States

Problem:
For positive integers $n$ and $k$ , let $\mho(n, k)$ be the number of distinct prime divisors of $n$ that are at least $k$ . For example, $\mho(90,3)=2$ , since the only prime factors of $90$ that are at least $3$ are $3$ and $5$ . Find the closest integer to
$\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} \frac{\mho(n, k)}{3^{n+k-7}}$

Your answer

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

Solution

Solution:
A prime $p$ is counted in $\mho(n, k)$ if $p \mid n$ and $k \leq p$ . Thus, for a given prime $p$ , the total contribution from $p$ in the sum is
$3^{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 \in \{2,3,5,7, \ldots\}$ we get
$\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 $\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.