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.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,1).
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
Heinz Ebert, Apr 10 2021
STATUS
approved