1
$\begingroup$

The Collatz function applied to a number $x$ gives $3x+1$ when $x$ is odd and $x/2$ when $x$ is even. Consider the following Collatz sequence:

97760291, 293280874, 146640437, 439921312, 219960656, 109980328, 54990164, 27495082, 13747541, 41242624, 20621312, 10310656, 5155328, 2577664, 1288832, 644416, 322208, 161104, 80552, 40276, 20138, 10069, 30208, 15104, 7552, 3776, 1888, 944, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

If we ignore even numbers then this sequence contains 14 consecutive odd primes (highlighted in bold). What is the most number of consecutive odd primes that can be found in a Collatz sequence?

This question was inspired by this one: Prime numbers in Collatz sequences

$\endgroup$

3 Answers 3

4
$\begingroup$

Your question is equivalent to find prime numbers : $$p,\frac{3p+1}{2^{a_1}},\frac{3\bigg(\frac{3p+1}{2^{a_1}}\bigg)+1}{2^{a_2}},\ldots$$ for arbitrarily long chains, say of length $n$. This is similar to Cunningham chains. According to Dickson's conjecture, $n$ can get arbitrarily large. Thus, one must expect there to be arbitrarily large chains of such primes in the Collatz Sequence.

$\endgroup$
7
  • $\begingroup$ Oh sorry, I'll have to fix that $\endgroup$
    – Haran
    Jun 26, 2020 at 11:17
  • $\begingroup$ Thanks for the answer. In the case of standard Cunningham chains (multiplier of 2), it seems that there is no direct way of obtaining large chains (despite Dickson's conjecture). Would this also be the case here? $\endgroup$ Jun 26, 2020 at 11:19
  • $\begingroup$ @DmitryKamenetsky Yes, there would most likely not be any direct way to find a cluster of such prime numbers $\endgroup$
    – Haran
    Jun 26, 2020 at 11:21
  • $\begingroup$ It seems to me that the existence of arbitrarily long chains of primes in the odd entries of a Collatz sequence would follow from Dickson's conjecture, but I don't see how it's equivalent. $\endgroup$ Jun 26, 2020 at 11:28
  • 2
    $\begingroup$ The question that OP asked is equivalent to the chain of numbers being prime, and the fact that the chain can be arbitrarily large with primes only follows from Dickson's conjecture. Sorry if it wasn't clear. $\endgroup$
    – Haran
    Jun 26, 2020 at 12:51
3
$\begingroup$

There is almost surely an existing Mersenne-prime-like conjecture to the effect that for any prime $p\gt3$, there is a prime $q\gt3$ of the form

$$q={2^np-1\over3}$$

with $n\ge1$. (I'd appreciate any confirmation or correction on this conjecture that such a conjecture exists; I looked through Richard Guy's UPINT and didn't see it.) If we always take the smallest $n$ for which $(2^np-1)/3$ is a prime greater than $3$, we can form a Collatz chain backwards:

$$1\leftarrow2\leftarrow4\leftarrow8\leftarrow16\leftarrow5\leftarrow10\leftarrow20\leftarrow40\leftarrow13\leftarrow26\leftarrow52\leftarrow17\leftarrow34\leftarrow11\leftarrow22\leftarrow7\leftarrow14\leftarrow28\leftarrow56\leftarrow112\leftarrow37\leftarrow\cdots$$

(Suppressing the even entries, that's $1\leftarrow5\leftarrow13\leftarrow17\leftarrow11\leftarrow7\leftarrow37\leftarrow\cdots$.)

The existence of arbitrarily long chains of primes as consecutive odd entries in a Collatz sequence doesn't depend on this conjecture (that is, the conjecture need not hold for every prime $p$, just for enough primes to get arbitrarily long chains), but it would follow from it.

$\endgroup$
4
  • $\begingroup$ I think I posted pretty much the same idea. $\endgroup$ Jun 26, 2020 at 14:29
  • $\begingroup$ @DmitryKamenetsky, indeed, great minds think alike... Interesting that the primes in your sequence get so large so quickly. Can you add some to mine? $\endgroup$ Jun 26, 2020 at 14:50
  • $\begingroup$ @samerivertwice, I'm not sure what you're referring, unless it's something you deleted before I had a chance to see it. $\endgroup$ Jul 2, 2020 at 17:07
  • $\begingroup$ @BarryCipra yes I deleted something. For $p$ not prime, there are sequences such that $3x+1=2^rp$ of the form $4^nx+\frac{4^n-1}{3}$ containing one or no primes. An early counterexample is $1,5,21,85,\ldots$ which factors to something like $\frac{(m+1)(m-1)}3$ and therefore $5$ is its only prime. These are linear combinations of Lucas sequences, and divisibility sequences, so the further one gets along any sequence the smaller becomes the likelihood of meeting a prime. But of course none of this is a counterexample to your answer. $\endgroup$ Jul 2, 2020 at 17:16
0
$\begingroup$

I believe I found a way to generate an infinite sequence of such primes. We proceed in reverse order. Start with a prime. Now multiply by 2. If the new number minus one is divisible by 3 and the result is a prime then output it (#). Otherwise continue multiplying by 2 until you reach condition (#), which could take a while. For example if we start with 19 then we will generate this sequence of primes: 19, 101, 67, 89, 59, 157, 13397, 9820104851543381, 1757376215861239855011157... There are more prime terms after this, but they get quite large. Also I am not sure if this will continue to find new primes.

$\endgroup$
1
  • 1
    $\begingroup$ This will likely eventually fail for the reasons in the comments I have put on Barry's answer. $\endgroup$ Jul 2, 2020 at 16:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .