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

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, 403, 532, 707, 936, 1249, 1668, 2220, 2976, 3966, 5278, 7028, 9386, 12531, 16696, 22246, 29622, 39540, 52768, 70395, 93795, 124977, 166619, 222222, 296358, 395213

Offset: 1

Author

Perry Dobbie, Jul 11 2007, Jul 12 2007, Jul 13 2007, Jul 17 2007, Jul 22 2007, Oct 15 2008

Keywords

• nonn

Comments

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

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.

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

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

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

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]

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

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

From Jon E. Schoenfield, Mar 15 2022: (Start)

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

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

(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

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

Examples

			For n=3, the only valid c are:
  c = (3,2,1): (2^3 - 2^2 - 3^1*2^1 - 3^2) / 3^3 = -11/27,
  c = (3,2):   (2^3 - 2^2 - 3^1) / 3^2 = 1/9,
  c = (3):     (2^3 - 2^0) / 3 = 7/3,
  and none are integers so a(3) = 0.
a(9)=2:
  c = (9,5):   (2^9 - 2^5 - 3) / 3 = 53,
  c = (9,5,2): (2^9 - 2^5 - 3*2^2 - 9) / 27 = 17,
  and no other valid c give integer x.
From _Jon E. Schoenfield_, Mar 15 2022: (Start)
The a(12)=6 integers x are { 15, 45, 141, 151, 453, 1365 }, of which only one (151) satisfies x == 1 (mod 6);
the a(13)=7 integers x are { 9, 29, 93, 277, 301, 853, 909 }, of which only one (29) satisfies x == 5 (mod 6);
thus, at n=14, the set of a(14)=8 integers is the union of the three sets
  { 4*15+1 = 61, 4*45+1 = 181, 4*141+1 = 565, 4*151+1 = 605, 4*453+1 = 1813, 4*1365+1 = 5461 },
  { (4*151-1)/3 = 201 }, and
  { (2*29-1)/3 = 19 }. (End)
		

Links

• Perry Dobbie, Collatz representations.
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A060322, A248573.

Programs

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

Extensions

Edited by David Applegate, Oct 16 2008

a(51) from Jon E. Schoenfield, Mar 15 2022