A188545 -id:A188545 - cp's OEIS frontend

A045883 a(n) = ((3n+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

Edward Early

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

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).

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.

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

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

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 *)

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

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

Simpler description from Vladeta Jovovic, Jul 18 2002

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

Original entry on oeis.org

1, 3, 7, 17, 39, 89, 199, 441, 967, 2105, 4551, 9785, 20935, 44601, 94663, 200249, 422343, 888377, 1864135, 3903033, 8155591, 17010233, 35418567, 73633337, 152859079, 316902969, 656175559, 1357090361, 2803659207, 5786275385, 11930464711, 24576757305

Offset: 1

Artur Jasinski, Feb 09 2007

a(n) is the number of runs of strictly increasing parts in all compositions of n. a(3) = 7: (1)(1)(1), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017
From Hugo Pfoertner, Feb 19 2020: (Start)
a(n)/2^(n-2) apparently is the expected number of flips of a fair coin to completion of a game where the player advances by 1 for heads and by 2 for tails, starting at position 0 and repeating to flip until the target n+1 is exactly reached. If the position n (1 below the target) is reached, the player stays at this position and continues to flip the coin and count the flips until he can advance by 1.
The expected number of flips for targets 1, 2, 3,... , found by inversion of the corresponding Markov matrices, is 2, 2, 3, 7/2, 17/4, 39/8, 89/16, 199/32, 441/64, ...
Target 1 needs an expected number of 2 flips and would require a(0) = 1/2.
  n=1, target n+1 = 2: 1 / 2^(1-2) = 2;
  n=2, target n+1 = 3: 3 / 2^(2-2) = 3;
  n=3, target n+1 = 4: 7 / 2^(3-2) = 7/2.
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
W. Bosma, Signed bits and fast exponentiation, J. Th. des Nombres de Bordeaux Vol.13, Fasc. 1, 2001.
Aruna Gabhe, Problem 11623, Am. Math. Monthly 119 (2012) 161.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Cf. A059570, A073371, A127976, A127978, A127979, A127980, A127981, A127982, A127983, A073371, A000337, A172481.

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

A127984:=n->(n/3 + 7/9)*2^(n - 1) + (-1)^n/9; seq(A127984(n), n=1..50); # Wesley Ivan Hurt, Mar 14 2014

