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:
- If B[n] is prime, B[n+1] is defined as 3*B[n]+1.
- 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."
|
