Let $\sigma(\cdot)$ denote the divisor sum function and $d(\cdot)$ denote the divisor counting function. Find all positve integers $n$ such that $\sigma(d(n))=n.$ Andrei Bâra
Problem
Source: Romania JBMO TST 2024 Day 3 P3
Tags: number theory, Arithmetic Functions
grupyorum
01.08.2024 11:01
Check first that for $d(N)\le 9$, $N=1,3,4,12$ are the only solutions. The cases $N\le 7$ are also handled analogously, so suppose in the remainder $d(N)\ge 10$ and $N\ge 8$. First, recall the well-known estimate $d(N)\le 2\sqrt{N}$.
Consider the pairs $(d,N/d)$ where $d\mid N$ and notice $\min\{d,N/d\}\le \sqrt{N}$ with equality iff $N$ is a perfect square and $d=\sqrt{N}$. The rest follows easily.
I next claim that for any $N\ge 8$ and $d(N)\ge 3$, $\sigma(N)\le Nd(N)/2$. Combined with $d(N)\le 2\sqrt{N}$, this yields \[ N = \sigma(d(N))\le \frac{d(N)d(d(N))}{2}\le \sqrt{N}2\sqrt{d(N)}\le 2\sqrt{2}N^{\frac34} \Rightarrow N\le 64.
Notice that the map $\phi(d):d\mapsto d+n/d$, on the interval $d\in[1,n]$, attains the maxima at $1+n$. Clearly $N$ is not a prime, so we can in fact observe
\[
\sigma(N) = \sum_{d\mid N}d \le \sum_{d\mid N, d\le \sqrt{N}}\left(d+\frac{N}{d}\right)\le (N+1) + \left(2+\frac{N}{2}\right)\frac{d(N)-2}{2}.
\]With simple algebra, the last display is at most $Nd(N)/2$ provided $N\ge 8$ and $d(N)\ge 3$.
Lastly, if $d(N)\ge 16$ then $d(N)\le 2\sqrt{N}$ yields $N\ge 64$. So, it suffices to inspect the cases $d(N)\in\{10,\dots,15\}$, which is easy and omitted.