A problem of Erd\H{o}s and Selfridge. This is true for $n=24$. The $n+2$ is best possible here since\[\max(\tau(n-1)+n-1,\tau(n-2)+n-2)\geq n+2.\]In \cite{Er79} Erd\H{o}s says 'it is extremely doubtful' that there are infinitely many such $n$, and in fact suggets that\[\lim_{n\to \infty}\max_{m<n}(\tau(m)+m-n)=\infty.\]In \cite{Er79d} Erd\H{o}s says it 'seems certain' that for every $k$ there are infinitely many $n$ for which\[\max_{n-k<m<n}(m+\tau(m))\leq n+2,\]but 'this is hopeless with our present methods', although it follows from Schinzel's Hypothesis H.

In \cite{Er92e} Erd\H{o}s offered £25 for an example of such an $n>24$. He wrote 'I am being rather stingy but we old people are stingy.' (This has been converted to \$44 using approximate 1992 exchange rates.)

Tao has observed in the comments that, since $\tau(m)$ is similar to $2^{\omega(m)}$, this problem is similar to (but slightly weaker than) the first part of [679], but much stronger than [413] or [248].

See also [413].


References


[Er79] Erd\H{o}s, Paul, Some unconventional problems in number theory. Math. Mag. (1979), 67-70.

[Er79d] Erd\H{o}s, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. (1979), 71-80.

[Er92e] Erd\H{o}s, P\'{a}l, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48.