A conjecture of Erdős, Granville, Pomerance, and Spiro [EGPS90]. It is possible for $s(A)$ to have positive density even if $A$ has zero density (for example taking $A$ to be the product of two distinct primes). Erdős [Er73b] proved that there are sets $A$ of positive density such that $s^{-1}(A)$ is empty.

Pollack [Po14b] has shown that this is true if $A$ is the set of primes. Troupe [Tr15] has shown that this is true if $A$ is the set of integers with unusually many prime factors. Troupe [Tr20] has also shown this is true if $A$ is the set of integers which are the sum of two squares.

Pollack, Pomerance, and Thompson [PPT18] prove that if $\epsilon(x)=o(1)$ and $A\subset \mathbb{N}$ has size at most $x^{1/2+\epsilon(x)}$ then\[\#\{ n\leq x: s(n)\in A\} =o(x)\]as $x\to \infty$. It follows that (using $s(n)\ll n\log\log n$) if $A$ grows like $\lvert A\cap [1,x]\rvert\leq x^{1/2+o(1)}$ then $s^{-1}(A)$ has density $0$.

Alanen calls $k$ such that $s(n)=k$ has no solutions untouchable. These are discussed in problem B10 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

2 comments on this problem