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

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

Offset: 0

Author

Edward Early

Keywords

• easy
• nonn

Comments

Without the initial zero, PSumSIGN transform of A001787. - Michael Somos, Jul 10 2003

Number of rises (drops) in the compositions of n+2 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 i-th 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^(n-i) = 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 dimension-regular generalized recursive circulant graph (commonly known as multiplicative circulant graph) of order 2^n. - John Rafael M. Antalan, Sep 25 2020

Total sum over all compositions of n of the absolute differences between consecutive parts, assuming an initial part 0. - Alois P. Heinz, Apr 30 2025

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 dimension-regular generalized recursive circulant graph of order power of two and three, arXiv:2009.11608[math.CO], 2020.
• M. Archibald, A. Blecher, A. Knopfmacher, and 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.
• Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
• Silvia Heubach and Toufik 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, 145--153. 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 Balanced-Power Product Recurrence, Fibonacci Quart. 54 (2016), no. 3, 242-246. See Remark 2.2 p. 244.
• Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397-405.
• Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Crossrefs

Partial sums of A059570, bisection: A014916.

Row sums of triangle A094953.

Cf. A059260, A127984.

Cf. A000079, A001045, A001787, A045883, A049260, A113861, A140960, A188545.

Cf. A238343, A238344.

Programs

Magma

[((3*n+1)*2^n-(-1)^n)/9: n in [0..35]]; // Vincenzo Librandi, Jun 15 2017

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(1-x)/(1-x-2x^2)/(1-2x);b=x^2/(1-2x)^2;Drop[CoefficientList[Series[(b-a)/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] (* Jean-François Alcover, Sep 27 2017 *)

PARI

{a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};

Formula

G.f.: x/((1+x)*(1-2*x)^2).

a(n) = 3*a(n-1) - 4*a(n-3).

Convolution of A001045 and A000079. G.f.: x/((1-2*x)(1-x-2*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(n-1), f(n-2)), 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(n-1) + 2*a(n-2) + 2^(n-1), n >= 0, with input a(-2) = 1/4 and a(-1) = 0. See also A127984. (End)

E.g.f.: (exp(2*x)*(1 + 6*x) - cosh(x) + sinh(x))/9. - Stefano Spezia, Apr 09 2025

a(n) = Sum_{k=0..n+2} k * A238343(n+2,k). - Alois P. Heinz, Apr 30 2025

Extensions

Simpler description from Vladeta Jovovic, Jul 18 2002