29
$\begingroup$

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

  • 0
    but does $-17-17=0?$2012-07-29
  • 0
    @dato OP says that if the current value is negative, you are to add, not subtract2012-07-29
  • 2
    This has the feel of the [Collatz Conjecture](http://en.wikipedia.org/wiki/Collatz_conjecture) although there are significant differences.2012-07-29
  • 3
    Maybe this has nothing to do with primes. I suggest experimenting with various lists of "pseudoprimes".2012-07-29
  • 0
    Does your conjecture require $Z$ to be prime? It sounds like it, but it is not clear since your example uses $Z=25$.2012-07-29
  • 0
    @alex.jordan Yes. For every other odd prime from 3, the cycle seems to reach 1. However, by removing the `is-prime` constraint, we also get numbers like `8,14,20,25,27,30,33,35...` (for `Z=1`)2012-07-29
  • 0
    I had an answer - but it was based on buggy code. I've retracted it.2012-07-29
  • 0
    I can't post to OEIS, its unlisted there. Maybe someone might help? Here are some lists filtered by primality. [Z=0](http://pastebin.com/4sajf9rv), [Z=1](http://pastebin.com/Pn9p4qVG), [Z=2](http://pastebin.com/p1aLpsn3)2012-07-29
  • 0
    @Furlox I think those pastes are private.2012-07-29
  • 0
    @irrelephant: Sorry about that, fixed it. Thanks2012-07-29
  • 0
    Note that this question was also posted to MathOverflow, and some of the comments made there look useful.2012-07-29
  • 0
    [Link here](http://mathoverflow.net/questions/103433?sort=votes#sort-top). Thank you @Gerry Myerson!2012-07-29
  • 0
    I came back to this MUCH later, and now I think my answer may be a complete solution. I have left out rigor regarding the growth of the sum of primes though.2013-09-10

1 Answers 1

8

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.

  • 0
    Finding numbers for which terminal values are $-1$ still hasn't landed me an odd number. This strongly points towards there being a poof. edit: Read @alex.jordan's explanation, much better than what I posted.2012-07-29
  • 0
    An elementary result that would follow if odd numbers don't have $−1$ as a terminal is that there always exists a prime between $p_2n+1$ and $−1+\sum_{i=1}^{{2n+}1}p_i$ where $p_n$ is the $n-th$ prime. For example, $-1 + 2 + 3 + 5 = 9$, if there is no prime $p$ such that $52012-07-29
  • 0
    @Furlox I noted at MO that you are saying $-2$ is a possible terminal $N$-value. (I can't post there or I would.) This is not so. $-2$ is just as impossible to reach as $3$ is. I'll clarify in my answer. The lack of symmetry about $0$ is coming from how your algorithm lots $0$ with the negative numbers.2012-07-29
  • 0
    My real bad. That aside, even numbers only get $Z_t\in\{-1,0,1\}$ while odd numbers have $\{0,1,2\}$. Let us assume above observation is true till $2n+1$. Then, we can prove if $2n+1$ never reaches $1$, it will not reach $-1$. Follows from the fact that $2n$ would have the same chain as $2n+1$, but for a displacement of $1$ in values. Hence, at the terminus, $Z_t({2n})$ would displace to $2$ (from $-1$) instead of $-2$. This won't work for for any odd number reaching $1$ in the middle of the sequence, of course.2012-07-30
  • 0
    Of course, it would also have to happen that the only $1s$ I have encountered in odd number chains correspond to $Z_t$ values, which end the sequence. If this is the only place $1s$ might occur (for odd numbers), the conjecture would fall to induction.2012-07-30