login
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.
5
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,9
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)
EXAMPLE
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)
PROG
(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
CROSSREFS
Sequence in context: A211376 A278249 A339743 * A114218 A133691 A111973
KEYWORD
nonn
AUTHOR
Perry Dobbie (pdobbie(AT)rogers.com), Jul 11 2007, Jul 12 2007, Jul 13 2007, Jul 17 2007, Jul 22 2007, Oct 15 2008
EXTENSIONS
Edited by David Applegate, Oct 16 2008
a(51) from Jon E. Schoenfield, Mar 15 2022
STATUS
approved