Problem #418: Are there infinitely many positive integers not of the form...

---

Progress

Asked by Erdős and Sierpiński. Numbers not of the form we call non-cototients. It follows from the Goldbach conjecture that every odd number can be written as $n-\phi(n)$. What happens for even numbers?

Browkin and Schinzel [BrSc95] provided an affirmative answer to this question, proving that any integer of the shape $2^{k}\cdot 509203$ for $k\geq 1$ is a non-cototient. It is open whether the set of non-cototients has positive density.

Erdős [Er73b] has shown that a positive density set of natural numbers cannot be written as $\sigma(n)-n$ (numbers not of this form are called nonaliquot, or sometimes untouchable). Banks and Luca [BaLu05] have proved that the set of nonaliquots has lower density $\geq 1/48$. This bound was improved to $0.06$ by Chen and Zhao [ChZh11]. Pollack and Pomerance [PoPo16] give a heuristic that predicts the density exactly (with a value of $\approx 0.17$).

This is discussed in problem B36 of Guy's collection [Gu04].