login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #41 Sep 21 2023 19:32:23

%S 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,

%T 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

%N 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).

%C 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:

%C t = ((2^6)*(9k+1)-1)/3 = (18k*(2^5)+63)/3=192k+21 -> t == 0(mod 3),

%C t = ((2^5)*(9k+2)-1)/3 = (18k*(2^4)+63)/3=96k+21 -> t == 0(mod 3),

%C t = 9k+3 -> t == 0(mod 3),

%C t = ((2^4)*(9k+4)-1)/3 = (18k*(2^3)+63)/3=48k+21 -> t == 0(mod 3),

%C t = ((2^1)*(9k+5)-1)/3 = (18k+9)/3=6k+3 -> t == 0(mod 3),

%C t = 9k+6 -> t == 0(mod 3),

%C t = ((2^2)*(9k+7)-1)/3 = (18k*2+27)/3=12k+9 -> t == 0(mod 3),

%C t = ((2^3)*(9k+8)-1)/3 = (18k*(2^2)+63)/3=24k+21 -> t == 0(mod 3),

%C t = 9k -> t == 0(mod 3).

%C There are three additional facts according to the sequence:

%C 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.

%C 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.

%C 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.

%H Stefan Andrei, Manfred Kudlek, and Radu Stefan Niculescu, <a href="http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/41/pdf/B_217.pdf">Chains in Collatz's tree</a>, Report 217, 1999, Dep. of Informatics, University of Hamburg.

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,0,0,0,1).

%F 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

%o (BASIC)

%o Function a(n As Long)

%o Dim d As Long, k As Long

%o d = 0

%o If ((n Mod 3) <> 0) Then

%o k = n

%o Do

%o d = d + 1: k = k + k

%o Loop Until ((k Mod 9) = 1)

%o d = d + 1

%o End If

%o a = d

%o End Function

%Y Cf. A088975, A006370.

%K nonn,easy

%O 1,1

%A _Heinz Ebert_, Apr 10 2021