20
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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?) $\endgroup$ – Steven Stadnicki Jun 4 '18 at 15:58
  • $\begingroup$ 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$? $\endgroup$ – lulu Jun 4 '18 at 15:58
  • 5
    $\begingroup$ @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$. $\endgroup$ – Steven Stadnicki Jun 4 '18 at 15:59
  • $\begingroup$ @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). $\endgroup$ – lulu Jun 4 '18 at 16:02
  • 1
    $\begingroup$ 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 $\endgroup$ – rtybase Jun 4 '18 at 17:50
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.