A prime number pattern 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
 A: This is implicit in Douglas Zare's comment to the problem as well as in domotorp's
posted answer and the comments following, but I will make it explicit: one can substitute
any slow growing sequence of integers for the primes and arrive at the same conclusion.
While slow growing could be suitably generalized to some ordered groups, for the integers I will
stick to there being  for every positive integer n at least one member p of the sequence satisfying
2n>=p>n, and all sequence members being greater than 1.
For if we have such a slow growing sequence, then starting from any positive n, the algorithm
will produce a partial sum in the interval [1 - p, p] using the term p.  Now we have a loop invariant
that applies to every step of the algorithm, and if the sequence has only finitely many terms less than
n and they are used in decreasing order of magnitude, the invariant is maintained for each successive
term p used.  The conditions above show that termination yields a partial sum in [-1,2].  If you
know the parity of the terms used, you can determine the parity of the result.  The fact that all
but one of the primes is odd explains the specific results seen by the poster.
Gerhard "Ask Me About System Design" Paseman, 2012.07.29
A: I think it is enough to use induction and Bertrand's postulate, that there is always a prime between n and 2n for n>1. Let me try to sketch the proof that we always reach 0, 1 or 2.
The induction hypothesis is that taking the primes up to p and starting from any |z|<2p, we reach 0, 1 or 2. Suppose we want to prove this for the next prime after p, denoted by q. We know that q<2p. Initially, |z|<2q. Once we subtract (supposing z>0) q from it, we get z< q< 2p.
A: Let $p$ be a prime such that the number of primes less than it is odd. Each number in the interval $[1-p,p]$ is a possible location for a sequence of $Z$s in the step directly after $p$ is added or subtracted. Some of these sequences end in $-1$, some do not. The convex hull of the numbers whose sequences end in $-1$ forms an interval. We will show, by induction, that this is about $[-p/2,p/2]$
Let $p_1$ and $p_2$ be the next two primes. If $x$ is the upper or lower bound for the interval of $p_2$, after applying the process twice it must be in the interval for $p_1$.
The upper bound: Clearly positive, so at the next step we subtract $p_1$. If this is still positive, then it is very close to $0$, so $u-p_1-p_2$ is very far from $0$ and not in the interval as long as the interval is approximately $[-p/2,p/2]$. So it's negative, and at the next step we add $p_2$. Thus the upper bound can increase by no more than $p_1-p_2$.
By identical logic, the lower bound can decrease by no more than the same amount. So it increases by a difference of two primes every two primes, so it's about half the size of the corresponding prime, so the hypothesis we need for induction is satisfied. it remains to check that this is true at some small prime. If my calculaions are correct for $p=41$ the interval is $[-19,17]$ which clearly qualifies, and we can manually check there are no solutions up till then.
Since the interval is small, the prime $p$ is never contained in it, and so the stated pattern occurs.
