13
$\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

$\endgroup$
8
  • $\begingroup$ This doesn't fit the site, but I'll give some hints. Use induction to bound the magnitude. The parity follows from considering what you are doing mod $2$. $\endgroup$ Jul 29, 2012 at 8:48
  • $\begingroup$ Dear Furlox, Welcome to MO. I think these kind of questions are not to be posted at MO ( Read FAQ's ). But your question seems to be quite interesting. You can try these things : 1) Verify the truth in your conjecture , by writing some machine code and computing the pattern for the largest number you can. Sometimes you can win, by just verifying up-to a largest number a machine can compute. $3n+1$ conjecture is widely believed for its computational truth, it has been verified for many large numbers. Contd.. $\endgroup$ Jul 29, 2012 at 8:58
  • $\begingroup$ Don't bother about the proof. Not all conjectures are proved. They are based upon some heuristics or some machine calculations. So if you can come up with the same pattern for some large prime $p$, then its done. 2) Along with your calculations and clear description, prepare a LaTeX file and then post it here. You can look at the naming conventions that Tao has suggested, which makes your problem attractive. You can read it here . In that he writes about the naming $\endgroup$ Jul 29, 2012 at 9:02
  • $\begingroup$ But my sincere request to you is to come up with some heuristic argument or numerical evidence. Please post it as a journal article, and if it is potential, you can add one more open problem in Number theory ;) . My sincere and best wishes to you. $\endgroup$ Jul 29, 2012 at 9:03
  • 4
    $\begingroup$ @Douglas and Shanmukha: I do not understand why you guys do not support this question. Although the write up does not meet the usual standards of MO and the problem might not have applications, it is interesting and non-trivial. $\endgroup$
    – domotorp
    Jul 29, 2012 at 9:17

4 Answers 4

5
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I would like a formal proof. Knowing the initial parity cannot be used to predict a result. The final parity is still dependent on $\pi(x)$. $\endgroup$
    – Furlox
    Jul 30, 2012 at 11:48
  • $\begingroup$ About the whole $-2$ thing, I applied the algorithm wrong for $9$. And didn't double check. I'm sorry guys! $\endgroup$
    – Furlox
    Jul 30, 2012 at 11:51
  • $\begingroup$ I am a bit confused. Sure this will depend on pi(x) but the question says so (implicitly) when talking about any other prime. For 3 and evry other prime there after...so precisely if one starts at the k-th prime with k even! Yet, then, I still do not see an argument why -1 cannot occur. So I am even more confused. $\endgroup$
    – user9072
    Jul 30, 2012 at 12:14
  • $\begingroup$ @quid: Yes, conjecture is equivalent to $Z_f(P({2n}))=1$ Also, so far, $-1$ hasn't shown up for me (and I assume, for others who checked via programs, otherwise they would have posted). It is very possible that there is some prime number with $Z_f$ equal to $-1$. However, I find it unlikely as every odd number so far has terminated in $\{0,1,2\}$ only. Check the page on M.SE, I think it has a better explanation. $\endgroup$
    – Furlox
    Jul 30, 2012 at 13:44
  • $\begingroup$ $-1$ cannot occur, is more personal opinion and evidence based guessing than proven fact. Maybe I didn't make that clear. Making the assumption seems to make the problem 'almost' susceptible to inductive methods, heuristics, or some witch's brew of everything we need :) $\endgroup$
    – Furlox
    Jul 30, 2012 at 13:54
