Let $d(k)$ be the number of positive divisors of integer $k$. A number $n$ is called balanced if $d(n-1) \leq d(n) \leq d(n+1)$ or $d(n-1) \geq d(n) \geq d(n+1)$. Show that there are infinitely many balanced numbers.
Problem
Source:
Tags: number theory proposed, number theory
xxp2000
23.08.2014 16:13
Leicich wrote: Let $d(k)$ be the number of positive divisors of integer $k$. A number $n$ is called balanced if $d(n-1) \leq d(n) \leq d(n+1)$ or $d(n-1) \geq d(n) \geq d(n+1)$. Show that there are infinitely many balanced numbers. Suppose there is no such number for $n>N$. Let $p_0>N$ be a prime, $d(p_0)<d(p_0+1)$. So we have $d(2k-1)\le d(2k)$ and $d(2k)\ge d(2k+1)$ for all $2k-1\ge p_0$. We can pick a prime of form $p_1=9m+4>p_0$. Now $d(2p_1)<d(2p_1+1)$. Absurd!
parmenides51
16.09.2021 10:39
solved from here
hyperbolictangent wrote:
Solution 5. Suppose, for the sake of contradiction, there were finitely many such $n$. Then for all $n \ge 2N$ for some large $N$, either $d(n) < d(n - 1), d(n + 1)$ or $d(n) > d(n - 1), d(n + 1)$ (we'll call these conditions 1 and 2, respectively).
Case 1: $d(2N) < d(2N + 1)$. Then condition 2 holds for $n = 2N + 1$, so $d(2N + 2) < d(2N + 1)$. It follows that condition 1 holds for $n = 2N + 2$, so $d(2N + 2) < d(2N + 3)$. Inductively, $d(2M + 1) > d(2M), d(2M + 2)$ for all $M \ge N$. Setting $M = (p - 1)/2$ for some sufficiently large prime $p$ gives a contradiction.
Case 2: $d(2N) > d(2N + 1)$. An identical argument to the one above gives $d(2M + 2) > d(2M + 1), d(2M + 3)$ for all $M \ge N$. By Dirichlet's Theorem, there are arbitrarily large primes $p$ congruent to $8$ modulo $15$. Set $M = p - 1$ for some such prime $p$; then $d(2M + 2) = d(2p) = 4$ yet $2M + 1 \equiv 2(7) + 1 \equiv 0 \pmod{15}$ so that $15 | d(2M + 1)$ forcing $d(2M + 1) \ge 4$, contradiction.
It follows that infinitely many such $n$ exist.