cp's OEIS Frontend

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

%I A343280 #41 Sep 21 2023 19:32:23
%S A343280 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 A343280 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 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).
%C A343280 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 A343280   t = ((2^6)*(9k+1)-1)/3 = (18k*(2^5)+63)/3=192k+21 -> t == 0(mod 3),
%C A343280   t = ((2^5)*(9k+2)-1)/3 = (18k*(2^4)+63)/3=96k+21  -> t == 0(mod 3),
%C A343280   t = 9k+3 -> t == 0(mod 3),
%C A343280   t = ((2^4)*(9k+4)-1)/3 = (18k*(2^3)+63)/3=48k+21  -> t == 0(mod 3),
%C A343280   t = ((2^1)*(9k+5)-1)/3 = (18k+9)/3=6k+3           -> t == 0(mod 3),
%C A343280   t = 9k+6 -> t == 0(mod 3),
%C A343280   t = ((2^2)*(9k+7)-1)/3 = (18k*2+27)/3=12k+9       -> t == 0(mod 3),
%C A343280   t = ((2^3)*(9k+8)-1)/3 = (18k*(2^2)+63)/3=24k+21  -> t == 0(mod 3),
%C A343280   t = 9k -> t == 0(mod 3).
%C A343280 There are three additional facts according to the sequence:
%C A343280 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 A343280 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 A343280 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 A343280 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 A343280 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%H A343280 <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 A343280 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 A343280 (BASIC)
%o A343280 Function a(n As Long)
%o A343280   Dim d As Long, k As Long
%o A343280   d = 0
%o A343280   If ((n Mod 3) <> 0) Then
%o A343280     k = n
%o A343280     Do
%o A343280       d = d + 1: k = k + k
%o A343280     Loop Until ((k Mod 9) = 1)
%o A343280     d = d + 1
%o A343280   End If
%o A343280   a = d
%o A343280 End Function
%Y A343280 Cf. A088975, A006370.
%K A343280 nonn,easy
%O A343280 1,1
%A A343280 _Heinz Ebert_, Apr 10 2021