Mathematical Reflections 2016, Issue 4 - Problem U381

Problem:
Find all positive integers $n$ such that
$$\sigma(n)+d(n)=n+100.$$

(We denoted by $\sigma(n)$ the sum of the divisors of $n$ and by $d(n)$ the number of divisors of $n$).

Proposed by Alessandro Ventullo, Milan, Italy

Solution:
Since $\sigma(n) \geq n+1$, then the sum of the proper divisors of $n$ is $99-d(n) \leq 97$. Denoting by $\omega(n)$ the number of distinct primes dividing $n$, observe that if $\omega(n) \geq 4$, then there exist four prime numbers $p<q<r<s$ that divide $n$. Since $p \geq 2$, $q \geq 3$, $r \geq 5$ and $s \geq 7$, then $qrs$ divides $n$ but $qrs \geq 3\cdot5\cdot7>97$, which contradicts the hypothesis. So, $\omega(n) \leq 3$. We have three cases.

(i) $\omega(n)=1$. Then, $n=p^k$, where $p$ is a prime number and $k \in \mathbb{N}^*$. If $k=1$, then $(1+p)+2=p+100$, contradiction. If $k \geq 2$, then $$1+p+\ldots+p^k+(k+1)=p^k+100,$$ i.e.
$$p(1+p+\ldots+p^{k-2})+k=98. \qquad (1)$$
If $k \geq 7$, then $$p(1+p+\ldots+p^{k-2}) \geq 2(1+2+\dots+2^5)=2\cdot63>97.$$ It follows that $k \in \{2,3,4,5,6\}$. An easy check in (1) shows that there are no solutions.

(ii) $\omega(n)=2$. Then, $n=p^{k_1}q^{k_2}$, where $p,q$ are prime numbers, $p<q$ and $k_1,k_2 \in \mathbb{N}^*$. Since $p \geq 2$ and $q \geq 3$, if $n=p^5q$, then $p^5+p^4q+p^3q \geq 32+16\cdot3+8\cdot3>97$, so $k_1 \leq 4$. If $n=pq^4$, then $q^4+q^3 \geq 81+27>97$, so $k_2 \leq 3$.  We have twelve cases.

(a) $k_1=1,k_2=1$. Then, $n=pq$ and $d(n)=4$. It follows that $p+q=95$. By parity, it must be $p=2$, but $q=93$ is not a prime. So, no solutions in this case.

(b) $k_1=2,k_2=1$. Then, $n=p^2q$ and $d(n)=6$. It follows that $p+p^2+q+pq=93$. By parity, it must be $p=2$ and we get $q=29$. So, $n=116$.

(c) $k_1=3, k_2=1$. Then, $n=p^3q$ and $d(n)=8$. It follows that $p+p^2+p^3+q+pq+p^2q=91$. By parity, it must be $p=2$ and we get $q=11$. So, $n=88$.

(d) $k_1=4, k_2=1$. Then, $n=p^4q$ and $d(n)=10$. It follows that $p+p^2+p^3+p^4+q+pq+p^2q+p^3q=89$. By parity, it must be $p=2$ and we get $q=59/11$, i.e. no solution.

(e) $k_1=1, k_2=2$. Then, $n=pq^2$ and $d(n)=6$. It follows that $p+pq+q+q^2=93$. By parity, it must be $p=2$ and we get $q(3+q)=91$, i.e. no solution.

(f) $k_1=2,k_2=2$. Then, $n=p^2q^2$ and $d(n)=9$. It follows that $p+p^2+pq+p^2q+pq^2+q+q^2=90$. By parity, it must be $p=2$ and we get $q(7+3q)=84$, i.e. no solution.

(g) $k_1=3, k_2=2$. Then, $n=p^3q^2$ and $d(n)=12$. But $$p^3q+p^2q^2+pq^2+p^2q \geq 8\cdot3+4\cdot9+2\cdot9+4\cdot3>99-d(n)=87,$$ so there are no solutions.

(h) $k_1=4, k_2=2$. Then, $n=p^4q^2$ and $d(n)=15$. But $$p^4+p^3q^2 \geq 16+8\cdot9>99-d(n)=84,$$ so there are no solutions.

(i) $k_1=1, k_2=3$. Then, $n=pq^3$ and $d(n)=8$. It follows that $p+pq+pq^2+q+q^2+q^3=91$. By parity, it must be $p=2$ and we get $q(3+3q+q^2)=89$, i.e. no solution.

(j) $k_1=2,k_2=3$. Then, $n=p^2q^3$ and $d(n)=12$. But $$q^3+pq^3+pq^2 \geq 27+2\cdot27+2\cdot9>99-d(n)=87,$$ so there are no solutions.

(k) $k_1=3, k_2=3$. Then, $n=p^3q^3$ and $d(n)=16$. But $$p^2q^3 \geq 4\cdot27>99-d(n)=83,$$ so there are no solutions.

(l) $k_1=4, k_2=3$. Then, $n=p^4q^3$ and $d(n)=20$. But $$p^2q^3 \geq 4\cdot27>99-d(n)=79,$$ so there are no solutions.

(iii) $\omega(n)=3$. Then, $n=p^{k_1}q^{k_2}r^{k_3}$, where $p,q,r$ are prime numbers, $p<q<r$ and $k_1,k_2,k_3 \in \mathbb{N}^*$. Since $p \geq 2$, $q \geq 3$ and $r \geq 5$, if $n=p^3qr$, then $p^3q+p^3r+p^2qr \geq 8\cdot3+8\cdot5+4\cdot3\cdot5>97$, so $k_1 \leq 2$. If $n=pq^2r$, then $pq^2+q^2r+pqr+r \geq 2\cdot9+9\cdot5+2\cdot3\cdot5>97$, so $k_2=1$. If $n=pqr^2$, then $qr^2+pr^2 \geq 3\cdot 25+2\cdot25>97$, so $k_3=1$.  We have two cases.

(a) $k_1=k_2=k_3=1$. Then, $n=pqr$ and $d(n)=8$. It follows that $p+q+r+pq+pr+qr=91$. By parity, it must be $p=2$, which gives $3q+3r+qr=89$, i.e. $(q+3)(r+3)=98$. There are no solutions in this case.

(b) $k_2=2, k_2=k_3=1$. Then, $n=p^2qr$ and $d(n)=12$. It follows that $p+p^2+q+pq+p^2q+r+pr+p^2r+qr+pqr=87$. By parity, it must be $p=2$, which gives $7q+7r+3qr=81$. If $q \geq 5$, then $r \geq 7$ and $7q+7r+3qr>81$. So, $q=3$ and $4r=15$, i.e. no solution.

In conclusion, $n \in \{88,116\}$.