Problems & Puzzles: Puzzles

Puzzle 73.- A Collatz-like sequence. (A puzzle suggested by Jack Brennen )

Consider the sequence of integers B[] defined by a starting point B[0] and the rules:

1. If B[n] is prime, B[n+1] is defined as 3*B[n]+1.
2. If B[n] is composite, B[n+1] is defined as the largest proper divisor of B[n], which can also be described as B[n]/P, where P is the smallest prime factor of B[n].

This is obviously derived from the Collatz problem, and in fact, all even or prime numbers >= 3 have the same successor as they do in the Collatz sequence; only the number 2 and odd composites behave differently...

The question is this: Does every starting point eventually end up entering the cycle ... 2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2 ..

The same question can be posed with the rule changed so that prime numbers go to 3*B[n]-1 instead of 3*B[n]+1.  Do all starting points then eventually enter this cycle?  ... 5, 14, 7, 20, 10, 5 ...

Solution

Felice Russo got the following interesting results:

"Question 1. I have checked (with an Ubasic program) that all the integers between 2 and 2^27 terminate in the cycle: 2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2. Moreover for the first 1000 integers I calculated the number of steps needed to end up in the cycle. I indicate this quantity with T(n) and we can call it the "transient time".

Then I calculated the ratio T(n)/n ("Normalized Transient time") which behavior is reported in the below graph.

<<graph>>

I have estimated an interpolating function given by: T(n)/n ~ 6.2*n^(-0.813) with a good R^2 value. Moreover I found that the average transient time <T(n)>=1/N*sum(n=1 to N). T(n) grows as the logarithm of n, namely: <T(n)> ~ 2.8*ln(n) and then the average transient time goes to infinite only for n-->00.

According to the experimental data, the function T(n)/n seems falls asymptotically as n increase; so it is very likely that T(n)/n never will diverges. So I'm enough confident to pose the following conjecture for the case 1:All the integers generate a Collatz-like sequence that end-up entering in the cycle 2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2. Similar results have been obtained for the question 2.

Question 2. All the integers between 2 and 2^27 have been checked to terminate in the cycle: 5, 14, 7, 20, 10, 5

About the Normalized transient time T(n)/n and the average transient time <T(n)> we have a behavior similar to the previous case: T(n)/n ~ 2.34*n^(-0.7477) with R^2 ~ 0.76. <T(n)> ~ 1.8*ln(n)

Then as done previously the following conjecture can be posed for the case 2: All the integers generate a Collatz-like sequence that end-up entering in the cycle 5, 14, 7, 20, 10, 5."

 Records   |  Conjectures  |  Problems  |  Puzzles