HMMT-Nov 2023 guts, Problem 36

Isabella writes the expression $\sqrt{d}$ for each positive integer $d$ not exceeding 8 ! on the board. Seeing that these expressions might not be worth points on HMMT, Vidur simplifies each expression to the form $a \sqrt{b}$, where $a$ and $b$ are integers such that $b$ is not divisible by the square of a prime number. (For example, $\sqrt{20}, \sqrt{16}$, and $\sqrt{6}$ simplify to $2 \sqrt{5}, 4 \sqrt{1}$, and $1 \sqrt{6}$, respectively.) Compute the sum of $a+b$ across all expressions that Vidur writes. Submit a positive real number $A$. If the correct answer is $C$ and your answer is $A$, you get $\max \left(0,\left\lceil 20\left(1-|\log (A / C)|^{1 / 5}\right)\right\rceil\right)$ points.

Solution: Solution: Let $\sqrt{n}$ simplifies to $a_{n} \sqrt{b_{n}}$, and replace 8 ! by $x$. First, notice that $\sum_{n \leq x} a_{n}$ is small $\left(O\left(x^{3 / 2}\right)\right.$ in particular) because each term cannot exceed $\sqrt{x}$. On the other hand, $\sum_{n \leq x} b_{n}$ will be large; we have $b_{n}=n$ when $n$ is squarefree, and squarefree numbers occurs $\frac{6}{\pi^{2}}$ over the time. Thus, it suffices to consider $\sum_{n \leq x} b_{n}$. We first explain how to derive the formula heuristically. Then, we will provide a rigorous proof that \[ B(x):=\sum_{n \leq x} b_{n}=\frac{\pi^{2}}{30} x^{2}+O\left(x^{3 / 2}\right) \] For heuristic explanation, we first rewrite the sum as \[ B(x)=\sum_{\substack{a^{2} b \leq x \\ b \text { squarefree }}} b=\sum_{a \leq x} \sum_{\substack{b \leq x / a^{2} \\ b \text { squarefree }}} b \] We estimate the inner sum as follows: first, recall that the density of squarefree numbers is $\frac{6}{\pi^{2}}$. The sum of first $k$ positive integers is approximately $k^{2} / 2$, so the sum of squarefree numbers from $1,2, \ldots, k$ should roughly be about $\frac{6}{\pi^{2}} \cdot \frac{k^{2}}{2}=\frac{3}{\pi^{2}} k^{2}$. Knowing this, we estimate \[ \begin{aligned} B(x) & \approx \sum_{a \leq x} \frac{3}{\pi^{2}}\left(\frac{x}{a^{2}}\right)^{2} \\ & =x^{2} \sum_{a \leq x} \frac{3}{\pi^{2}} \frac{1}{a^{4}} \\ & \approx \frac{3}{\pi^{2}} x^{2} \sum_{a=1}^{\infty} \frac{1}{a^{4}} \\ & =\frac{3}{\pi^{2}} x^{2} \cdot \frac{\pi^{4}}{90}=\frac{\pi^{2}}{30} x^{2} \end{aligned} \] The estimate $\frac{\pi^{2}}{30} \cdot(8 !)^{2}=534834652$ is good enough for 18 points. We now give a rigorous proof, which is essentially the above proof, but the errors are properly treated. To do that, we need several lemmas and some standard techniques in analytic number theory. Lemma 1. The number of squarefree integers not exceeding $x$ is $\frac{6}{\pi^{2}} x+O(\sqrt{x})$. Proof. This is a standard result in analytic number theory, but we give the full proof for completeness. \[ \mu(n)= \begin{cases}(-1)^{r} & n \text { is the product of } r \geq 0 \text { distinct primes } \\ 0 & \text { otherwise. }\end{cases} \] Then, by Inclusion-Exclusion, we have \[ \begin{aligned} \#\{\text { squarefree } \leq x\} & =\sum_{k \leq \sqrt{x}} \mu(k)\left\lfloor\frac{x}{k^{2}}\right\rfloor \\ & =\sum_{k \leq \sqrt{x}} \mu(k) \frac{x}{k^{2}}+O(\sqrt{x}) \\ & =x\left(\sum_{k \leq \sqrt{x}} \frac{\mu(k)}{k^{2}}\right)+O(\sqrt{x}) \end{aligned} \] The inner summation is \[ \begin{aligned} \sum_{k=1}^{\infty} \frac{\mu(k)}{k^{2}}+O\left(\sum_{k \geq \sqrt{x}} \frac{1}{k^{2}}\right) & =\prod_{p \text { prime }}\left(1-\frac{1}{p^{2}}\right)+O\left(\frac{1}{\sqrt{x}}\right) \\ & =\frac{1}{1+\frac{1}{2^{2}}+\frac{1}{3^{2}}+\ldots}+O\left(\frac{1}{\sqrt{x}}\right) \\ & =\frac{6}{\pi^{2}}+O\left(\frac{1}{\sqrt{x}}\right) \end{aligned} \] so putting it together, we get that \[ \#\{\text { squarefree } \leq x\}=x\left(\frac{6}{\pi^{2}}+O\left(\frac{1}{\sqrt{x}}\right)\right)+O(\sqrt{x})=\frac{6}{\pi^{2}} x+O(\sqrt{x}) \] Lemma 2. We have \[ \sum_{\substack{n \text { squarefree } \\ n \leq x}} n=\frac{3}{\pi^{2}} x^{2}+O\left(x^{3 / 2}\right) \] Proof. We apply Abel's summation formula on the sequence $a_{n}=\mathbf{1}_{\text {squarefree }}(n)$ and weight $\phi(n)=n$. Define the partial summation $A(x)=\sum_{n \leq x} a_{n}$. Applying Abel's summation, we get that \[ \begin{aligned} \sum_{\substack{n \text { squarefree } \\ n \leq x}} n & =\sum_{n \leq x} a_{n} \phi(n) \\ & =A(x) \phi(x)-\int_{1}^{x} A(t) \phi^{\prime}(t) d t \\ & =\left(\frac{6}{\pi^{2}} x+O(\sqrt{x})\right) x-\int_{1}^{x}\left(\frac{6}{\pi^{2}} t+O(\sqrt{t})\right) d t \\ & =\left(\frac{6}{\pi^{2} x}+O\left(x^{3 / 2}\right)\right)-\left(\frac{6}{\pi^{2}} \cdot \frac{x^{2}}{2}+O\left(x^{3 / 2}\right)\right) \\ & =\frac{3}{\pi^{2}} x^{2}+O\left(x^{3 / 2}\right) \end{aligned} \] Main Proof. Once we have Lemma 2., it is easy to get the desired estimate. We have \[ \begin{aligned} B(x) & =\sum_{\substack{a^{2} b \leq x \\ b \text { squarefree }}} b \\ & =\sum_{a \leq x} \sum_{\substack{b \leq x / a^{2} \\ b \text { squarefree }}} b \\ & =\sum_{a \leq x} \frac{3}{\pi^{2}} \frac{x^{2}}{a^{4}}+O\left(\frac{x^{3 / 2}}{a^{3}}\right) \\ & =\frac{3}{\pi^{2}} x^{2}\left(\sum_{a \leq x} \frac{1}{a^{4}}\right)+O\left(x^{3 / 2} \sum_{a \leq x} \frac{1}{a^{3}}\right) \end{aligned} \] Since $\sum_{a=1}^{\infty} \frac{1}{a^{3}}$ converges, we get that the big- $O$ term is indeed $O\left(x^{3 / 2}\right)$. Now, we only need to deal with the main term. Note the estimate \[ \sum_{a \leq x} \frac{1}{a^{4}}=\sum_{a=1}^{\infty} \frac{1}{a^{4}}-\sum_{a \geq x} \frac{1}{a^{4}}=\frac{\pi^{4}}{90}+O\left(\frac{1}{x^{3}}\right) \] Hence, we have \[ B(x)=\frac{3}{\pi^{2}} x^{2} \cdot \frac{\pi^{4}}{90}+O\left(x^{3 / 2}\right)=\frac{\pi^{2}}{30} x^{2}+O\left(x^{3 / 2}\right) \] as desired. Here is the code that gives the exact answer: $\fbox{534810086}$.

Answer: 534810086