For a positive integer $n$, denote by $g(n)$ the number of strictly ascending triples chosen from the set $\{1, 2, ..., n\}$. Find the least positive integer $n$ such that the following holds: The number $g(n)$ can be written as the product of three different prime numbers which are (not necessarily consecutive) members in an arithmetic progression with common difference $336$.
Problem
Source: Nordic Mathematical Contest 2020 p1
Tags: number theory, min, Arithmetic Progression, primes
25.04.2020 14:34
The number $g(n)$ of strictly ascending triples in the set $\{1,2,3, \ldots , n\}$ is ${n} \choose {3}$, i.e. ${\textstyle (1) \;\; g(n) = {{n} \choose {3}} = \frac{n(n - 1)(n - 2)}{6}}$. According to the given information there exists three primes $p_1 < p_2 < p_3$ s.t. $(2) \;\; 336 \mid p_i – p_j, 1 \leq i < j \leq 3$ and $g(n) = p_1p_2p_3$, i.e. $(3) \;\; n(n - 1)(n - 2) = 6p_1p_2p_3$. We have $p_1 > 3$ by condition (2), implying $n>5$ by equation (3). We also have $4 \nmid n(n - 1)(n - 2)$ by equation (3), which means $n$ is odd, i.e. $n – 1$ is even. Consequently $n(n - 1)(n - 2)$ is a product of five distinct primes, which combined with equation (3) and the fact that $n>5$ and $n$ is even implies $(4) \;\; (n,n-1,n-2) = (3p_1,2p_2,p_3)$ or $(5) \;\; (n,n-1,n-2) = (p_3,2p_2,3p_1)$. Equations (4) and (5) give us $(6) \;\; (p_1,p_2,p_3,n) = (1+2s,1+3s,1+6s,3+6s)$ and $(7) \;\; (p_1,p_2,p_3,n) = (1+2t,2+3t,5+6t,5+6t)$ respectively. By condition (2) we obtain $336 | s$ and $336 | t+1$. Thus $s_{\min}=336$ and $t_{\min}=335$. Observe that $t=335$ implies $5|n$ by the formulas (7). If $s=336$, then $(p_1,p_2,p_,n) = (673,1009,2017,2019)$ by the formulas (6). The fact that $673$, $1009$ and $2017$ are primes and $p_2-p_1=336$ and $p_3-p_2=3 \cdot 336$ give us the following conclusion: The least positive integer $n$ satisfying the equation (3) is $n=2019$.