Problem 647 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
Let $\tau(n)$ count the number of divisors of $n$. Is there some $n>24$ such that\[\max_{m<n}(m+\tau(m))\leq n+2?\]

Picture
-------
Divisors / subset-sum picture:

divisors(n):  1, d1, d2, ..., n
choose some of them and add them up

σ(n) = sum of *all* divisors

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: multiplicative number theory.

Benchmarks / known results (from comments)
----------------------------------------
- The $n+2$ is best possible here since\[\max(\tau(n-1)+n-1,\tau(n-2)+n-2)\geq
  n+2.\]In 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 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 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].