[Math] A prime number pattern

number theoryprime numbers

The algorithm
Given a natural number $n$ define a procedure as follows:

  • Generate a list of primes upto and possibly including, $n$
  • Assign $Z = n$
  • If $Z > 0$, subtract the largest prime from list which we haven't considered yet. Otherwise, add it to $Z$. If $n$ is prime, it is assumed accounted for by the first step.
  • Repeat until all primes have been considered.

For example, take $25$. The list of primes would be $2, 3, 5, 7, 11, 13, 17, 19, 23$. Subtracting $23$ from $Z=25$, we get $Z=2$. Next, we get $Z=2-19= -17$. And so on. Consequently, $Z$ assumes the values $25, 2, -17, 0, 13, 2, -5, 0, 3, 1$.

Note: Only an example. The conjecture as stated deals with applying the algorithms on primes. However, other numbers also seem to exhibit interesting patterns.

The Pattern

  • Beginning at $3$ and every other prime thereafter, following the algorithm always (seems to) land us at $1$.
  • For the rest of the primes, $Z$ has a final value of either $0$ or $2$.

The problem

Please read @alex.jordan's answer as he cleverly limits the range of values $Z$ can reach (say, terminal Z, or $Z_t$) to $\{-1,0,1,2\}$. As a result, the problem is now reduced to:

  • For any prime number, prove that $-1$ cannot be a terminal.

Also being discussed: here

Best Answer

Here is an outline:

  • No matter what $N$ you start with, it is impossible to end with $3$ or higher. The penultimate $N$-value would have either been $N=1$ (impossible, since your next step would need to have been subtracting 2) or $N=5$. Since $N$ was $5$ at some point, the prime $3$ was in the original set of primes, and this necessitates an even earlier step in the chain. The step before that would have either been with $N=2$ (again impossible, since you would have subtracted 3) or with $N=8$. And again, we have a number so large that there had to have been another prime in the original list ($5$); there had to be an earlier step; and there had to have been a point when $N$ was much larger ($13$). Since the value of $N$ is getting larger at a more than quadratic rate (summing primes grows almost like like $n^2\log(n)$) while prime values are getting larger much less quickly, this process will never have a chance to end.
  • No matter what $N$ you start with, it is impossible to end with $-2$ or lower. A similar, but negative, argument applies. If we end with $-2$, then the penultimate value was either $N=0$ (not possible, since our last step would then have been adding $2$) or $N=-5$. Since $N$ is negative at this step, there must have been a previous step, where either $N=-2$ (again not possible) or $N=-8$. And this continues; we never return to an initial $N$-value that is positive, since $N$ is growing negative so quickly relative to the next largest prime.
  • Since you are subtracting and adding primes (which are mostly odd) and you are starting with $N$ prime (and odd), the parity of the terminal number only depends on how many steps there are in your sequence - how many primes there are up to $N$. For example, since $N=11$ yields a prime collection $\{2,3,5,7,11\}$ with 5 elements, you will add/subtract 4 odd numbers, and end up with an odd terminal $N$-value. But with $N=13$, you will add/subtract 5 odd numbers, and end up with an even terminal $N$-value.

This explains why the terminal values of $N$ would have to alternate between something in $\{-1,1\}$ and something in $\{0,2\}$ as $N$ increments through prime values.

Your conjecture would be proved if we could rule out $-1$ as a terminal value when $N$ is prime. I've tried assuming that $-1$ is a terminal value, hoping that this led to only finitely many possible initial $N$, none of which are prime. However it appears that many $N$ lead to $-1$. The smallest are: $4, 10, 16, 22$. Perhaps it can be show that if $-1$ is terminal for $N$, then $N$ was even. But maybe someone else can take it from here.

Hope this much helps!

EDIT added MUCH later

We can indeed show that if the terminal value is $-1$, then $N$ must have been even.

Working again from the end of the process backward, let's denote $p_i$ to be the $i$th prime in the list, and $Z_i$ the $i$th value for $Z$. Again, these indices are from the end of the process. So we take $Z_0=-1$ and $p_0=2$.

$p_1$ is $3$. And $Z_1$ must have either been $-1+p_0$ or $-1-p_0$; that is, either $1$ or $-3$. Note that the only possibilities for $Z_1$ are odd numbers.

Next, $p_2$ is 5, and $Z_2$ must be one of the preceding possibilities for $Z_1$ plus or minus $3$. So $Z_2$ must be even.

Since all further primes are odd, if we continue in this way we see that for $n>0$, whatever $Z_n$ is, it's odd if $n$ is odd and even if $n$ is even.

Now only for some of the potential $Z_n$ that we can reverse engineer this way, is it possible for them to have been initial $N$ values. Still, we know now that if we start with an $N$ that has $-1$ as its terminal $Z$-value, and if it takes an even number of steps to get there, then $N$ must have been even, and therefore not prime.

All told, this process has terminating $Z$-values that alternate between $1$ and either $0$ or $2$ as $N$ increments through prime values.

Related Question