20

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.

Chris Sanders
  • 7,137
  • 10
  • 23
  • 2
    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 04 '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 04 '18 at 15:58
  • 5
    @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 04 '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 04 '18 at 16:02
  • Also, I should note that $\lim_{n\to\infty}\frac{p_{n+1}}{p_n}=1$ isn't actually that strong a result; it would hold if you had e.g. $p_n\approx n^2$, and IIRC it's pretty straightforward to show a quadratic bound on the $n$th prime. (Though note that that's not quite enough to show the limit in and of itself, because it's possible the limit could not exist at all; it's more just that the limit doesn't say much about the asymptotic growth of the primes that isn't pretty straightforward.) – Steven Stadnicki Jun 04 '18 at 16:04
  • @StevenStadnicki it is still more powerful than, say, Bertrand's postulate, although asymptotically. – Arnaud Mortier Jun 04 '18 at 16:12
  • 1
    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 04 '18 at 17:50

1 Answers1

3

This is problem 4 from the 2015 Miklós Schweitzer contest. There is an AoPS thread discussing this problem, see here. A couple of solutions is given there.

Wojowu
  • 26,600