Numbers of the form $k+f(k)$

Abstract

For a function $f:\mathbb{N}\to \mathbb{N}$, let $$ N^+_f(x)=\{n\leq x: n=k+f(k) \mbox{ for some } k\}. $$ Let $\tau (n)={\sum }_{d|n}1$ be the divisor function, $\omega (n)={\sum }_{p|n}1$ be the prime divisor function, and $\phi (n)=\#\{1\le k\le n:\gcd (k,n)=1\}$ be Euler's totient function. We show that \begin{align*} &(1) \quad x \ll N^+_ω(x), \\ &(2) \quad x\ll N^+_τ(x) \leq 0.94x, \\ &(3) \quad x \ll N^+_φ(x) \leq 0.93x. \end{align*}