login
A353063
Irregular triangle T(n,k) read by rows: Coefficients for the ordinary generating function of A014682^n as sum of partial fractions (up to one factor x); ^n means n iterations into the Collatz function.
1
1, 1, 1, 1, -3, 1, -3, 1, 1, 1, 3, -3, -9, 1, 13, -3, 9, 1, 1, 1, 1, 1, -9, 3, -9, -3, -3, -9, -27, 1, -15, 13, 13, -3, -3, 9, -27, 1, -19, 1, 13, 1, 1, 1, 1, 1, 9, -9, -9, 3, 3, -9, 27, -3, 27, -3, -27, -9, -9, -27, -81, 1, 49, -15, -15, 13, 13, 13, 121, -3, 109, -3, 33
OFFSET
1,5
COMMENTS
This sequence is an attempt to compress the complete information about the dynamics of the Collatz function into a single mathematically dense description.
We observe that the length of the rows in this triangle is growing in powers of two. This is true for all variants of the Collatz function of the form: odd->(b*x+c)/2; even->x/2, because after the first iteration into such a function we could write out the result into two rows (example here for (3*x+1)/2):
for odd n: 2, 5, 8,11,14,... progression with 3^1 (b^1) and start with 2,
for even n: 1, 2, 3, 4, 5,... progression with 3^0 (b^0) and start with 1.
After the second iteration we could write the result in four rows, then into eight and so forth. Each row will have a starting value and will have a progression in a power of b. The distribution of powers will be a permutation of A023416. This distribution of powers is reflected in our triangle by the coefficients T(n, 2^(n-1)+1..2^n). The distribution of start values of each such row determines T(n, 1..2^(n-1)) in our triangle.
The Collatz conjecture is true if for each k < 2^n-1, |T(n, 2^n-1 + k)| - (|T(n, k)| + 1)/2 reaches a value of <= 2 for some n big enough.
If this happens A014682^(n-1)(k) < 3 is reached. Alternatively we could say |T(n, 2^n-1 + k)| - (|T(n, k)| + 1)/2 may never be equal for same k but different in n, if it evaluates to a value > 2.
This sequence allows us to develop A014682^n(k) as a sum of sequences s1(k) + s2(k) + ... + sn(k). See the o.g.f. of A014682^n(y)-A014682^(n-1)(y) in the formula section.
FORMULA
The ordinary generating function of A014682^n(y):
x*(n*(1/4)/(1 - x) + 1/(1 - x)^2 + Sum_{k=1..n} ( Sum_{j=1..2^(n-1)} ( T(k, j)/4 / (1 + x^(2^(k-1))) ) + Sum_{m=1..2^(n-1)} ( T(k, 2^(n-1) + m)/2 / (1 + x^(2^(k-1)))^2 ) ) ).
The ordinary generating function of A014682^n(y) - A014682^(n-1)(y):
x*((1/4)/(1 - x) + Sum_{j=1..2^(n-1)} ( T(n, j)/4 / (1 + x^(2^(n-1))) ) + Sum_{m=1..2^(n-1)} ( T(n, 2^(n-1) + m)/2 / (1 + x^(2^(n-1)))^2 )).
T(n, 2^(n-1)) = 1.
T(n, 2^n) = 1.
T(n, 2^n-1) = -(3^(n-1)), for n > 1.
T(n, 2^c*k) = T(n-c, k) for n > c.
T(n, 2^(n-1) + 2*k - 1) = 3*T(n-1, 2^(n-2) + (((3*k + 1)/2) mod 2^(n-2))))*(-1)^floor(((3*k + 1)/2) / (2^(n-2) + (1/2))), for n > 1 and 0 < k <= 2^(n-2).
T(n, 2*k - 1) = -(2*(2-f(k,n))*abs(T(n-1, 2^(n-2) + m(k,n))) + abs(T(n-1, m(k,n))))*signum(T(n, 2^(n-1) + 2*k - 1)), for n > 1 and 0 < k <= 2^(n-2). f(k,n) = floor(((3*k + 1)/2) / (2^(n-2))), m(k,n) = ((3*k + 1)/2) mod 2^(n-2)) with the exception that if m(k,n) = 0, we add 2^(n-2) to the result.
Abs(T(n, k)) = max(2*(A014682^(n-1)(1+2^(n-1)+k) - 2*A014682^(n-1)(1+k)) - 1, 1), for k < 2^(n-1).
Abs(T(n, 2^(n-1) + k - 1)) = A014682^(n-1)(1+2^(n-1)+k) - A014682^(n-1)(1+k), for k < 2^(n-1).
Abs(T(n, 2^(n-1) + k)) = 3^A339694(n-1, k+1), for k < 2^(n-1) - 1.
Sum_{k=1..n} abs(T(n, 2^(n-1) + k)) = 2^(2*(n-1)).
Sum_{k=1..n} log_3(abs(T(n, 2^(n-1) + k)) = A001787(n-1).
n - 1 is the number of k where abs(T(n, 2^(n-1) + k)) = 3 for k = 1..2^(n-1).
A268292(n + 3) is the number of k where abs(T(n, k)) > 12 and abs(T(n, 2^(n-1) + k)) = 9 for k = 1..2^(n-1).
EXAMPLE
Written as an irregular triangle T(n,k):
n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
1 1, 1
2 1, 1, -3, 1
3 -3, 1, 1, 1, 3, -3, -9, 1
4 13, -3, 9, 1, 1, 1, 1, 1, -9, 3, -9, -3, -3, -9,-27, 1
.
The ordinary generating function of A014682(y) is:
x*(
1/4 /(1 - x) | n*(1/4)/(1 - x), n = 1
+ 1/(1 - x)^2
+ 1/4 /(1 + x) | (T(1,1)/4)/(1 + x^(2^(k-1))), k = 1
+ 1/2 /(1 + x)^2) | (T(1,2)/2)/(1 + x^(2^(k-1)))^2 ), k = 1.
The ordinary generating function of A014682(A014682(y)) is:
x*(
1/2 /(1 - x) | n*(1/4)/(1 - x), n = 2
+ 1/(1 - x)^2
+ 1/4 /(1 + x) | (T(1,1)/4)/(1 + x^(2^(k-1))), k = 1
+ 1/2 /(1 + x)^2 | (T(1,2)/2)/(1 + x^(2^(k-1)))^2 ), k = 1
+ (1/4 + 1/4*x)/(1 + x^2) | ((T(2,1) + T(2,2))/4)/(1 + x^(2^(k-1))), k = 2
+ (-3/2 + 1/2*x)/(1 + x^2)^2)| ((T(2,3) + T(2,4))/2)/(1 + x^(2^(k-1)))^2 ), k = 2.
The ordinary generating function of A014682(A014682(A014682(y))) is:
x*(
3/4 /(1 - x)
+ 1/(1 - x)^2
+ 1/4 /(1 + x)
+ 1/2 /(1 + x)^2
+ (1/4 + 1/4*x)/(1 + x^2)
+ (-3/2 + 1/2*x)/(1 + x^2)^2
+ (-3/4 + 1/4*x + 1/4*x^2 + 1/4*x^3)/(1 + x^4)
+ (3/2 - 3/2*x - 9/2*x^2 + 1/2*x^3)/(1 + x^4)^2).
PROG
(MATLAB)
function a = A353063( max_n )
a = cell(0);
a{1} = [1 1];
for n = 2:max_n
row = zeros(1, 2^n);
% T(n, 2*k) = T(n-1, k)
row(2.*[1:2^(n-1)]) = a{n-1};
j = 2.*[1:2^(n-2)]-1;
m = mod((j*3+1)/2, 2^(n-2));
f = floor(((j*3+1)/2)/2^(n-2));
f2 = f; f2(m==0) = f(m==0)-1;
% T(n, 2^(n-1) + 2*k - 1) = 3*T(n-1, 2^(n-2)
% + (((3*k + 1)/2) mod 2^(n-2))))
% *(-1)^floor(((3*k + 1)/2) / (2^(n-2) + (1/2)))
row(2^(n-1) + j) = 3*a{n-1}(2^(n-2) + m).*(-1).^f2;
m(m==0) = 2^(n-2);
% T(n, 2*k - 1) = -(2*(2-f(k))*abs(T(n-1, 2^(n-2) + m(k)))
% + abs(T(n-1, m(k))))*signum(T(n, 2^(n-1) + 2*k - 1))
row(j) = (2*(2-f).*abs(a{n-1}(2^(n-2) + m))+abs(a{n-1}(m)))...
.*(-1*sign(row(2^(n-1) + j)));
a{n} = row;
end
end
CROSSREFS
KEYWORD
sign,tabf
AUTHOR
Thomas Scheuerle, Apr 21 2022
STATUS
approved