Let $s(n)$ denote the smallest prime divisor and $d(n)$ denote the number of positive divisors of a positive integer $n>1$. Is it possible to choose $2023$ positive integers $a_{1},a_{2},...,a_{2023}$ with $a_{1}<a_{2}-1<...<a_{2023}-2022$ such that for all $k=1,...,2022$ we have $d(a_{k+1}-a_{k}-1)>2023^{k}$ and $s(a_{k+1}-a_{k}) > 2023^{k}$? Proposed by Nikola Velov
Problem
Source: 2023 Macedonian Team Selection Test P1
Tags: number theory
VicKmath7
21.05.2023 18:53
Take sufficiently large constant $M$; choose $a_1$ arbitrarily and select $a_2, a_3, \ldots, a_{2023}$ so that $a_{k+1}-a_k=M!+1$ for all integers $k \in [1;2022]$. Observe that $s(a_{k+1}-a_k)=s(M!+1)>M$ and that $\tau (a_{k+1}-a_k-1)=\tau (M!)>M$, so we are done.
Comment: Alternatively, this problem can be done by induction (but it is essentially the same as the factorial construction): select $a_1$ arbitrarily and to construct $a_{k+1}$, take large constant $N$ and all primes $p_1, p_2, \ldots, p_{m_k}$ in the interval $[1; 2023^k]$; let $a_{k+1} \equiv a_k+1 \pmod {p_i^N}$ for all $i=1, 2, \ldots, m_k$. Then $s(a_{k+1}-a_k)>2023^k$ and $\tau (a_{k+1}-a_k-1)>(N+1)^{m_k}>2023^k$.
starchan
21.05.2023 18:57
Solved with L567, mueller.25
Yes, it is possible. Inductively construct such a sequence by selecting $a_1 = 1$ and for each $k > 1$ we choose $a_k-a_{k-1}$ to be $1$ plus the product of all the first $2023^{2023^{2023^k}}$ primes.
Orestis_Lignos
23.05.2023 00:28
The answer is yes. Let $a_{i+1}-a_i-1=b_i$ for all $i=1,\ldots,2022$. Then, $b_i>0$ for all $i$, and we need $d(b_i)>4^i$ and $s(b_i+1)>4^i$ for all $i=1,2,\ldots,2022$. Now, just take all $b_i$ to be equal to $N!$, where $N>2 \cdot 2023^{2022}$. Then, $d(b_i)>v_2(b_i)=v_2(N!)>\dfrac{N}{2}>2023^{2022}$ and $s(b_i+1)>2023^{2022},$ as all primes $p<2023^{2022}$ divide $b_i=N!$. Thus, this selection of the $b_i$ works