A020988 -id:A020988 - cp's OEIS frontend

A073724 a(n) = (4^(n+1) + 6n + 5)/9.

1, 3, 9, 31, 117, 459, 1825, 7287, 29133, 116515, 466041, 1864143, 7456549, 29826171, 119304657, 477218599, 1908874365, 7635497427, 30541989673, 122167958655, 488671834581, 1954687338283, 7818749353089, 31274997412311

Offset: 0

Wouter Meeussen, Sep 01 2002

a(n) is the number of times a disk is moved from peg 1 to peg 2 during a move of a tower of 2n or (2n-1) disks from peg 1 to peg 2 ("Tower of Hanoi" problem). Binomial transform of A025579.

An approximation to A091841.

			Moving a tower of 4 disks = 2^4 - 1 moves, coded {1,0,5,1,2,3,1,0,5,4,2,5,1,0,5}. The move from peg 1 to peg 2 has code "0" and this occurs 3 times. For 3 disks we also find 3 zeros in {0,1,3,0,4,5,0}. Hence a(2)=3. The coding corresponds to the rank of the permutation {'from peg' 1, 'to peg' 2, 'by peg' 3} or {1,2,3} with rank 0.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
Hacène Belbachir and El-Mehdi Mehiri, Enumerating moves in the optimal solution of the Tower of Hanoi, arXiv:2210.08657 [math.CO], 2022.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
Index entries for sequences related to Gijswijt's sequence
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).
Index entries for sequences related to Towers of Hanoi

Cf. A001045, A002450, A007583, A020988, A025579, A047849 (first differences), A090822, A091841.

[(4^(n+1)+6*n+5)/9: n in [0..40] ]; // Vincenzo Librandi, Apr 28 2011

Mathematica
```
Table[(4^(n+1)+6n+5)/9, {n, 0, 24}]
```
PARI
```
a(n)=(4*4^n+6*n+5)/9
```

a(n)=polcoeff((1-3*x)/(1-4*x)/(1-x)^2+x*O(x^n),n)

G.f.: (1-3*x)/((1-4*x)*(1-x)^2).
a(n) = Sum_{k=0..n} A047849(k). - L. Edson Jeffery, May 01 2021
From Elmo R. Oliveira, Dec 11 2023: (Start)
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>2.
E.g.f.: (1/9)*(4*(exp(4*x)) + 6*x*exp(x) + 5*exp(x)). (End)

A173732 a(n) = (A016957(n)/2^A007814(A016957(n)) - 1)/2, with A016957(n) = 6*n+4 and A007814(n) the 2-adic valuation of n.

Original entry on oeis.org

0, 2, 0, 5, 3, 8, 2, 11, 6, 14, 0, 17, 9, 20, 5, 23, 12, 26, 3, 29, 15, 32, 8, 35, 18, 38, 2, 41, 21, 44, 11, 47, 24, 50, 6, 53, 27, 56, 14, 59, 30, 62, 0, 65, 33, 68, 17, 71, 36, 74, 9, 77, 39, 80, 20, 83, 42, 86, 5, 89, 45, 92, 23, 95, 48, 98, 12, 101, 51, 104, 26, 107, 54, 110, 3

Offset: 0

Howard A. Landman, Feb 22 2010

All positive integers eventually reach 1 in the Collatz problem iff all nonnegative integers eventually reach 0 with repeated application of this map, i.e., if for all n, the sequence n, a(n), a(a(n)), a(a(a(n))), ... eventually hits 0.
0 <= a(n) <= (3n+1)/2, with the upper bound being achieved for all odd n.
The positions of the zeros are given by A020988 = (2/3)*(4^n-1). This is because if n = (2/3)*(4^k-1), then m = 2n+1 = (1/3)*(4^(k+1)-1), and 3m+1 = 4^(k+1) is a power of 4. - Howard A. Landman, Mar 14 2010
Subsequence of A025480, a(n) = A025480(3n+1), i.e., A025480 = 0,[0],1,0,[2],1,3,[0],4,2,[5],1,6,[3],7,0,[8],4,9,[2],10,5,[11],1,12,[6],13,3,[14],... with elements of A173732 in brackets. - Paul Tarau, Mar 21 2010
A204418(a(n)) = 1. - Reinhard Zumkeller, Apr 29 2012
Original name: "A compression of the Collatz (or 3x+1) sequence considered as a map from odd numbers to odd numbers." - Michael De Vlieger, Oct 07 2019

			a(0) = 0 because 2n+1 = 1 (the first odd number), 3*1 + 1 = 4, dividing all powers of 2 out of 4 leaves 1, and (1-1)/2 = 0.