4
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ The above induction wouldn't suffice to prove the regularity in pattern, i.e. only every other prime, beginning with 3, reaches 1. $\endgroup$
    – Furlox
    Jul 29, 2012 at 13:50
  • $\begingroup$ Also, while we inductively prove for the next prime $q$, we also need to prove that $z \in \{0,1,2\}$ for all $2r>k>2q$ where $r$ is the next prime (before we attempt induction on $r$). $\endgroup$
    – Furlox
    Jul 29, 2012 at 14:20
  • $\begingroup$ Plus, the claim is simply not true for $Z=4 < 2 \cdot 3$. We obtain $4-3-2 = -1$. $\endgroup$
    – Niemi
    Jul 29, 2012 at 14:40
  • $\begingroup$ We can extend that example to a counterexample to the main claim! $19 - 19 = 0 + 17 = 17 - 11 = 6 - 7 = -1 + 5 = 4 - 3 = 1 - 2 = -1.$ $\endgroup$
    – Will Sawin
    Jul 29, 2012 at 15:12
  • $\begingroup$ 'If n is prime, it is assumed accounted for by the first step' $19-17-13+11+7-5-3+2=1$ $\endgroup$
    – Furlox
    Jul 29, 2012 at 15:20
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @Will: I am totally lost as to what you mean by 'smallest subinterval $[p-1,p]$ ... which after $p$ is that number ends at $-1$.' Also, you refer to primes where $Pi(x=p)$ is odd. However, the unresolved 'pattern' relates to $Pi(x=p)$ being even. If thats what $p_1$ and $p_2$ deal with, I'm really sorry. May I ask for a complete example, so I can understand better? Thanks! $\endgroup$
    – Furlox
    Jul 31, 2012 at 5:14
  • $\begingroup$ I believe I clarified that. $\endgroup$
    – Will Sawin
    Jul 31, 2012 at 12:14
  • 1
    $\begingroup$ I think you mean [1-p,p]. Also, I worry that the same argument can apply for starting with (ending with) 1. If you can contrast the two situations, that will make a compelling argument. Gerhard "Ask Me About System Design" Paseman, 2012.07.31 $\endgroup$ Jul 31, 2012 at 15:43
  • 1
    $\begingroup$ I did not check the entire argument in detail, but for the contrast of the two situations: for 1, we can not 'manually check there are no sulotions up till then'. $\endgroup$
    – user9072
    Jul 31, 2012 at 16:54
  • $\begingroup$ Yes, that's basically why. There are lots of solutions, and a solution implies that the interval is quite large. Then it's possible for there to be too subtractions or two additions in a row, meaning the interval can grow faster and can continue to be quite large. $\endgroup$
    – Will Sawin
    Jul 31, 2012 at 17:16
1
$\begingroup$

I prove below that if $n$ is odd then it can not end up in -1 as terminal value after applying your process. There are some details minor missing.

Let $n$ be an integer on the range $[p_k+1,p_{k+1}]$ And define $Z_i$ ($i=k,k-1,\dots,1$) as $$ Z_i = \begin{cases} Z_{i+1}-p_i \quad &\text{if } Z_{i+1} > 0\\\\Z_{i+1}+p_i \quad &\text{if } Z_{i+1}\le 0 \end{cases}$$ the first step is to prove that $$ -p_i < Z_i \le p_i\quad\quad\quad(\*) $$

First we see that $Z_k \le p_k$, but otherwise $$ p_{k+1} > Z_{k+1} = Z_k+p_k > 2p_k $$ and this contradicts Bertrand's postulate. On the other hand $Z_k > 0 > -p_k$ trivially, so we have the inequality for $i=k$. Now if the inequality is true for $i+1$ (with $i>1$) it is also true for $i$, because we have:

  • if $Z_{i+1} \le 0$ then $Z_i \le p_i$ and if $Z_i \le -p_i$ then $$ -p_{i+1} + p_i < Z_{i+1} + p_i = Z_i \le -p_i $$ contradicting Bertrand's postulate.

  • if $Z_{i+1} > 0$ then $Z_i > -p_i$ by definition and if $Z_i > p_i$ then $$ p_i < Z_i = Z_{i+1}-p_i \le p_{i+1}-p_i $$ again contradicting Bertrand's postulate.

In particular for $i=1$ we get $-2 < Z_1 \le 2$ which shows that the only possible end values are -1,0,1 and 2. We want to rule out the value $-1$ whenever $n$ is odd. By the same inequality the only possible values of $Z_2$ are $-2,-1,0,1,2,3$, and and the only one that leads to $Z_1=-1$ is $Z_2=1$, so we can asume that we start with a value of $n$ that leads to $Z_2=1$. It is also easy to see using a parity argument that if $n$ is odd and ends in $-1$ then $k$ is even say $p_{2k+1} > n \ge p_{2k}$

