|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
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)
|
|
|
LINKS
|
|
|
|
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.
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