a(1) = 2 because 2n+1 = 3, 3*3 + 1 = 10, dividing all powers of 2 out of 10 leaves 5, and (5-1)/2 = 2.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics,Collatz Problem.
Wikipedia, Collatz conjecture.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A006370, A007494 (range), A007814, A016957, A020988, A025480, A075677.

#include  main() { int k,m,n; for (k = 0; ; k++) { n = 2*k + 1 ; m = 3*n + 1 ; while (!(m & 1)) { m >>= 1 ; } printf("%d,",((m - 1) >> 1)); } }

a173732 n = a173732_list !! n
a173732_list = f $ tail a025480_list where f (x :  :  : xs) = x : f xs
-- Reinhard Zumkeller, Apr 29 2012

Array[(#/2^IntegerExponent[#, 2] - 1)/2 &[6 # + 4] &, 75, 0] (* Michael De Vlieger, Oct 06 2019 *)

odd(n) = n >> valuation(n, 2);
a(n) = (odd(6*n+4) - 1)/2; \\ Amiram Eldar, Aug 26 2024

From Amiram Eldar, Aug 26 2024: (Start)
a(n) = (A075677(n+1) - 1)/2.
Sum_{k=1..n} a(k) ~ n^2 / 2. (End)

Name changed by Michael De Vlieger, Oct 07 2019

A080675 a(n) = (5*4^n - 8)/6.

Original entry on oeis.org

2, 12, 52, 212, 852, 3412, 13652, 54612, 218452, 873812, 3495252, 13981012, 55924052, 223696212, 894784852, 3579139412, 14316557652, 57266230612, 229064922452, 916259689812, 3665038759252, 14660155037012, 58640620148052, 234562480592212, 938249922368852

Offset: 1

N. J. A. Sloane, Mar 02 2003

These numbers have a simple binary pattern: 10,1100,110100,11010100,1101010100, ... i.e., the n-th term has a binary expansion 1(10){n-1}0, that is, there are n-1 10's between the most significant 1 and the least significant 0.

Vincenzo Librandi, Table of n, a(n) for n = 1..170
Andrei Asinowski, Cyril Banderier, Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
Index entries for linear recurrences with constant coefficients, signature (5,-4).

a(n) = A072197(n-1) - 1 = A014486(|A106191(n)|). a(n) = A079946(A020988(n-2)) for n>=2. Cf. also A122229.

[(5*4^n-8)/6: n in [1..40] ]; // Vincenzo Librandi, Apr 28 2011

(5*4^Range[30]-8)/6 (* or *) LinearRecurrence[{5,-4},{2,12},30] (* Harvey P. Dale, Oct 16 2012 *)

a(n)=(5*4^n-8)/6 \\ Charles R Greathouse IV, Oct 07 2015

a(1)=2, a(2)=12, a(n)=5*a(n-1)-4*a(n-2). - Harvey P. Dale, Oct 16 2012

Further comments added by Antti Karttunen, Sep 14 2006

A083597 a(n) = (7*4^n - 4)/3.

Original entry on oeis.org

1, 8, 36, 148, 596, 2388, 9556, 38228, 152916, 611668, 2446676, 9786708, 39146836, 156587348, 626349396, 2505397588, 10021590356, 40086361428, 160345445716, 641381782868, 2565527131476, 10262108525908, 41048434103636

Offset: 0

Paul Barry, May 02 2003

Binomial transform of A082541.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4).

[(7*4^n-4)/3: n in [0..25]]; // Vincenzo Librandi, Jul 24 2011

(7*4^Range[0,25]-4)/3 (* or *) LinearRecurrence[{5,-4},{1,8},26] (* Harvey P. Dale, Jul 23 2011 *)
CoefficientList[Series[(1 + 3 x)/((1 - 4 x) (1 - x)), {x, 0, 22}], x] (* Michael De Vlieger, Mar 03 2017 *)

a(n)=(7*4^n-4)/3 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = (7*4^n-4)/3.
G.f.: (1+3*x)/((1-4*x)*(1-x)).
E.g.f.: (7*exp(4*x)-4*exp(x))/3.
a(n) = 4*a(n-1) + 4, n > 0. - Gary Detlefs, Jun 23 2010
a(0)=1, a(1)=8, a(n) = 5*a(n-1) - 4*a(n-2). - Harvey P. Dale, Jul 23 2011
a(n) = A020988(n) + A020989(n), n >= 0. - Yosu Yurramendi, Mar 03 2017

A167030 a(n) = (2^n - (-1)^n - 3)/3.

Original entry on oeis.org

-1, 0, 0, 2, 4, 10, 20, 42, 84, 170, 340, 682, 1364, 2730, 5460, 10922, 21844, 43690, 87380, 174762, 349524, 699050, 1398100, 2796202, 5592404, 11184810, 22369620, 44739242, 89478484, 178956970, 357913940, 715827882

Offset: 0

Paul Curtz, Oct 27 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..240 from Vincenzo Librandi)
Nicolas Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, arXiv preprint arXiv:1711.10906 [cs.DM], 2017.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

