, 2014

Solution:

Answer: $\quad 29$

If $n$ is even, $n+1 \mid n^{n+1}+1$, so we can cover all odd $m$.

If $m$ is even and $m \mid n^{n+1}+1$, then $n$ must be odd, so $n+1$ is even, and $m$ cannot be divisible by $4$ or any prime congruent to $3 \pmod{4}$. Conversely, if $m / 2$ has all factors $1 \pmod{4}$, then by CRT there exists $N \equiv 1 \pmod{4}$ such that $m \mid N^{2}+1 \mid N^{N+1}+1$ (note $(N+1)/2$ is odd).

So the only bad numbers take the form $2k$, where $1 \leq k \leq 24$ is divisible by at least one of $2,3,7,11,19,23,31, \ldots$ We count $k=2,4, \ldots, 24$ (there are $12$ numbers here), $k=3,9,15,21$ (another four), $k=7,11,19,23$ (another four), giving a final answer of $49-12-4-4=29$.