Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
but does $-17-17=0?$ –  dato datuashvili Jul 29 '12 at 8:56
    
@dato OP says that if the current value is negative, you are to add, not subtract –  alex.jordan Jul 29 '12 at 9:01
2  
This has the feel of the Collatz Conjecture although there are significant differences. –  alex.jordan Jul 29 '12 at 9:03
3  
Maybe this has nothing to do with primes. I suggest experimenting with various lists of "pseudoprimes". –  Christian Blatter Jul 29 '12 at 9:15
    
Does your conjecture require $Z$ to be prime? It sounds like it, but it is not clear since your example uses $Z=25$. –  alex.jordan Jul 29 '12 at 9:19
show 8 more comments

1 Answer 1

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.

share|improve this answer
    
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. –  Furlox Jul 29 '12 at 11:26
    
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 $5<p<9$ then we have a contradiction. –  Furlox Jul 29 '12 at 14:09
    
@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. –  alex.jordan Jul 29 '12 at 19:42
    
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. –  Furlox Jul 30 '12 at 11:18
    
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. –  Furlox Jul 30 '12 at 11:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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