%I #31 Nov 13 2024 14:11:04

%S 0,1,0,1,1,1,1,1,2,4,6,6,7,8,11,18,23,29,39,52,71,99,124,160,220,302,

%T 403,532,707,936,1249,1668,2220,2976,3966,5278,7028,9386,12531,16696,

%U 22246,29622,39540,52768,70395,93795,124977,166619,222222,296358,395213

%N a(n) is the number of integers x that can be written x = (2^c(1) - 2^c(2) - 3*2^c(3) - 3^2*2^c(4) - ... - 3^(m-2)*2^c(m) - 3^(m-1)) / 3^m for integers c(1), c(2), ..., c(m) such that n = c(1) > c(2) > ... > c(m) > 0 and c(1) - c(2) != 2 if m >= 2.

%C For m = 1, the expression for x becomes x = (2^c(1) - 1) / 3.

%C Also the number of odd x with stopping time n for the Collatz or 3x+1 problem where x->x/2 if x is even, x->(3x+1)/2 if x is odd (see A060322), except that 1 is counted as having stopping time 2 instead of 0.

%C Equivalently, a(n) is the number of x == 2 (mod 3) with stopping time n-1.

%C The number of possible c(1),...,c(m) is 2^(n-1) - 2^(n-3); most do not yield integer x.

%C n-c(m), n-c(m-1), ..., n-c(2) are the stopping times of the odd integers in the Collatz trajectory of x.

%C For n > 4, a(n) = a(n-2) + a(n-2):(x is 1 mod 6) + a(n-1):(x is 5 mod 6). [I.e., for n > 4, a(n) = a(n-2) + (number of values of x counted in a(n-2) such that x == 1 (mod 6)) + (number of values of x counted in a(n-1) such that x == 5 (mod 6)). - _Jon E. Schoenfield_, Mar 14 2022]

%C It is conjectured that lim_{n->oo} a(n)/a(n-1) = 4/3.

%C With a(2) = 0 this is the first difference sequence of A060322, the row length sequence of A248573 (Collatz-Terras tree). - _Wolfdieter Lang_, May 04 2015

%C From _Jon E. Schoenfield_, Mar 15 2022: (Start)

%C For n > 4, the set of integers counted in a(n) is the union of three disjoint sets:

%C (1) the set of integers 4*x+1 obtained using all integers x counted by a(n-2),

%C (2) the set of integers (4*x-1)/3 obtained using only those integers x counted by a(n-2) that satisfy x == 1 (mod 6), and

%C (3) the set of integers (2*x-1)/3 obtained using only those integers x counted by a(n-1) that satisfy x == 5 (mod 6). (See Example.) (End)

%H Perry Dobbie, <a href="http://sites.google.com/site/3nplus1/home">Collatz representations</a>.

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

%e For n=3, the only valid c are:

%e c = (3,2,1): (2^3 - 2^2 - 3^1*2^1 - 3^2) / 3^3 = -11/27,

%e c = (3,2): (2^3 - 2^2 - 3^1) / 3^2 = 1/9,

%e c = (3): (2^3 - 2^0) / 3 = 7/3,

%e and none are integers so a(3) = 0.

%e a(9)=2:

%e c = (9,5): (2^9 - 2^5 - 3) / 3 = 53,

%e c = (9,5,2): (2^9 - 2^5 - 3*2^2 - 9) / 27 = 17,

%e and no other valid c give integer x.

%e From _Jon E. Schoenfield_, Mar 15 2022: (Start)

%e The a(12)=6 integers x are { 15, 45, 141, 151, 453, 1365 }, of which only one (151) satisfies x == 1 (mod 6);

%e the a(13)=7 integers x are { 9, 29, 93, 277, 301, 853, 909 }, of which only one (29) satisfies x == 5 (mod 6);

%e thus, at n=14, the set of a(14)=8 integers is the union of the three sets

%e { 4*15+1 = 61, 4*45+1 = 181, 4*141+1 = 565, 4*151+1 = 605, 4*453+1 = 1813, 4*1365+1 = 5461 },

%e { (4*151-1)/3 = 201 }, and

%e { (2*29-1)/3 = 19 }. (End)

%o (Magma) a:=[0,1,0,1]; Y:=[]; X:=[5]; for n in [5..51] do Z:=Y; Y:=X; X:=[]; for x in Z do X[#X+1]:=4*x+1; end for; for x in Z do if x mod 6 eq 1 then X[#X+1]:=(4*x-1) div 3; end if; end for; for x in Y do if x mod 6 eq 5 then X[#X+1]:=(2*x-1) div 3; end if; end for; X:=Sort(X); a[n]:=#X; end for; a; // _Jon E. Schoenfield_, Mar 15 2022

%Y Cf. A060322, A248573.

%K nonn

%O 1,9

%A _Perry Dobbie_, Jul 11 2007, Jul 12 2007, Jul 13 2007, Jul 17 2007, Jul 22 2007, Oct 15 2008

%E Edited by _David Applegate_, Oct 16 2008

%E a(51) from _Jon E. Schoenfield_, Mar 15 2022