|
| |
|
|
A343280
|
|
a(n) is the number of steps for the n-th vertex of the Collatz tree A088975 to reach a vertex t == 0 (mod 3).
|
|
0
|
|
|
|
7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The terminal node t == 0 (mod 3) can be computed by repeated application of the operation m'=2m until n*(2^(a(n)-1)) == 10 (mod 18) is valid; then application of the operation m'=(m-1)/3 results in t = (n*(2^(a(n)-1))-1)/3. Both operations are part of the inverse Collatz function. The sequence repeats after every n == 0 (mod 9) thus:
t = ((2^6)*(9k+1)-1)/3 = (18k*(2^5)+63)/3=192k+21 -> t == 0(mod 3),
t = ((2^5)*(9k+2)-1)/3 = (18k*(2^4)+63)/3=96k+21 -> t == 0(mod 3),
t = 9k+3 -> t == 0(mod 3),
t = ((2^4)*(9k+4)-1)/3 = (18k*(2^3)+63)/3=48k+21 -> t == 0(mod 3),
t = ((2^1)*(9k+5)-1)/3 = (18k+9)/3=6k+3 -> t == 0(mod 3),
t = 9k+6 -> t == 0(mod 3),
t = ((2^2)*(9k+7)-1)/3 = (18k*2+27)/3=12k+9 -> t == 0(mod 3),
t = ((2^3)*(9k+8)-1)/3 = (18k*(2^2)+63)/3=24k+21 -> t == 0(mod 3),
t = 9k -> t == 0(mod 3).
There are three additional facts according to the sequence:
1. The sequence is based on the proof of S. Andrei et al. (see LINKS) that at most 7 steps are needed to reach a multiple of 3.
2. The distance 1 is missing due to the fact that all y == 10 (mod 18) are congruent to 1 modulo 9. Obviously for every positive integer y == 10 (mod 18) the distance to the next level is 1 not 7, since ((18k+10)-1)/3 = 6k+3. Thus repeating the proof with all rest classes modulo 18 includes the distance 1 but blows up the sequence to: 7, 6, 0, 5, 2, 0, 3, 4, 0, 1, 6, 0, 5, 2, 0, 3, 4, 0 but without touching the previous fact.
3. Another consequence is that there exists a path P from every positive integer n as a start terminal of P to an end terminal t == 0 (mod 3). Thus every path P is unique because of the unique start node n but the map t = (n*(2^(a(n)-1))-1)/3 is surjective.
|
|
|
LINKS
|
Stefan Andrei, Manfred Kudlek, and Radu Stefan Niculescu, Chains in Collatz's tree, Report 217, 1999, Dep. of Informatics, University of Hamburg.
|
|
|
FORMULA
|
G.f.: -x*(4*x^7 + 3*x^6 + 2*x^4 + 5*x^3 + 6*x + 7)/(x^9 - 1). - Thomas Scheuerle, Apr 12 2021
|
|
|
PROG
|
(BASIC)
Function a(n As Long)
Dim d As Long, k As Long
d = 0
If ((n Mod 3) <> 0) Then
k = n
Do
d = d + 1: k = k + k
Loop Until ((k Mod 9) = 1)
d = d + 1
End If
a = d
End Function
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
