

A045883


a(n) = ((3*n+1)*2^n  (1)^n)/9.


27



0, 1, 3, 9, 23, 57, 135, 313, 711, 1593, 3527, 7737, 16839, 36409, 78279, 167481, 356807, 757305, 1601991, 3378745, 7107015, 14913081, 31224263, 65244729, 136081863, 283348537, 589066695, 1222872633, 2535223751, 5249404473, 10856722887, 22429273657, 46290203079
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Without the initial zero, PSumSIGN transform of A001787.  Michael Somos, Jul 10 2003
Number of rises (drops) in the compositions of n2 with parts in N.
From Michel Lagneau, Jan 13 2012: (Start)
This sequence is connected with the Collatz problem. We consider the array T(i,j) where the ith row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 > 3 > 10 >5 > 16 >8 > 4 > 2 > 1 > 4 > 2 > 1 > 4>2> 1 ... and T(6,j) = [0,1,0,1,0,0,0,0,1,0,0,1,...,1,0,0,1,...]. Now, we consider the sum of the digits 1 of each array T(i,j), where
a(1) = sum of the digits "1" of T(i,j), i = 1..2^1 and j = 1;
a(2) = sum of the digits "1" of T(i,j), i = 1..2^2 and j = 1..2;
a(3) = sum of the digits "1" of T(i,j), i = 1..2^3 and j = 1..3;
a(n) = Sum_{i=1..2^n}(Sum_{j=1..n} T(i,j)) = Sum_{i=1..n} A001045(n)*2^(ni) = convolution of A001045 and A000079 (see the formula below).
The number of digits "0" equals A113861(n) = n*2^n  a(n) because n and 2^n are the dimensions of each array.
An important result is that the ratio r = A113861(n) / A045883(n) tends towards 2 when n tends towards infinity. In other words, when the array tends towards infinity, the ratio r = (number of divisions by 2) / (number of multiplications by 3) tends towards 2, even if there exists divergent trajectories. That is the problem! For each possible divergent infinite trajectory, r < 2 even though the global ratio r is 2.
Conclusion:
1. For each number n with a convergent trajectory T(n,k), k = 1..infinity, or for each row of the array T(i,j), the ratio r tends towards 2 (the proof is easy because the trajectory becomes periodic from a certain index 1001001001...).
2. For each array of dimension n X 2^n, the radio r tends towards 2.
3. If there exists a number n such that the trajectory is divergent, this trajectory is random and r tends towards a real x such that 1 < = r < = x < 2.
4. In order to establish a proof of the Collatz problem from this considerations (if that is possible), it is necessary to prove that a ratio < 2 for an infinite row (or several rows) of an infinite array T(i,j) is incompatible with r = 2, the exact ratio for this array. (End)
a(n) is the distance spectral radius of the dimensionregular generalized recursive circulant graph (commonly known as multiplicative circulant graph) of order 2^n.  John Rafael M. Antalan, Sep 25 2020


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John Rafael M. Antalan and Francis Joseph H. Campeña, Distance eigenvalues and forwarding indices of dimensionregular generalized recursive circulant graph of order power of two and three, arXiv:2009.11608[math.CO], 2020.
M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
F. K. Hwang, Three versions of a group testing game, SIAM J. Algebraic Discrete Methods 5 (1984), no. 2, 145153. MR0745434(85d:90120). See p. 151, f(n) (but divide by 2).  N. J. A. Sloane, Apr 13 2014
Peter J. Larcombe and Eric J. Fennessey, On a Scaled BalancedPower Product Recurrence, Fibonacci Quart. 54 (2016), no. 3, 242246. See Remark 2.2 p. 244.
Peter J. Larcombe, Julius Fergy T. Rabago, Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397405.
Index entries for linear recurrences with constant coefficients, signature (3,0,4).


FORMULA

G.f.: x/((1+x)*(12*x)^2).
a(n) = 3*a(n1)  4*a(n3).
Convolution of A001045 and A000079. G.f.: x*((12*x)(1x2*x^2)).  Paul Barry, May 21 2004
Starting with "1" = triangle A049260 * the odd integers as a vector.  Gary W. Adamson, Mar 06 2012
a(n) = A140960(n)/2.  J. M. Bergot, May 21 2013
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n)*2^n, where f(n) is a rational Fibonacci type sequence based on fuse(a,b) = (a+b+1)/2 with f(0) = 0, f(1) = 1/2 and f(n) = fuse(f(n1), f(n2)), for n >= 2. For fuse(a,b) see the Jeff Erickson link under A188545. Proof with f(n) = (3*n+1  (1)^n/2^n)/9, n >= 0, by induction.
a(n) = a(n1) + 2*a(n2) + 2^(n1), n >= 0, with input a(2) = 1/4 and a(1) = 0. See also A127984. (End)


MAPLE

A045883:=n>((3*n+1)*2^n(1)^n)/9; seq(A045883(n), n=0..30); # Wesley Ivan Hurt, Mar 21 2014


MATHEMATICA

nn=31; a=x^2(1x)/(1x2x^2)/(12x); b=x^2/(12x)^2; Drop[CoefficientList[Series[(ba)/2, {x, 0, nn}], x], 2] (* Geoffrey Critzer, Mar 21 2014 *)
CoefficientList[Series[x / ((1 + x) (1  2 x)^2), {x, 0, 33}], x] (* Vincenzo Librandi, Jun 15 2017 *)
LinearRecurrence[{3, 0, 4}, {0, 1, 3}, 33] (* JeanFrançois Alcover, Sep 27 2017 *)


PROG

(PARI) {a(n) = if( n<1, 0, ((3*n + 1)*2^n  (1)^n) / 9)};
(Magma) [((3*n+1)*2^n(1)^n)/9: n in [0..35]]; // Vincenzo Librandi, Jun 15 2017


CROSSREFS

Partial sums of A059570, bisection: A014916.
Row sums of triangle A094953.
Cf. A059260, A127984.
Sequence in context: A147126 A147212 A341029 * A292329 A133654 A193695
Adjacent sequences: A045880 A045881 A045882 * A045884 A045885 A045886


KEYWORD

easy,nonn


AUTHOR

Edward Early


EXTENSIONS

Simpler description from Vladeta Jovovic, Jul 18 2002


STATUS

approved