A026644 is an essentially identical sequence.

Cf. A001045, A153772, A047849, A020988, A000975.

[(2^n-(-1)^n)/3 -1: n in [0..40] ]; // Vincenzo Librandi, Apr 28 2011

f[n_] := (2^n - (-1)^n - 3)/3; Array[f, 32, 0]

a(n)=(2^n-(-1)^n)/3-1 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = A001045(n) - 1.
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
G.f.: (1 - 2*x - x^2)/((x^2 - 1)*(1-2*x)).
2*a(n) = A153772(n+1).
a(2n+1) - a(2n) = A047849(n).
a(2n+1) = A020988(n); a(2n+2) = 2*A020988(n).
a(n+2) = 2*A000975(n).
a(2n+2) = a(2n) + 2^(2n).
E.g.f.: (1/3)*(exp(2*x) - 3*exp(x) - exp(-x)). - G. C. Greubel, May 30 2016

Edited by R. J. Mathar, Dec 17 2010

A211016 Triangle read by rows: T(n,k) = number of squares and rectangles of area 2^(k-1) after 2^n stages in the toothpick structure of A139250, n>=1, k>=1, assuming the toothpicks have length 2.

Original entry on oeis.org

0, 0, 4, 8, 12, 4, 40, 52, 12, 4, 168, 212, 52, 12, 4, 680, 852, 212, 52, 12, 4, 2728, 3412, 852, 212, 52, 12, 4, 10920, 13652, 3412, 852, 212, 52, 12, 4, 43688, 54612, 13652, 3412, 852, 212, 52, 12, 4, 174760, 218452, 54612, 13652, 3412, 852, 212, 52, 12, 4

Offset: 1

Omar E. Pol, Sep 18 2012

All internal regions in the toothpick structure are squares and rectangles.

			For n = 5 in the toothpick structure after 2^5 stages we have that:
T(5,1) = 168 is the number of squares of size 1 X 1.
T(5,2) = 212 is the number of rectangles of size 1 X 2.
T(5,3) = 52 is the total number of squares of size 2 X 2 and of rectangles of size 1 X 4.
T(5,4) = 12 is the number of rectangles of size 2 X 4.
T(5,5) = 4 is the number of rectangles of size 2 X 8.
Triangle begins:
       0;
       0,      4;
       8,     12,     4;
      40,     52,    12,     4;
     168,    212,    52,    12,    4;
     680,    852,   212,    52,   12,   4;
    2728,   3412,   852,   212,   52,  12,   4;
   10920,  13652,  3412,   852,  212,  52,  12,  4;
   43688,  54612, 13652,  3412,  852, 212,  52, 12,  4;
  174760, 218452, 54612, 13652, 3412, 852, 212, 52, 12, 4;

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Row sums give 0 together with A145655.

Cf. A020988, A072197, A080675, A139250, A160124, A211008, A211017, A211018, A211019.

T(n,k) = A211008(2^n,k) = 4*A211019(n,k).

T(n,1) = 4*A020988(n-2), n>=2.

A048329 Numbers that are repdigits in base 4.

Original entry on oeis.org

0, 1, 2, 3, 5, 10, 15, 21, 42, 63, 85, 170, 255, 341, 682, 1023, 1365, 2730, 4095, 5461, 10922, 16383, 21845, 43690, 65535, 87381, 174762, 262143, 349525, 699050, 1048575, 1398101, 2796202, 4194303, 5592405, 11184810, 16777215, 22369621, 44739242, 67108863

Offset: 0