Table[(n/3 + 7/9)2^(n - 1) + (-1)^n/9, {n, 50}] (* Artur Jasinski *)
CoefficientList[Series[(1 - 2 x^2) / ((-1 + 2 x)^2 (1 + x)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 15 2017 *)

a(n) = (n/3 + 7/9)*2^(n - 1) + (-1)^n/9.
From R. J. Mathar, Apr 04 2008: (Start)
O.g.f.: -x*(-1+2x^2)/((-1+2x)^2*(1+x)).
a(n) = 3*a(n-1) - 4*a(n-3). (End)
a(n) + a(n+1) = A087447(n+1). - R. J. Mathar, Feb 21 2009
A172481(n) = a(n) + 2^(n-1). Application: Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n+1)*2^(n-1), 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 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: f(n) = (3*n+4 - (-1)^n/2^(n-2))/9, n >= 0, by induction.
a(n) = a(n-1) + a(n-2) + 2^(n-2), n >= 1, with inputs a(-1) = 0, a(0) = 1/2.
(End)
E.g.f.: (2*exp(-x) + exp(2*x)*(7 + 6*x) - 9)/18. - Stefano Spezia, Feb 19 2020

A287012 Number of time intervals that can be measured off with n ropes and a lighter.

Original entry on oeis.org

2, 6, 15, 34, 78, 174, 386, 844, 1837, 3960, 8513, 18238

Offset: 1

Mark Rickert, May 17 2017

Suppose you have n ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end as you see fit. If you're strategic in how you burn the ropes, how many specific lengths of time can you measure? (For example, if you had one rope, you could measure two lengths of time: one hour, by simply burning the entire rope from one end, and half an hour, by burning the rope from both ends and marking when the flames meet.)

In this sequence, the time intervals begin when any rope (or safety fuse, or match cord) begins or stops burning.

			a(2)=6: (i) Generate 1 by burning one rope from one end. (ii) Generate 2 by burning one rope from one end at t=0 and the other afterwards at t=1 from one end. (iii) Generate 1/2 by burning 1 rope from both ends. (iv) Generate 3/2 by burning 1 rope from one end at t=0 then the other from both ends at t=1 (or swapped order). (v) Generate 3/4 by burning one rope at t=0 from both ends, starting the other also at t=0 at one end, and lighting the other's second end at t=1/2 when the first rope's flames have met, so the 2nd rope's flames finish at t=3/4. (vi) Generate 1/4 using the technique for 3/4 and measuring the time between t=1/2 and t=3/4.
For n = 3 the a(3) = 15 solutions are 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1, 9/8, 5/4, 3/2, 7/4, 2, 5/2, 3.

Mark Rickert, Python implementation

Cf. A283075, A188545.

A383922 a(n) = A002104(n) + A002104(n+1) - 1.

Original entry on oeis.org

0, 3, 10, 31, 112, 503, 2786, 18443, 141744, 1237755, 12088266, 130457479, 1541023936, 19769882767, 273671845058, 4065274481939, 64493941507232, 1088226653465139, 19458541429154250, 367527663494842671, 7311506648705326672, 152804399672163086695, 3347034732868985727202, 76675452816691696778843

Offset: 0

Jianing Song, May 15 2025

nonn

Let m_0(x) = -x for x < 0 and (1/2)*m_0(x - m_0(x-1)) for x >= 0, then:
   m_0(1 - 2^(-n)) = 2^(-(n+1)) for n >= -1;
   m_0(2 - 2^(-n)) = 2^(-(2*n+3)) for n >= -2;
   m_0(3 - 2^(-n)) = 2^(-a(n+2)) for n >= -2 (see my link for a proof).
Let F_0 = {x + m_0(x) : x in R}, then the intersection of F_0 and (-oo,n) is well-ordered with order type omega^^n. As a result, F_0 is well-ordered with order type epsilon_0 = omega^^omega. F_0 is a proper subset of F, the set of fusible numbers.
It had been believed that x + m_0(x) was the least fusible greater than x. Junyan Xu points out that this is false. Indeed, let x_n = 17/8 - 1/2^(n+1), c_n = 5/4 - 1/2^(n+1), and d_n = 2 - 1/2^(n-2) + 1/2^(2*n-1) for n >= 0, then
    c_n = (1/2 + (1-1/2^n) + 1)/2,
    d_n = ((1-1/2^(2*n-2)) + d_{n-1} + 1)/2, n >= 1
  are both fusible numbers, hence so is (c_n + d_{n+3} + 1)/2 = 17/8 - 1/2^(n+1) + 1/2^(2*n+6); in other words, the least fusible number greater than x_n is at most x_n + 1/2^(2*n+6). But we have m_0(x_n) = 1/2^(n+8) > 1/2^(2*n+6) for n >= 3.
Junyan Xu gives a conjecture on the recursive formula of m(x), where x + m(x) is the least fusible greater than x. (A188545(n) is -log_2 m(n)). We have m(x) = m_0(x) for x < 33/16 (i.e., F_0 and F coincide on the interval (-oo,33/16]), but they differ for x >= 33/16, even if the intersection of F and (-oo,n) still has order type omega^^n if the conjecture is true. In fact, we have -log_2 m_0(3) = 1541023937, while -log_2 m(3) > 2^^^^^^^^^16 in Knuth's up-arrow notation.

Jianing Song, Notes on A383922
Junyan Xu, Survey on Fusible Numbers, arXiv:1202.5614 [math.CO], 2012.

Cf. A002104, A188545.

a(n) = A002104(n) + A002104(n+1) - 1 \\ See A002104

E.g.f.: exp(x) * (-2*log(1-x) + x/(1-x)).
E.g.f. satisfies (1-x)^2 * (A'(x) - A(x)) = (-2*x+3)*exp(x).
Recurrence: n*a(n) = (n^2+n-1)*a(n-1) - (n^2-1)*a(n-2) + 2*n + 1, a(0) = 0, a(1) = 3.
Recurrence: a(n) = n*a(n-1) - a(n-2) - (n-2)*a(n-3) + 4, a(0) = 0, a(1) = 3, a(2) = 10.
a(n) ~ exp(1)*n!.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A287012 Number of time intervals that can be measured off with n ropes and a lighter.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A383922 a(n) = A002104(n) + A002104(n+1) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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