(Richard Henner). For a natural number $n \geq 2$, let $d(n)$ be the number of positive divisors of $n$.

Determine all natural numbers $n \geq 3$ for which

$$
d(n-1)+d(n)+d(n+1) \leq 8
$$

holds.
(Richard Henner, Birgit Vera Schmidt). First, we establish some basic considerations about the number of divisors:

- For all $k \geq 2$, $d(k) \geq 2$.
- $d(k)=2$ holds exactly when $k$ is a prime number.
- $d(k)=3$ holds exactly when $k$ is the square of a prime number.
- $d(k)=4$ holds exactly when $k$ is either the third power of a prime number or the product of two distinct prime numbers.
- Because $d(n-1)+d(n)+d(n+1) \leq 8$, $d(k)>4$ cannot occur.

We will try some small cases, see Table 1.

| $n$ | $d(n-1)$ | $d(n)$ | $d(n+1)$ | Sum | Solution |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 3 | 2 | 2 | 3 | 7 | yes |
| 4 | 2 | 3 | 2 | 7 | yes |
| 5 | 3 | 2 | 4 | 9 | no |
| 6 | 2 | 4 | 2 | 8 | yes |
| 7 | 4 | 2 | 4 | 10 | no |
| 8 | 2 | 4 | 3 | 9 | no |
| 9 | 4 | 3 | 4 | 11 | no |

Table 1: Problem 4, Solution 1

Lemma. For $n>9$, $d(n-1)+d(n)+d(n+1)>8$ and is therefore too large.

Proof. Let $n>9$ from now on. Clearly, $d(n-1)+d(n)+d(n+1) \geq 6$. Thus, we only need to exclude the cases where the sum is 6, 7, or 8.

- The case $d(n-1)+d(n)+d(n+1)=6$ cannot occur because three consecutive numbers cannot all be prime.
- The case $d(n-1)+d(n)+d(n+1)=7$ can only occur if two of the three numbers are prime and the third is the square of a prime. This holds for $n=3$ and $n=4$ (see Table 1).

For $n>9$, there are no more consecutive prime numbers, so $n-1$ and $n+1$ would have to be the two primes, and thus $n$ must be even. An even number greater than 9 cannot be the square of a prime.

- The sum $d(n-1)+d(n)+d(n+1)=8$ can be achieved either as $2+2+4$ or as $2+3+3$ (or any permutation of the order). We consider these separately.
- If two of the summands are 2 and one is 4, this means that two of the three numbers must be prime and the third must be either the product of two different primes or the third power of a prime. As before, $n-1$ and $n+1$ must be the two primes, and thus $n$ must be even. Since the primes $n-1$ and $n+1$ are not divisible by 3, but among three consecutive numbers, there must be one divisible by 3, $n$ must be even and divisible by 3. Therefore, only $n=6$ is possible, which, as mentioned above, is a solution.
- If one of the summands is 2 and the other two are 3, one of the three consecutive numbers must be even. On the other hand, all three numbers must be either prime or the square of a prime. Therefore, 2 or $2^{2}$ must appear among the three numbers, which is of course not possible for $n>9$.

Thus, the claim is proven, and $n=3$, $n=4$, and $n=6$ are the only solutions.