# prove that $\frac{a_n}{n}\rightarrow 1$: strange contest problem

A friend of mine told me about a contest problem, which he had once seen but the provenance of which he could not remember:

An infinite sequence of positive integers $a_i$ has this property: for every prime $p$, the set $\{ a_1,a_2,...,a_p\}$ is a complete residue system modulo $p$. Now prove that $\frac{a_n}{n}$ converges to $1$.

1) Does anyone recognise this problem and know whence it comes?

2) I would like a solution. Though I have not solved it myself, I have made a curious observation. Denoting the primes by $p_i$, the sequence with these blocks $[p_n,p_n-1,...,p_{n-1}+1]$ is admissible. The statement in the problem then implies that $\frac{p_{n+1}}{p_n}$ tends to $1$. Rarely does a contest problem say anything about the distribution of the primes.

EDIT: My curiosity about this problem is growing day by day, but my progress is not. I would be thrilled about and grateful for a solution, whatever techniques are employed.

• It took me a minute to understand your block structure in 2), so it might be worth explaining that a bit better. (Just to make sure: your blocks are essentially [2, 1], [3], [5, 4], [7, 6], [11, 10, 9, 8], [13, 12], [17, 16, 15, 14], etc, correct?) – Steven Stadnicki Jun 4 '18 at 15:58
• Unless I am misunderstanding, your collection is just a simple reordering of $a_i=i$. How does that construction show that the ratio of successive primes goes to $1$? – lulu Jun 4 '18 at 15:58
• @lulu Because the $p_n$th term in his sequence is $p_{n-1}+1$, so it must be that $\lim_{n\to\infty}\frac{p_{n-1}+1}{p_n}=1$ since it's a subsequence of $a_n$. – Steven Stadnicki Jun 4 '18 at 15:59
• @StevenStadnicki Ah, thank you. I may have it wrong, but I believe that proving that limit requires the Prime Number Theorem (or at least something close to it). – lulu Jun 4 '18 at 16:02
• Just as a side note, using Rosser's theorem it is easy to show $\lim\limits_{n \to \infty } \frac{p_{n}}{p_{n+1}}=1$, for example this one – rtybase Jun 4 '18 at 17:50