Patrick De Geest, Feb 15 1999

			10_10 = 22_4, 15_10 = 33_4, 5461_10 = 1111111_4.

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Eric Weisstein's World of Mathematics, Repdigit.
Index entries for linear recurrences with constant coefficients, signature (0,0,5,0,0,-4).

Cf. A010785, A033017, A028987, A028988, A248721.

Base 4 repdigits 1,2,3 (trisections): A002450, A020988, A024036.

[0] cat  [k:k in [1..10^7]| #Set(Intseq(k,4)) eq 1]; // Marius A. Burtea, Oct 11 2019

a:= n-> (1+irem(n+2, 3))*(4^iquo(n+2,3)-1)/3:
seq(a(n), n = 0..45);

Union[Flatten[Table[FromDigits[PadRight[{}, n, d], 4], {n, 0, 40}, {d, 3}]]](* Vincenzo Librandi, Feb 06 2014 *)
LinearRecurrence[{0,0,5,0,0,-4},{0,1,2,3,5,10},40] (* Harvey P. Dale, Jul 11 2023 *)

G.f.: x*(1+2*x+3*x^2) / ( (x-1)*(4*x^3-1)*(1+x+x^2) ) with a(n) = 5*a(n-3) - 4*a(n-6). - R. J. Mathar, Mar 15 2015

Sum_{n>=1} 1/a(n) = (11/2) * A248721 = 2.31603727318383077512... - Amiram Eldar, Jan 21 2022

A077864 Expansion of (1-x)^(-1)/(1-x-2*x^2-x^3).

Original entry on oeis.org

1, 2, 5, 11, 24, 52, 112, 241, 518, 1113, 2391, 5136, 11032, 23696, 50897, 109322, 234813, 504355, 1083304, 2326828, 4997792, 10734753, 23057166, 49524465, 106373551, 228479648, 490751216, 1054084064, 2264066145, 4862985490, 10445201845, 22435238971, 48188628152

Offset: 0

N. J. A. Sloane, Nov 17 2002

Diagonal sums of triangle using cumulative sums of odd-indexed rows of Pascal's triangle (cf. A020988). - Paul Barry, May 18 2003

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2, 1, -1, -1).

a := n -> (Matrix([[1,1,0,0], [2,0,1,0], [1,0,0,0], [1,0,0,1]])^(n+1))[4,1]; seq(a(n), n=0..50);  # Alois P. Heinz, Jul 24 2008

CoefficientList[Series[(1-x)^(-1)/(1-x-2x^2-x^3),{x,0,40}],x] (* or *) LinearRecurrence[{2,1,-1,-1},{1,2,5,11},40] (* Harvey P. Dale, Oct 08 2014 *)

Vec((1-x)^(-1)/(1-x-2*x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

a(0)=1, a(1)=2, a(2)=5, a(3)=11, a(n)=2*a(n-1)+a(n-2)-a(n-3)-a(n-4) for n>3. - Philippe Deléham, Oct 25 2006
a(n) = term (4,1) in the 4x4 matrix [1,1,0,0; 2,0,1,0; 1,0,0,0; 1,0,0,1]^(n+1). - Alois P. Heinz, Jul 24 2008
Conjecture: a(n) = Sum_{j=0..n/2} A027907(n+1-j,2*j+1), n >= 0. - Werner Schulte, Sep 29 2015

A135351 a(n) = (2^n + 3 - 7(-1)^n + 30^n)/6; or a(0) = 0 and for n > 0, a(n) = A005578(n-1) - (-1)^n.

Original entry on oeis.org

0, 2, 0, 3, 2, 7, 10, 23, 42, 87, 170, 343, 682, 1367, 2730, 5463, 10922, 21847, 43690, 87383, 174762, 349527, 699050, 1398103, 2796202, 5592407, 11184810, 22369623, 44739242, 89478487, 178956970, 357913943, 715827882, 1431655767, 2863311530, 5726623063, 11453246122, 22906492247, 45812984490

Offset: 0

Miklos Kristof, Dec 07 2007

Partial sums of A155980 for n > 2. - Klaus Purath, Jan 30 2021

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A005578, A099754.
Cf. A001045, A327767, A328284.
Cf. A007583, A062092, A087289, A020988 (even bisection), A163834 (odd bisection), A078008, A084247, A181565.

List([0..40], n-> (2^n+3-7*(-1)^n+3*0^n)/6); # G. C. Greubel, Sep 02 2019

a135351:=func< n | (2^n+3-7*(-1)^n+3*0^n)/6 >; [ a135351(n): n in [0..32] ]; // Klaus Brockhaus, Dec 05 2009

G(x):=x*(2 - 4*x + x^2)/((1-x^2)*(1-2*x)): f[0]:=G(x): for n from 1 to 30 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n]/n!,n=0..30);

