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