Let $d(n)$ be the number of all positive divisors of a natural number $n \ge 2$. Determine all natural numbers $n \ge 3$ such that $d(n -1) + d(n) + d(n + 1) \le 8$. Proposed by Richard Henner
Problem
Source: 49th Austrian Mathematical Olympiad Regional Competition (Qualifying Round) 5th April 2018 p4
Tags: number of divisors, Divisors, number theory
25.05.2019 18:34
The only solutions in natural numbers $n \geq 3$ of the Diophantine equation $(1) \;\; d(n-1) + d(n) + d(n+1) \leq 8$ are $n=3,4,6$. Proof: If $\prod_{i=1}^k p_i^{r_i}$ is the prime factorization of $m \geq 2$, then $(2) \;\; d(m) = \prod_{i=1}^k (r_i + 1)$. According to (2) we have the following equivalences: $(3) \;\; d(m)=2$ iff $m$ is a prime. $(4) \;\; d(m)=3$ iff $m$ is a square of a prime. $(5) \;\: d(m)=4$ iff $m$ is a cube of a prime or $m$ is a product of two distinct primes. Let $S(n) = d(n-1) + d(n) + d(n+1)$. Then $S(n) \geq 6$ since $d(m) \geq 2$ for all $m \geq 2$. Let us consider the following three cases: Case 1: $S(n)=6$. Then $n-1,n,n+1$ are all primes according to (3), which obviously is impossible. Case 2: $S(n)=7$. Then according to (3)-(4) the set $\{n-1,n,n+1\}$ consists of two primes and a square of a prime. Two solutions of $S(n)=7$ are $n=3$ and $n=4$. Assume $n \geq 5$. Then $(n-1,,n,n+1)=(p,q^2,r)$, where $p,q,r$ are distinct primes, yielding $(6) \;\; p + r = 2q^2$. The fact that $ p$ and $r$ are prime twins with $4 < p < r$ means $6 | p+1$ and $6 | r-1$. Hence $6 | p+r$ , implying $3 | 2q^2$ by (6), i.e. $3|q$, which give us $q=3$. Hence $p+ r = 18$, which combined with $r - p = 2$ yields $(p,r) = (8,10)$. Consequently the only solutions of $S (n)=7$ are $n=3$ and $n=4$. Case 3: $S(n)=8$. Then according to (3)-(5) the set $\{n-1,n,n+1\}$ either consists of one prime and the square of two primes, or two primes and a cube of a prime or the product of two distinct primes. The first possibility implies $p^2,q^2 \in \{n-1,n,n+1\}$, where $p < q$ are two primes, yielding $2 \geq q^2 - p^2 \geq (p + 2)^2 - p^2 = 2p + 4$, i.e. $p \leq -1$. This contradiction implies $(7) \;\; (n-1,n,n+1) = (p,q^3,r)$ or $(8) \;\; (n-1,n,n+1) = (p,st,r)$, where $p,q,r,s,t$ with $s<t$ are distinct primes. Assume (7) is true. Then $p+r=2q^3$, yielding $3 | 2q^3$ (since $6 | p+r$). Hence $q=3$ and $p+r = 54$, which combined with $r-p = 2$ result in $(p,r) = (26,28)$. Thus there are no solution of $S(n)=8$. Finally assume (8) is true. The fact that $n=p+1=st$ is even (since $p$ is an odd prime) and $p+r=2st$ implies $2|st$ and $3|st$ (since $6 | p+r$). Therefore $(s,t)=(2,3)$, which means $(p,r)=(5,7)$. In other words, we have one solution of $S(n)=8$, namely $n=6$. Summa summarum, the only solutions $n \geq 3$ of the Diophantine equation (1) are $n=3,4,6$. q.e.d.
03.08.2020 18:21
It's easy to check that among numbers $3,...,6$ $n=3,4,6$ are solutions. Suppose $n \ge 7$ $d(m) \ge 2$ holds for all natural numbers $m \ge 2$. An even number $2k \ge 3$ has at least 4 divisors $(1,2,k, 2k)$. If $n$ is odd, then both $n-1$ and $n+1$ are even, hence they have at least 4 divisors. So $d(n) \le 0$, a contradiction. Then $n$ is even, $d(n) \ge 4$, so $d(n-1) = 2$, $d(n+1)=2$, so $d(n)=4$. Then $n-1$, $n+1$ are primes. Among three consecutive numbers one is divisible by 3, so is $n$. But then $n$ has at least 5 divisors (1, 2, 3, 6, n), a contradiction. So there's no solutions for $n \ge 7$. Answer: $n=3,4,6$.
13.11.2021 18:32
We note that $n=2$ doesn't work so henceforth assume $n>2$. This implies that there is at least one prime in $\{n-1,n,n+1\}$. We claim that there are exactly two primes in $\{n-1,n,n+1\}$. Proof: We obviously can't have three primes. Suppose there is only one prime. Then the other two must be perfect squares, which is a contradiction. $n=3,4,6$ are solutions, but $n=5$ isn't, so we assume $n>6$. So $n-1$ and $n+1$ are both primes and $n$ has $1,2,3,4$ divisors. But this is not possible as $n>6$ and $6|n$. So the answer is $\boxed{n=3,4,6}$.