Join[{0}, Table[(2^n +3 -7*(-1)^n)/6, {n,40}]] (* G. C. Greubel, Oct 11 2016 *)
LinearRecurrence[{2,1,-2},{0,2,0,3},40] (* Harvey P. Dale, Feb 13 2024 *)

a(n) = (2^n + 3 - 7*(-1)^n + 3*0^n)/6; \\ Michel Marcus, Oct 11 2016

[(2^n+3-7*(-1)^n+3*0^n)/6 for n in (0..40)] # G. C. Greubel, Sep 02 2019

G.f.: x*(2 - 4*x + x^2)/((1-x^2)*(1-2*x)).
E.g.f.: (exp(2*x) + 3*exp(x) - 7*exp(-x) + 3)/6.
From Paul Curtz, Dec 20 2020: (Start)
a(n) + (period 2 sequence: repeat [1, -2]) = A328284(n+2).
a(n+1) + (period 2 sequence: repeat [-2, 1]) = A001045(n).
a(n+1) + (period 2 sequence: repeat [-1, 0]) = A078008(n).
a(n+1) + (period 2 sequence : repeat [-3, 2]) = -(-1)^n*A084247(n).
a(n+4) = a(n+1) + 7*A001045(n).
a(n+4) + a(n+1) = A181565(n).
a(2*n+2) + a(2*n+3) = A087289(n) = 3*A007583(n).
a(2*n+1) = A163834(n), a(2*n+2) = A020988(n). (End)

First part of definition corrected by Klaus Brockhaus, Dec 05 2009

A144414 a(n) = 2*(4^n - 1)/3 - n.

Original entry on oeis.org

1, 8, 39, 166, 677, 2724, 10915, 43682, 174753, 699040, 2796191, 11184798, 44739229, 178956956, 715827867, 2863311514, 11453246105, 45812984472, 183251937943, 733007751830, 2932031007381, 11728124029588, 46912496118419

Offset: 1

Roger L. Bagula and Gary W. Adamson, Oct 01 2008

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A142458, A142976, A144380.

[(2^(2*n+1) -3*n -2)/3: n in [1..50]]; // G. C. Greubel, Mar 28 2021

Table[2(4^n-1)/3 -n,{n,30}] (* or *) LinearRecurrence[{6,-9,4},{1,8,39},30] (* Harvey P. Dale, Mar 17 2015 *)

[(2^(2*n+1) -3*n -2)/3 for n in (1..50)] # G. C. Greubel, Mar 28 2021

a(n) = A142458(n+1,n).
a(n) = A020988(n) - n. - R. J. Mathar, Nov 21 2008
G.f.: x*(1+2*x)/((1-x)^2*(1-4*x)). - Colin Barker, Jan 11 2012
a(1)=1, a(2)=8, a(3)=39, a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3). - Harvey P. Dale, Mar 17 2015
E.g.f.: (1/3)*(-2 - 3*x + 2*exp(x))*exp(x). - G. C. Greubel, Mar 28 2021

cp's OEIS Frontend

A073724 a(n) = (4^(n+1) + 6n + 5)/9.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A173732 a(n) = (A016957(n)/2^A007814(A016957(n)) - 1)/2, with A016957(n) = 6*n+4 and A007814(n) the 2-adic valuation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Mathematica

PARI

Formula

Extensions

A080675 a(n) = (5*4^n - 8)/6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A083597 a(n) = (7*4^n - 4)/3.

Views

Author

Keywords

Comments

Links

Programs

Magma

Mathematica

PARI

Formula

A167030 a(n) = (2^n - (-1)^n - 3)/3.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A211016 Triangle read by rows: T(n,k) = number of squares and rectangles of area 2^(k-1) after 2^n stages in the toothpick structure of A139250, n>=1, k>=1, assuming the toothpicks have length 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A048329 Numbers that are repdigits in base 4.

Views

Author

Keywords

Examples

A135351 a(n) = (2^n + 3 - 7(-1)^n + 30^n)/6; or a(0) = 0 and for n > 0, a(n) = A005578(n-1) - (-1)^n.