cp's OEIS Frontend

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

%I A045883 #111 Apr 30 2025 14:58:23
%S A045883 0,1,3,9,23,57,135,313,711,1593,3527,7737,16839,36409,78279,167481,
%T A045883 356807,757305,1601991,3378745,7107015,14913081,31224263,65244729,
%U A045883 136081863,283348537,589066695,1222872633,2535223751,5249404473,10856722887,22429273657,46290203079
%N A045883 a(n) = ((3*n+1)*2^n - (-1)^n)/9.
%C A045883 Without the initial zero, PSumSIGN transform of A001787. - _Michael Somos_, Jul 10 2003
%C A045883 Number of rises (drops) in the compositions of n+2 with parts in N.
%C A045883 From _Michel Lagneau_, Jan 13 2012: (Start)
%C A045883 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
%C A045883 a(1) = sum of the digits "1" of T(i,j), i = 1..2^1 and j = 1;
%C A045883 a(2) = sum of the digits "1" of T(i,j), i = 1..2^2 and j = 1..2;
%C A045883 a(3) = sum of the digits "1" of T(i,j), i = 1..2^3 and j = 1..3;
%C A045883 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).
%C A045883 The number of digits "0" equals A113861(n) = n*2^n - a(n) because n and 2^n are the dimensions of each array.
%C A045883 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.
%C A045883 Conclusion:
%C A045883 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...).
%C A045883 2. For each array of dimension n X 2^n, the radio r tends towards 2.
%C A045883 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.
%C A045883 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)
%C A045883 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
%C A045883 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
%H A045883 Vincenzo Librandi, <a href="/A045883/b045883.txt">Table of n, a(n) for n = 0..1000</a>
%H A045883 John Rafael M. Antalan and Francis Joseph H. Campeña, <a href="https://arxiv.org/abs/2009.11608">Distance eigenvalues and forwarding indices of dimension-regular generalized recursive circulant graph of order power of two and three</a>, arXiv:2009.11608[math.CO], 2020.
%H A045883 M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
%H A045883 Roland Bacher, <a href="http://arxiv.org/abs/1509.09054">Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle</a>, arXiv:1509.09054 [math.CO], 2015.
%H A045883 Tomislav Došlić and Biserka Kolarec, <a href="https://doi.org/10.3390/math13071179">On Log-Definite Tempered Combinatorial Sequences</a>, Mathematics (2025) Vol. 13, Iss. 7, 1179.
%H A045883 Silvia Heubach and Toufik Mansour, <a href="https://arxiv.org/abs/math/0310197">Counting rises, levels and drops in compositions</a>, arXiv:math/0310197 [math.CO], 2003.
%H A045883 F. K. Hwang, <a href="https://doi.org/10.1137/0605016">Three versions of a group testing game</a>, 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
%H A045883 Peter J. Larcombe and Eric J. Fennessey, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/54-3/LarcombeFennessey02282016.pdf">On a Scaled Balanced-Power Product Recurrence</a>, Fibonacci Quart. 54 (2016), no. 3, 242-246. See Remark 2.2 p. 244.
%H A045883 Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, <a href="http://pjm.ppu.edu/sites/default/files/papers/PJM_April2018_397to405.pdf">On two derivative sequences from scaled geometric mean sequence terms</a>, Palestine Journal of Mathematics (2018) Vol. 7(2), 397-405.
%H A045883 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-4).
%F A045883 G.f.: x/((1+x)*(1-2*x)^2).
%F A045883 a(n) = 3*a(n-1) - 4*a(n-3).
%F A045883 Convolution of A001045 and A000079. G.f.: x/((1-2*x)(1-x-2*x^2)). - _Paul Barry_, May 21 2004
%F A045883 Starting with "1" = triangle A049260 * the odd integers as a vector. - _Gary W. Adamson_, Mar 06 2012
%F A045883 a(n) = A140960(n)/2. - _J. M. Bergot_, May 21 2013
%F A045883 From _Wolfdieter Lang_, Jun 14 2017: (Start)
%F A045883 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.
%F A045883 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)
%F A045883 E.g.f.: (exp(2*x)*(1 + 6*x) - cosh(x) + sinh(x))/9. - _Stefano Spezia_, Apr 09 2025
%F A045883 a(n) = Sum_{k=0..n+2} k * A238343(n+2,k). - _Alois P. Heinz_, Apr 30 2025
%p A045883 A045883:=n->((3*n+1)*2^n-(-1)^n)/9; seq(A045883(n), n=0..30); # _Wesley Ivan Hurt_, Mar 21 2014
%t A045883 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 *)
%t A045883 CoefficientList[Series[x / ((1 + x) (1 - 2 x)^2), {x, 0, 33}], x] (* _Vincenzo Librandi_, Jun 15 2017 *)
%t A045883 LinearRecurrence[{3, 0, -4}, {0, 1, 3}, 33] (* _Jean-François Alcover_, Sep 27 2017 *)
%o A045883 (PARI) {a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};
%o A045883 (Magma) [((3*n+1)*2^n-(-1)^n)/9: n in [0..35]]; // _Vincenzo Librandi_, Jun 15 2017
%Y A045883 Partial sums of A059570, bisection: A014916.
%Y A045883 Row sums of triangle A094953.
%Y A045883 Cf. A059260, A127984.
%Y A045883 Cf. A000079, A001045, A001787, A045883, A049260, A113861, A140960, A188545.
%Y A045883 Cf. A238343, A238344.
%K A045883 easy,nonn
%O A045883 0,3
%A A045883 _Edward Early_
%E A045883 Simpler description from _Vladeta Jovovic_, Jul 18 2002