Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Using $(3p+1)/2$ starting with $p = 44102911$, we find an ordered set of $8$ primes. By computer, we find that this is the only ordered set of $8$ primes $< 300000000$ primes.

The primes:

$\{44102911, 66154367, 99231551, 148847327, 223270991, 334906487, 502359731, 753539597\}$

When we take the differences and remove the common factor, $344554$, we have:

$\{64, 96, 144, 216, 324, 486, 729\}$

As you can see, this is the $7th$ row of Nicomachus's Triangle. A036561


Question: What would it take to show that a count of $8$ is the upper bounds for this ordered set?

Terry Tao has a recent blog about this.

Collatz on arxiv and another Collatz on arxiv.

Set of $7$ primes

$\{89599, 134399, 201599, 302399, 453599, 680399, 1020599\}$

When we take the differences and remove the common factor, $1400$, we have:

$\{32, 48, 72, 108, 162, 243\}$

As you can see, this is the $6th$ row of the triangle.

share|cite|improve this question
up vote 5 down vote accepted

The numbers $p_i$ in your list are of the form $p_i=344554\cdot2^{7-i}3^i-1,$ for $i=0,1,\ldots,7$, so there is nothing mysterious about the appearance of a row from Nicomachus' triangle, as $$ \frac{p_{i+1}-p_i}{344554}=3^{i+1}2^{6-i}-3^i2^{7-i}=3^i2^{6-i}(3-2)=3^i2^{6-i}. $$ Of course, it is rare that they would all primes, but as Gerry Myerson explained, there is no obvious reason, why we couldn't find even longer sequences of primes given that the residue class of $-1$ is a fixed point for the mapping $x\mapsto(3x+1)/2$ modulo $q$, $q$ any odd prime.

As an example of a constraint to your search for such sequences, implicit in Gerry's answer, let us consider the following. If you search for such a sequence of length ten, then all the primes in that sequence must be congruent to $-1$ modulo $11$. This is because the mapping $x\mapsto(3x+1)/2$ permutes the other residue classes modulo $11$ as a 10-cycle: $$ 6\mapsto 4\mapsto 1\mapsto 2\mapsto 9\mapsto 3\mapsto 5\mapsto8\mapsto 7\mapsto 0(\mapsto 6), $$ so any integer $x$ that is not $\equiv-1\pmod{11}$ will become divisible by eleven after at most nine iterations.

Trying to address the question on the emergence of Nicomachus' triangle. Assume that we start a Collatz run from the number $a_0=m\cdot 2^k-1$, where $k>0$ and $m$ is an odd integer. Observe that every odd positive integer $a_0$ can be written in this way. As $a_0$ is odd, the next Collatz step gives $3a_0+1=m\cdot2^k\cdot3-2$. This is an even number, so the next step yields $a_1=m\cdot2^{k-1}\cdot3-1.$ If $k>1$, then we can repeat the same reasoning, and two further steps of Collatz gives us $a_2=(3a_1+1)/2=m\cdot2^{k-2}\cdot3^2-1.$ The logic will be broken after $2k$ Collatz steps, because $a_k=m\cdot2^03^k-1$ is an even number, so the two types of steps stop alternating at this point.

Assume that the numbers $a_i$ are primes in the range $i=0,1,\ldots,\ell$. Obviously then $\ell<k$. Let us consider the differences $\Delta_i=a_{i}-a_{i-1}$, for $i=1,2,\ldots,\ell$. Then $$ \Delta_i=(m\cdot2^{k-i}3^i-1)-(m\cdot2^{k-i+1}3^{i-1}-1)=m\cdot2^{k-i}3^{i-1}(3-2) =m\cdot2^{k-i}3^{i-1}. $$ We immediately see that the greatest common divisor of the numbers $\Delta_i,i=1,2,\ldots,\ell$ is $d=m\cdot2^{k-\ell}.$ This is because, we always have $3\Delta_i=2\Delta_{i+1}$. Thus the numbers $$ \frac{\Delta_i}{d}=\frac{m\cdot2^{k-i}3^{i-1}}{m\cdot2^{k-\ell}}=2^{\ell-i}3^{i-1} $$ form the $\ell^{\text{th}}$ row Nicomachus' triangle with $i$ ranging from $1$ to $\ell$.

share|cite|improve this answer is rare that they would all [be] primes... My observations indicate that matching to the Triangle is a necessary condition to finding only primes in the set. I'll edit the OP to include some sets of 5, 6, and 7 – Fred Kline May 27 '12 at 7:48
@Rudy, I think that you get a similar match with the triangle, whenever the numbers are such that Collatz rules force the pair of operations $x\mapsto 3x+1\mapsto (3x+1)/2$ to be followed enough many times. Quite irrespective of whether the numbers are all primes or not. Should I elaborate on that? – Jyrki Lahtonen May 27 '12 at 7:55
I know this can generate sequences on non-primes as well. However, I force primes at each step.… for a slight variation of the algorithm – Fred Kline May 27 '12 at 8:23
@Rudy, does the latest addition answer your question? – Jyrki Lahtonen May 27 '12 at 8:54
Yes, thank-you. So you're counting the multiply and divides as two Collatz steps? So my count of eight would be sixteen? – Fred Kline May 27 '12 at 10:40

I would expect you'd get arbitrarily long sequences of primes by iterating $(3p+1)/2$. You're asking whether some finite set of linear expressions can be simultaneously prime. The general belief is that it can be, if there is no simple congruential reason why it can't. For small primes $q$, just make sure $p+1$ is a multiple of $q$. For sufficiently large primes $q$, there should be no problem.

share|cite|improve this answer

Your Answer


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.