15
$\begingroup$

This is a question that has bothered me for almost 6 years now on and off, and I still don't really know enough to tackle it.

To phrase it somewhat formally:

Let $P$ be the series of prime numbers such that $P(i)$ is the i-th prime number.

Let $N$ be a positive integer with a value greater than $2$.

Let $X$ be the series of numbers such that $X(0) = 0$ and $X(i) = (X(i - 1) + P(i)) \pmod N$

Does there exist an $N$ for which the set of elements $X(0),\ldots,X(N-1)$ contain every number from $0$ to $N-1$ exactly once? Can we prove it one way or another?

I've made computer simulations and let them run overnight and the results seem to suggest that no, there is no such N, but the graphs I got out of doing this are fairly interestingly shaped.

For instance, this is a scatter plot where the $x$-axis is $N$ and the $y$-axis is the percent of numbers in $X(0), \ldots, X(N-1)$ that were reached before a duplicate. Proportions

And if we zoom in we can see some definite "structure" to the proportions, which is also interesting. Zoomed in

And on the long tail there seems to be a definite "range", with some outliers

Long tail I don't know how to explain why the graph is shaped like it is, or what the structure in it means, or why it seems like a "thick" logarithmic curve. The shape would seem to imply.

Also interestingly, the minimum proportion seems to approach ~0.0001592, which I have no clue the significance of.

$\endgroup$
13
  • $\begingroup$ Presumably the two curves correspond to some simple property of $N$ (for example, whether $N$ is even or odd)—you could look at the two sets of moduli to see. $\endgroup$ Apr 28, 2020 at 7:09
  • $\begingroup$ No such luck I'm afraid. The top and bottom line have even and odd numbers. $\endgroup$ Apr 28, 2020 at 7:15
  • $\begingroup$ I'm getting a very different-looking graph from yours. Can you give an example of the calculation of the $X$ series when $p=29$, say, and the corresponding point on the graph? $\endgroup$ Apr 28, 2020 at 7:24
  • 2
    $\begingroup$ Your program is only testing each individual prime mod $N$ (main.rs, line 23), not accumulating the $X_i$ series as you describe, so I don't think your program is answering the question as stated. Bottom line is even $N$s and odd $N$s that are $2$ less than a prime; top line is other odd $N$s. This is easily explained, but it isn't the question asked, so I'll not explain here. Your question is still interesting. $\endgroup$
    – nickgard
    Apr 28, 2020 at 19:07
  • 1
    $\begingroup$ Let $s_n$ be sum of first $n$ primes. Notice that if we can prove that for all $N\ge 10^4$, $$\text{ There exist } j\lt k\lt N, \text{ such that } s_k\equiv s_j\pmod{N}$$ Then there are no solutions to your question. This holds for all prime numbers $N$ because $$s_i=s_{i-1}+p_i\equiv s_{i-1}\pmod{p_i}$$ So we have $i-1\lt i \lt p_i$ for any $i$th prime number $p_i=N$. I'm not sure how to prove this for arbitrary composite numbers though. $\endgroup$
    – Vepir
    May 1, 2020 at 16:16

0

You must log in to answer this question.