Problems & Puzzles: Puzzles

Puzzle 299. Collatz-like sequence of primes.

Rudolph Knjzek, sent the following nice & interesting puzzle:

Let's define a Collatz-like sequence of primes. Start with a prime number p>2.
The next number is the largest primefactor of 3p+1. The sequence stops if we reach 2.

Clearly, the next prime is less than the previous if (3p+1)/2 is composite and only larger than the previous if (3p+1)/2 is prime.

The obtained sequences contain subsequences of n increasing primes, i.e. n=3: 7-11-17 and n=4: 31-47-71-107.

And there are the questions:

1. Can you proof, that there is no loop in the sequences and that all sequences converge to 2?

2. Find increasing subsequences with n>4.

3. Is there an upper limit for the length of increasing subsequences?

4. Find sequences starting with p, containing all primes less than p.

5. Change the rule for the next number from 3p+1 to 3p-1. Is there a significant change of the properties of the sequences?

Contributions came from Luke Pebody, Faride Firoozbakht & Anurag Sahay. Nevertheless the main question (1) is still open...

Luke wrote:

Q2.The smallest increasing subsequences of length n for n=1,2,3,4,5,6,7,8 start with 3,7,31,2111,89599,89599,44102911. The smallest with n=9 is at least 7*10^8.

Q4. The only such sequences are [2] and [3,5,2]:

Proof: Any other such prime must include both 3 and 7. Thus it must reach one of them first. When it reaches 3, it then goes 5 and then terminates at 2, bypassing 7 altogether. Therefore 7 must be hit first. However the route from 7 goes:
7,11,17,13,5,2, bypassing 3 altogether.

Faride Firoozbakht wrote:

Q2. The same than Luke.

Q3. I guess that the sequence 3,3,7,31,2111,89599,89599,44102911,...
is an infinite sequence so there is no an upper limit for the length of increasing subsequences.

Q4. The only such sequence is the sequence starting with p=3: 3,5,2 because if p>3 then 3 can't be a term of sequence ( 3 doesn't divide (3p+1)/2 ).

Q5. No, there isn't a significant change of the properties of the sequences. Because in this case for some primes there is a loop of the form 5-7-5 and for other primes the corresponding sequence converges to 2.

Primes such that the corresponding sequence converges to 2 :


Primes such that the corresponding sequence has a loop (of the form 5-7-5):


Follow-up question : In this case , for which primes the corresponding sequence converges to 2?

Anurag Sahay wrote:

Question 5: Yes, they behave differently.

Two major differences for 3*n-1:

1) there is a loop in every sequence except 3-2
2) They do not converge . Examples: 31-23-17-5-7-5...

I have also observed that there are fewer increasing sequences of a given length when compared to 3*n+1

Question 4: some sequences with all primes less than p

79 17 13 5 2,
53 5 2 ,
113 17 13 5 2,
83 5 2,
293250815317 13423957 1229 461 173 13 5 2

Question 3:
I think there is no upper limit.
It is difficult to prove the contrary (that there should be an upper limit).


Later (31/1/05), Mike Oakes sent 'a partial solution to Q1':

There cannot be a repeating 2-cycle.
Suppose there is a cycle p - q - p - ...
Case(A): Suppose p = +1 mod 4.
Then (3*p+1) = 0 mod 4, and (3*p+1)/4 = q * r, where q is odd, r >= 1.
q = (3*p+1)/(4*r).
For a 2-cycle, p must divide (3*q+1), and (3*q+1) is even,
so (3*q+1) >= 2*p.
i.e. (9*p+3)/(4*r) + 1 >= 2*p,
i.e. (9*p+3)/(4*r) >= (2*p-1)
i.e. r <= (9*p+3)/(8*p-4)
So r = 1, and q = (3*p+1)/4.
Now, p divides (3*q+1) = (9*p+7)/4, so p = 7, which = -1 mod 4.
Case(B). Suppose p = +3 mod 4.
Then (3*p+1) = 2 mod 4, and (3*p+1)/2 = q * r, where q and r are odd.
q = (3*p+1)/(2*r).
For a 2-cycle, p must divide (3*q+1), and (3*q+1) is even,
so (3*q+1) >= 2*p.
i.e. (9*p+3)/(2*r) + 1 >= 2*p,
i.e. (9*p+3)/(2*r) >= (2*p-1)
i.e. r <= (9*p+3)/(4*p-2)
So r cannot be 3, so r = 1, and q = (3*p+1)/2.
Now, p divides (3*q+1) = (9*p+5)/2, so p = 5, which = +1 mod 4.
So there are no 2-cycles.


Even Rudolph Knjzek added this interesting feature:

A prime number of the form p=4n+1 can't be the first prime of an increasing subsequence, because (3p+1)/2 is even and the next prime is less than p.
An increasing subsequence must start with a prime of the form p=4n-1.
It is easy to proof, that the primes of an increasing subsequence have the form
4n(3/2)^k-1. This deduces, that the maximum possible length of the sequence is determined by the power of 2 in the prime factorisation of n. If n=2^r*odd and k=r+2 we get an even number and the subsequence ends, assuming the sequence hasn't been terminated by a composite before.
To obtain large subsequences, we need a large first prime number. But question 3 is still open, written in another form:
Is it possible to construct a sequence of the form 4n(3/2)^k-1, all numbers prime for k=0,1,2,3,... of arbitrary length, when chosing an appropriate value for n ?
In opposition to Faride, I guess, it isn't possible, because primes become rare when the numbers get large.




Records   |  Conjectures  |  Problems  |  Puzzles