The second step we consider the two sequences \begin{align} W_i &= \{-1, 1, -2, 3, -4, 7, -6, 11, -8, \dots \} \quad \text{and} \\\\ Y_i &= \{-1, 1, 4, -1, 6, -5, 8, -9, 12, \dots \} \end{align} where the $i$th term comes from the preceding adding or substracting the $(i-1)$th prime ie $$ W_1 = -1, W_2 = 1, W_{2i+1} = W_{2i}-p_{2i}, W_{2i} = W_{2i-1}+p_{2i-1} $$ and $$ Y_1 = -1, Y_2 = 1, Y_{2i+1} = Y_{2i}+p_{2i}, Y_{2i} = Y_{2i-1}-p_{2i-1} $$ it is easy to verify that both series alternate positive and negative values after the third term and that $\lvert W_i \rvert > i$ and $\lvert Y_i\rvert \ge i$ for $i\ge 10$.

We are going to prove that if $Z_i$ is a sequence with terminal value -1, then for all $i$ $$ Y_{2i} \le Z_{2i} \le W_{2i} \quad \text{and} \quad Z_{2i+1} \le W_{2i+1}\text{ or } Y_{2i+1} \le Z_{2i+1} \quad\quad\quad (\*\*)$$ We need first a simple (and nice:) bound on prime gaps: For all $n$ we have $$ p_{n+1}-p_n \le n $$ to prove it, it is enough to combine the inequalities of Dusart and of Miller-Robin inequalities for the $n$-the prime (see here for the references) say $$ p_n > n(\log n + \log \log n -1 ) \quad \text{for all } n $$ and $$ p_n < n(\log n + \log \log n -1 +1.8\log \log n/\log n) \quad \text{if } n > 13 $$ and check by hand the small cases. (I suppose there are proofs of this fact that don't use the prime number theorem at all).

Now suppose that for a given $n$ with terminal value $-1$, some $Z_i$ doesn't verify either of the inequalities $(\*\*)$, let's take the least such $i$, if $i=2t+1$ is odd this means that $$ W_{2t+1} < Z_{2t+1} < Y_{2t+1} $$ but then if $Z_{2t+1}>0$, then $$ Z_{2t} = Z_{2t+1}-p_{2t} < Y_{2t+1}-p_{2t} = Y_{2t} $$ and if $Z_t \le 0$ then $$ Z_{2t} = Z_{2t+1}+p_{2t} > W_{2t+1} + p_{2t} = W_{2t} $$ in either case it contradicts that $i$ is least.

So we can assume that $i$ is even say $i=2t$. This implies that $Z_{2t} < Y_{2t}$ or that $Z_{2t} > W_{2t}$, in the first case by the minimallity of $i$ we have either $$ Z_{2t-1} \le W_{2t-1} \quad \text{or}\quad Z_{2t-1} \ge Y_{2t-1} \quad\quad (\*\*\*)$$ the second case is clearly impossible as $Z_{2t} < Y_{2t}$, for the first case we would have using (*): $$ -p_{2t} + p_{2t-1} < Z_{2t}+p_{2t-1} \le W_{2t-1} $$ but this implies that $p_{2t}-p_{2t-1} > W_{2t-1} > 2t-1$, a contradiction if $2t-1\ge 10 $.

Identically if $Z_{2t} > W_{2t}$ then again using $(\*\*\*)$ we see that $Z_{2t-1} \ge Y_{2t-1}$ and $$ 2t-1 < Y_{2t-1} \le Z_{2t} + p_{2t-1} \le p_{2t}+p_{2t-1} $$ again a contradiction if $2t-1\ge 10$.

We are left a few number of cases that can be ruled out by checking them by hand (going back from -1 and seeing what are the possible chains that end up at -1 for the first few primes.)

Finally, if some $n$ odd ends up in $-1$, then as we stated before $$ p_{2k+1} > n \ge p_{2k}$$ and then $$ n=Z_{2k}\ge p_{2k} > W_{2k} $$ contradicting $(\*\*)$.

$\endgroup$

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