Suppose that $d(n)$ is the number of positive divisors of natural number $n$. Prove that there is a natural number $n$ such that $$ \forall i\in \mathbb{N} , i \le 1402: \frac{d(n)}{d(n \pm i)} >1401 $$ Proposed by Navid Safaei and Mohammadamin Sharifi
Problem
Source: Iran TST 2023 ; Exam 2 Problem 1
Tags: number theory, number of divisors, divis
a_507_bc
16.03.2023 20:57
This means that the inequality should be true for one appropriate choice of the sign, or for both $ n \pm i$?
Tintarn
16.03.2023 21:27
For both (at least this is the stronger version and also true as my solution shows).
Let $p_1<p_2<\dots<p_m$ be the primes less than $1402$ and $p_{m+1}<p_{m+2}<\dots$ the sequence of other primes.
Consider $n=AB$ where $A=(p_1p_2\dots p_m)^{1402}$ and $b=p_{m+1}\dots p_k$.
We claim that this does the trick for $k$ sufficiently large.
So take any $i \le 1402$ and any sign, so that we need to prove that $\tau(n)>1401\tau(n \pm i)$.
First of all, note that $\tau(n) \ge 2^k$.
Since $\tau(N) \le 2^{\Omega(N)}$ for general $N$, where $\Omega(N)$ is the number of prime factors with repetition (suffices to check for prime powers where it follows from $2^k \ge k+1$), it suffices to prove that $\Omega(n \pm i) \le k-12$.
Note that each of the primes $p_1,\dots,p_m$ divides $n \pm i$ at most once by construction, and none of $p_{m+1},\dots,p_k$ divide $n \pm i$.
Write $n \pm i=ab$ where $b$ is the part coprime to $p_1,\dots,p_k$. Hence $b \le n+i \le 2n \le Ap_1p_2\dots p_k$ and it suffices to prove that $\Omega(b) \le k-2023$.
But this is rather easy: Otherwise, we would have $b \ge p_k^{k-2023}$ and hence
\[p_k^{k-2023} \le Ap_1\dots p_k \le Ap_1\dots p_{2024} p_k^{k-2024}\]which is equivalent to $p_k \le Ap_1\dots p_{2024}$ and hence clearly fails for large $k$. Done!
M11100111001Y1R
27.06.2023 00:41
It seems like another NT construction problem by Mr. Safaei had proposed, I'll try to solve it tomorrow.
M11100111001Y1R
28.06.2023 02:00
Alright here is a solution that is similar to $Post \ 3.$ Let $p_i$ the $i-th$ prime number and take $n=(p_1.p_2\cdots p_m)^{1402}$ so we are done. I'll try to find another solution but as I promised yesterday I should solve it today and here was my solution.