A060482 -id:A060482 - cp's OEIS frontend

A016116 a(n) = 2^floor(n/2).

1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768, 32768, 65536, 65536, 131072, 131072, 262144, 262144, 524288, 524288, 1048576, 1048576, 2097152

Offset: 0

N. J. A. Sloane, Dec 11 1999

Powers of 2 doubled up. The usual OEIS policy is to omit the duplicates in such cases (when this would become A000079). This is an exception.
Number of symmetric compositions of n: e.g., 5 = 2+1+2 = 1+3+1 = 1+1+1+1+1 so a(5) = 4; 6 = 3+3 = 2+2+2 = 1+4+1 = 2+1+1+2 = 1+2+2+1 = 1+1+2+1+1 = 1+1+1+1+1+1 so a(6) = 8. - Henry Bottomley, Dec 10 2001
This sequence is the number of digits of each term of A061519. - Dmitry Kamenetsky, Jan 17 2009
Starting with offset 1 = binomial transform of [1, 1, -1, 3, -7, 17, -41, ...]; where A001333 = (1, 1, 3, 7, 17, 41, ...). - Gary W. Adamson, Mar 25 2009
a(n+1) is the number of symmetric subsets of [n]={1,2,...,n}. A subset S of [n] is symmetric if k is an element of S implies (n-k+1) is an element of S. - Dennis P. Walsh, Oct 27 2009
INVERT and inverse INVERT transforms give A006138, A039834(n-1).
The Kn21 sums, see A180662, of triangle A065941 equal the terms of this sequence. - Johannes W. Meijer, Aug 15 2011
First differences of A027383. - Jason Kimberley, Nov 01 2011
Run lengths in A079944. - Jeremy Gardiner, Nov 21 2011
Number of binary palindromes (A006995) between 2^(n-1) and 2^n (for n>1). - Hieronymus Fischer, Feb 17 2012
Pisano period lengths: 1, 1, 4, 1, 8, 4, 6, 1, 12, 8, 20, 4, 24, 6, 8, 1, 16, 12, 36, 8, ... . - R. J. Mathar, Aug 10 2012
Range of row n of the Circular Pascal array of order 4. - Shaun V. Ault, May 30 2014
a(n) is the number of permutations of length n avoiding both 213 and 312 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Also, the decimal representation of the diagonal from the origin to the corner (and from the corner to the origin except for the initial term) of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 190", based on the 5-celled von Neumann neighborhood when initialized with a single black (ON) cell at stage zero. - Robert Price, May 10 2017
a(n + 1) + n - 1, n > 0, is the number of maximal subsemigroups of the monoid of partial order-preserving or -reversing mappings on a set with n elements. See the East et al. link. - James Mitchell and Wilf A. Wilson, Jul 21 2017
Number of symmetric stairs with n cells. A stair is a snake polyomino allowing only two directions for adjacent cells: east and north. See A005418. - Christian Barrientos, May 11 2018
For n >= 4, a(n) is the exponent of the group of the Gaussian integers in a reduced system modulo (1+i)^(n+2). See A302254. - Jianing Song, Jun 27 2018
a(n) is the number of length-(n+1) binary sequences, denoted , with s(1)=1 and with s(i+1)=s(i) for odd i. - Dennis P. Walsh, Sep 06 2018
a(n+1) is the number of subsets of {1,2,..,n} in which all differences between successive elements of subsets are even.  For example, for n = 7, a(6) = 8 and the 8 subsets are {7}, {1,7}, {3,7}, {5,7}, {1,3,7}, {1,5,7}, {3,5,7}, {1,3,5,7}.  For odd differences between elements see Comment in A000045 (Fibonacci numbers). - Enrique Navarrete, Jul 01 2020
Also, the number of walks of length n on the graph x--y--z, starting at x. - Sean A. Irvine, May 30 2025

			For n=5 the a(5)=4 symmetric subsets of [4] are {1,4}, {2,3}, {1,2,3,4} and the empty set. - _Dennis P. Walsh_, Oct 27 2009
For n=5 the a(5)=4 length-6 binary sequences are <1,1,0,0,0,0>, <1,1,0,0,1,1>, <1,1,1,1,0,0> and <1,1,1,1,1,1>. - _Dennis P. Walsh_, Sep 06 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, Oct 06 2014, Pages 45-54.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
Arvind Ayyer, Amritanshu Prasad, and Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016. See Theorem 6 p. 12.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
Francesco Battistoni and Giuseppe Molteni, An elementary proof for a generalization of a Pohst's inequality, arXiv:2101.06163 [math.NT], 2021.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Emeric Deutsch, Problem 1633, Math. Mag., 74 #5 (2001), p. 403.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017.
A. Goupil, H. Cloutier, and F. Nouboud, Enumeration of polyominoes inscribed in a rectangle Discrete Applied Mathematics 158(2010), pp. 2014-2023.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1067
D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
D. Merlini, F. Uncini and M. C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), A23, 26 pp.
Agustín Moreno Cañadas, Hernán Giraldo, and Robinson Julian Serna Vanegas, Some integer partitions induced by orbits of Dynkin type, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 12 (2017), pp. 2745-2766.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, Laurent, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013, Laurent, Année 2012-2013.
Valentin Ovsienko, Villes paires et impaires (Oddtown and Eventown) I, Images des Mathématiques, CNRS, 2013 (in French).
Dennis Walsh, Notes on symmetric subsets of {1, 2, ..., n}
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264 | doi:10.1246/bcsj.20140204. See Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A006995, A057148, A079944, A112030, A112033.
a(n) = A094718(3, n).
Cf. A001333.
See A052955 for partial sums (without the initial term).
A000079 gives the odd-indexed terms of a(n).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

List([0..45],n->2^Int(n/2)); # Muniru A Asiru, Apr 03 2018

[2^Floor(n/2): n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

A016116:= proc(n): 2^floor(n/2) end: seq(A016116(n), n=0..42); # Dennis P. Walsh, Oct 27 2009

Table[ 2^Floor[n/2], {n, 0, 42}] (* Robert G. Wilson v, Jun 05 2004 *)
With[{c=2^Range[0,30]},Riffle[c,c]] (* Harvey P. Dale, Jan 23 2015 *)
CoefficientList[Series[(1+x)/(1-2*x^2), {x, 0, 50}], x] (* Stefano Spezia, Sep 07 2018 *)

makelist(2^floor(n/2), n, 0, 50); /* Martin Ettl, Oct 17 2012 */

PARI
```
a(n)=if(n<0,0,2^(n\2))
```

def A016116(n): return 1 << n//2 # Chai Wah Wu, Jun 07 2022

def A016116():
    x, y = -1, 0
    while True:
        yield -x
        x, y = x + y, x - y
a = A016116(); [next(a) for i in range(40)]  # Peter Luschny, Jul 11 2013

a(n) = a(n-1)*a(n-2)/a(n-3) = 2*a(n-2) = 2^A004526(n).
G.f.: (1+x)/(1-2*x^2).
a(n) = (1/2 + sqrt(1/8))*sqrt(2)^n + (1/2 - sqrt(1/8))*(-sqrt(2))^n. - Ralf Stephan, Mar 11 2003
E.g.f.: cosh(sqrt(2)*x) + sinh(sqrt(2)*x)/sqrt(2). - Paul Barry, Jul 16 2003
The signed sequence (-1)^n*2^floor(n/2) has a(n) = (sqrt(2))^n(1/2 - sqrt(2)/4) + (-sqrt(2))^n(1/2 + sqrt(2)/4). It is the inverse binomial transform of A000129(n-1). - Paul Barry, Apr 21 2004
Diagonal sums of A046854. a(n) = Sum_{k=0..n} binomial(floor(n/2), k). - Paul Barry, Jul 07 2004
a(n) = a(n-2) + 2^floor((n-2)/2). - Paul Barry, Jul 14 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2), floor(k/2)). - Paul Barry, Jul 15 2004
E.g.f.: cosh(asinh(1) + sqrt(2)*x)/sqrt(2). - Michael Somos, Feb 28 2005
a(n) = Sum_{k=0..n} A103633(n,k). - Philippe Deléham, Dec 03 2006
a(n) = 2^(n/2)*((1 + (-1)^n)/2 + (1-(-1)^n)/(2*sqrt(2))). - Paul Barry, Nov 12 2009
a(n) = 2^((2*n - 1 + (-1)^n)/4). - Luce ETIENNE, Sep 20 2014

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454

Offset: 0

R. K. Guy

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5                R
                    / \
                   /   \
                  /     \
                 /       B
                /       / \
mrbt4          B       /   B
              / \     B   E E
             /   B   E E
mrbt3       R   E E
           / \
          /   B
mrbt2    B   E E
        / E
mrbt1  R
      E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors.  For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753-754.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015

[2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008

a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)

a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011

def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000

Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022

A029744 Numbers of the form 2^n or 3*2^n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304

Offset: 1

N. J. A. Sloane

This entry is a list, and so has offset 1. WARNING: However, in this entry several comments, formulas and programs seem to refer to the original version of this sequence which had offset 0. - M. F. Hasler, Oct 06 2014
Number of necklaces with n-1 beads and two colors that are the same when turned over and hence have reflection symmetry. [edited by Herbert Kociemba, Nov 24 2016]
The subset {a(1),...,a(2k)} contains all proper divisors of 3*2^k. - Ralf Stephan, Jun 02 2003
Let k = any nonnegative integer and j = 0 or 1. Then n+1 = 2k + 3j and a(n) = 2^k*3^j. - Andras Erszegi (erszegi.andras(AT)chello.hu), Jul 30 2005
Smallest number having no fewer prime factors than any predecessor, a(0)=1; A110654(n) = A001222(a(n)); complement of A116451. - Reinhard Zumkeller, Feb 16 2006
A093873(a(n)) = 1. - Reinhard Zumkeller, Oct 13 2006
a(n) = a(n-1) + a(n-2) - gcd(a(n-1), a(n-2)), n >= 3, a(1)=2, a(2)=3. - Ctibor O. Zizka, Jun 06 2009
Where records occur in A048985: A193652(n) = A048985(a(n)) and A193652(n) < A048985(m) for m < a(n). - Reinhard Zumkeller, Aug 08 2011
A002348(a(n)) = A000079(n-3) for n > 2. - Reinhard Zumkeller, Mar 18 2012
Without initial 1, third row in array A228405. - Richard R. Forberg, Sep 06 2013
Also positions of records in A048673. A246360 gives the record values. - Antti Karttunen, Sep 23 2014
Known in numerical mathematics as "Bulirsch sequence", used in various extrapolation methods for step size control. - Peter Luschny, Oct 30 2019
For n > 1, squares of the terms can be expressed as the sum of two powers of two: 2^x + 2^y. - Karl-Heinz Hofmann, Sep 08 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..2000
Spencer Daugherty, Pamela E. Harris, Ian Klein, and Matt McClinton, Metered Parking Functions, arXiv:2406.12941 [math.CO], 2024. See pp. 11, 22.
Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012
Index entries for linear recurrences with constant coefficients, signature (0,2).
Index entries for sequences related to necklaces

Cf. A056493, A038754, A063759. Union of A000079 and A007283.
First differences are in A016116(n-1).
Cf. A082125, A094958, A048739, A048985, A193652, A048673, A064216, A246360, A354785.
Row sums of the triangle in sequence A119963. - John P. McSorley, Aug 31 2010
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent. There may be minor differences from (s(n)) at the start, and a shift of indices. A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A060482 (s(n)-3); A136252 (s(n)-3); A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4);   A354785 (3*s(n)), A061776 (3*s(n)-6); A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

a029744 n = a029744_list !! (n-1)
a029744_list = 1 : iterate
   (\x -> if x `mod` 3 == 0 then 4 * x `div` 3 else 3 * x `div` 2) 2
-- Reinhard Zumkeller, Mar 18 2012

1,seq(op([2^i,3*2^(i-1)]),i=1..100); # Robert Israel, Sep 23 2014

CoefficientList[Series[(-x^2 - 2*x - 1)/(2*x^2 - 1), {x, 0, 200}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)
Function[w, DeleteCases[Union@ Flatten@ w, k_ /; k > Max@ First@ w]]@ TensorProduct[{1, 3}, 2^Range[0, 22]] (* Michael De Vlieger, Nov 24 2016 *)
LinearRecurrence[{0,2},{1,2,3},50] (* Harvey P. Dale, Jul 04 2017 *)

PARI
```
a(n)=if(n%2,3/2,2)<<((n-1)\2)\1
```

def A029744(n):
    if n == 1: return 1
    elif n % 2 == 0: return 2**(n//2)
    else: return 3 * 2**((n-3)//2) # Karl-Heinz Hofmann, Sep 08 2022

(define (A029744 n) (cond ((<= n 1) n) ((even? n) (expt 2 (/ n 2))) (else (* 3 (expt 2 (/ (- n 3) 2)))))) ;; Antti Karttunen, Sep 23 2014

a(n) = 2*A000029(n) - A000031(n).
For n > 2, a(n) = 2*a(n - 2); for n > 3, a(n) = a(n - 1)*a(n - 2)/a(n - 3). G.f.: (1 + x)^2/(1 - 2*x^2). - Henry Bottomley, Jul 15 2001, corrected May 04 2007
a(0)=1, a(1)=1 and a(n) = a(n-2) * ( floor(a(n-1)/a(n-2)) + 1 ). - Benoit Cloitre, Aug 13 2002
(3/4 + sqrt(1/2))*sqrt(2)^n + (3/4 - sqrt(1/2))*(-sqrt(2))^n. a(0)=1, a(2n) = a(n-1)*a(n), a(2n+1) = a(n) + 2^floor((n-1)/2). - Ralf Stephan, Apr 16 2003 [Seems to refer to the original version with offset=0. - M. F. Hasler, Oct 06 2014]
Binomial transform is A048739. - Paul Barry, Apr 23 2004
E.g.f.: (cosh(x/sqrt(2)) + sqrt(2)sinh(x/sqrt(2)))^2.
a(1) = 1; a(n+1) = a(n) + A000010(a(n)). - Stefan Steinerberger, Dec 20 2007
u(2)=1, v(2)=1, u(n)=2*v(n-1), v(n)=u(n-1), a(n)=u(n)+v(n). - Jaume Oliver Lafont, May 21 2008
For n => 3, a(n) = sqrt(2*a(n-1)^2 + (-2)^(n-3)). - Richard R. Forberg, Aug 20 2013
a(n) = A064216(A246360(n)). - Antti Karttunen, Sep 23 2014
a(n) = sqrt((17 - (-1)^n)*2^(n-4)) for n >= 2. - Anton Zakharov, Jul 24 2016
Sum_{n>=1} 1/a(n) = 8/3. - Amiram Eldar, Nov 12 2020
a(n) = 2^(n/2) if n is even. a(n) = 3 * 2^((n-3)/2) if n is odd and for n>1. - Karl-Heinz Hofmann, Sep 08 2022

Corrected and extended by Joe Keane (jgk(AT)jgk.org), Feb 20 2000

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the least k such that A056792(k) = n.
One quarter of the number of positive integer (n+2) X (n+2) arrays with every 2 X 2 subblock summing to 1. - R. H. Hardin, Sep 29 2008
Number of length n+1 left factors of Dyck paths having no DUU's (here U=(1,1) and D=(1,-1)). Example: a(4)=7 because we have UDUDU, UUDDU, UUDUD, UUUDD, UUUDU, UUUUD, and UUUUU (the paths UDUUD, UDUUU, and UUDUU do not qualify).
Number of binary palindromes < 2^n (see A006995). - Hieronymus Fischer, Feb 03 2012
Partial sums of A016116 (omitting the initial term). - Hieronymus Fischer, Feb 18 2012
a(n - 1), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving or -reversing partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017
Number of monomials of the algebraic normal form of the Boolean function representing the n-th bit of the product 3x in terms of the bits of x. - Sebastiano Vigna, Oct 04 2020

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 15*x^6 + 23*x^7 + ... - _Michael Somos_, Jun 24 2018

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, 2014.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, Journal of Combinatorics 5 (2014), 453-469.
David Blackman and Sebastiano Vigna, Scrambled Linear Pseudorandom Number Generators, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; arXiv preprint, arXiv:1805.01407 [cs.DS], 2018.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]
Brian Hopkins and Aram Tangboonduangjit, Water Cells in Compositions of 1s and 2s, arXiv:2412.11528 [math.CO], 2024. See p. 9.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026
Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
Mark Shattuck, Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's, arXiv:2501.09931 [math.CO], 2025. See p. 3.
Index to sequences related to the complexity of n
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225 for even terms, A055010 for odd terms. See also A056792.
Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]
Union of A000225 & A055010.
For partial sums see A027383.
See A016116 for the first differences.
Cf. A083329, A107659, A132666.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019

a052955 n = a052955_list !! n
a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
-- Reinhard Zumkeller, Feb 22 2012

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019

spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n]/2, n=2..43); # Zerinvary Lajos, Mar 16 2008

a[n_]:= If[EvenQ[n], 2^(n/2+1) -1, 3*2^((n-1)/2) -1]; Table[a[n], {n, 0, 41}] (* Robert G. Wilson v, Jun 05 2004 *)
a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* Michael Somos, Jun 24 2018 *)

a(n)=(2+n%2)<<(n\2)-1 \\ Charles R Greathouse IV, Jun 19 2011

{a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* Michael Somos, Jun 24 2018 */

# command line argument tells how high to take n
# Beyond a(38) = 786431 you may need a special code to handle large integers
  $lim = shift;
  sub show{};
$n = $incr = $P = 1;
show($n, $incr, $P);
$incr = 1;
for $n (2..$lim) {
    $P += $incr;
    show($n, $P, $incr, $P);
    $incr *=2 if ($n % 2); # double the increment after an odd n
}
sub show {
    my($n, $P) = @_;
    printf("%4d\t%16g\n", $n, $P);
}
# Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010

def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019

a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.
G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).
a(n) = -1 + Sum_{alpha = RootOf(-1 + 2*Z^2)} (1/4) * (3 + 4*alpha) * alpha^(-1-n). (That is, the sum is indexed by the roots of the polynomial -1 + 2*Z^2.)
a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - Paul Barry, May 23 2004
a(n) = 1 + Sum_{k=0..n-1} A016116(k). - Robert G. Wilson v, Jun 05 2004
A132340(a(n)) = A027383(n). - Reinhard Zumkeller, Aug 20 2007
From Hieronymus Fischer, Sep 15 2007: (Start)
a(n) = A027383(n-1) + 1 for n>0.
a(n) = A132666(a(n+1)-1).
a(n) = A132666(a(n-1)) + 1 for n>0.
A132666(a(n)) = a(n+1) - 1. (End)
a(n) = A027383(n+1)/2. - Zerinvary Lajos, Mar 16 2008
a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - Hieronymus Fischer, Feb 03 2012
a(2n+1) = (a(2*n) + a(2*n+2))/2. Combined with a(n) = 2*a(n-2) + 1, n >= 2 and a(0) = 1, this specifies the sequence. - Richard R. Forberg, Nov 30 2013
a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - Luce ETIENNE, Sep 20 2014
a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/4)*exp(-sqrt(2)*x)*(4 - 3*sqrt(2) + (4 + 3*sqrt(2))*exp(2*sqrt(2)*x) - 4*exp(x + sqrt(2)*x)). - Stefano Spezia, Oct 22 2019
A term k appears in this sequence <=> 4 does not divide binomial(k, j) for any j in 0..k. - Peter Luschny, Jun 28 2025

Formula and more terms from Henry Bottomley, May 03 2000
Additional comments from Robert G. Wilson v, Jan 29 2001
Minor edits from N. J. A. Sloane, Jul 09 2022

A060546 a(n) = 2^ceiling(n/2).

Original entry on oeis.org

1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768, 32768, 65536, 65536, 131072, 131072, 262144, 262144, 524288, 524288, 1048576, 1048576, 2097152, 2097152

Offset: 0

André Barbé (Andre.Barbe(AT)esat.kuleuven.ac.be), Apr 03 2001

a(n) is also the number of median-reflective (palindrome) symmetric patterns in a top-down equilateral triangular arrangement of closely packed black and white cells satisfying the local matching rule of Pascal's triangle modulo 2, where n is the number of cells in each edge of the arrangement. The matching rule is such that any elementary top-down triangle of three neighboring cells in the arrangement contains either one or three white cells.
The number of possibilities for an n-game (sub)set of tennis with neither player gaining a 2-game advantage. (Motivated by the marathon Isner-Mahut match at Wimbledon, 2010.) - Barry Cipra, Jun 28 2010
Number of achiral rows of n colors using up to two colors. For a(3)=4, the rows are AAA, ABA, BAB, and BBB. - Robert A. Russell, Nov 07 2018
Also the number of walks of length n on the graph x--y--z starting at y. - Sean A. Irvine, May 30 2025

Harry J. Smith, Table of n, a(n) for n = 0..500
A. Barbé, Symmetric patterns in the cellular automaton that generates Pascal's triangle modulo 2, Discr. Appl. Math. 105(2000), 1-38.
Index entries for sequences related to cellular automata
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,2).

Column k=2 of A321391.
Cf. A016116, A008619.
Cf. A000079 (oriented), A005418(n+1) (unoriented), A122746(n-2) (chiral).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

[2^Ceiling(n/2): n in [0..50]]; // G. C. Greubel, Nov 07 2018

for n from 0 to 100 do printf(`%d,`,2^ceil(n/2)) od:

2^Ceiling[Range[0,50]/2] (* or *) Riffle[2^Range[0, 25], 2^Range[25]] (* Harvey P. Dale, Mar 05 2013 *)
LinearRecurrence[{0, 2}, {1, 2}, 40] (* Robert A. Russell, Nov 07 2018 *)

a(n) = { 2^ceil(n/2) } \\ Harry J. Smith, Jul 06 2009

a(n) = 2^ceiling(n/2).
a(n) = A016116(n+1) for n >= 1.
a(n) = 2^A008619(n-1) for n >= 1.
G.f.: (1 + 2*x) / (1 - 2*x^2). - Ralf Stephan, Jul 15 2013
E.g.f.: cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x). - Stefano Spezia, Feb 02 2023

More terms from James Sellers, Apr 04 2001
a(0)=1 prepended by Robert A. Russell, Nov 07 2018
Edited by N. J. A. Sloane, Nov 10 2018

A068156 G.f.: (x+2)(x+1)/((x-1)(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

Original entry on oeis.org

1, 3, 9, 21, 45, 93, 189, 381, 765, 1533, 3069, 6141, 12285, 24573, 49149, 98301, 196605, 393213, 786429, 1572861, 3145725, 6291453, 12582909, 25165821, 50331645, 100663293, 201326589, 402653181, 805306365, 1610612733

Offset: 0

Benoit Cloitre, Mar 12 2002

Number of moves to solve Hard Pagoda puzzle.
Partial sums of A111286. Binomial transform of (1,2,4,2,4,2,4 ....). - Paul Barry, Feb 28 2003
Warren W. Kokko writes that this sequence also appears to give the number of scoring sequences for the Racer Dice Game with n dice. - N. J. A. Sloane, Feb 24 2015
From Michel Lagneau, Apr 27 2015: (Start)
For n > 0, a(n) is the number of identical bowls having the same weight except for one which has a higher weight than the others which are identifiable by a weighing machine using n weighings.
Example: a(2)=9 because two weighings are sufficient:
Start with 9 bowls;
Step 1: remove 3 bowls => there are still 6 bowls;
Step 2: first weighing of 6 bowls (3 bowls on each side of the weighing machine);
Step 3: if the machine is in equilibrium, we find immediately the unknown bowl with a second weighing from the first 3 removing bowls. Else, we find immediately the unknown bowl with a second weighing from the 3 heaviest bowls.
Note: If the unknown bowl has a lower weight, the reasoning is the same, but it is necessary to know whether the unknown bowl is heavier or lighter.
In the general case, we always remove 3 bowls in step 1.
(End)
The number of ternary words of length n that avoid {11-2,22-1}. G.f. [1+(k-1)*x^2]/[1-k*x+(k-1)*x^2] at k=3. [Theorem 7.93 by Heubach and Mansour]. - R. J. Mathar, May 22 2016
Apart from the first term, column 2 of A222057. - Anton Zakharov, Oct 27 2016

Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.
S. Heubach, T. Mansour, in Combinatorics of Compositions and words, Discr. Math. Applicat. (ed by K H Rosen), CRC Press 2010, p 300.
Warren W. Kokko, The Racer Dice Game, Manuscript, 2015.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Artur Schaefer, Endomorphisms of The Hamming Graph and Related Graphs, arXiv preprint arXiv:1602.02186 [math.CO], 2016. See Table Remark 4.5.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

A diagonal of A233308 (for n > 1).

Cf. A000079.

[3*2^n+0^n-3 : n in [0..30]]; // Vincenzo Librandi, Nov 11 2011

Join[{1}, LinearRecurrence[{3, -2}, {3, 9}, 30]] (* Jean-François Alcover, Jan 08 2019 *)
CoefficientList[Series[(1+2x^2)/((1-2x)(1-x)),{x,0,40}],x] (* Harvey P. Dale, Jan 02 2022 *)

def a(n): return 3*2**n+0**n-3 # Torlach Rush, Jan 09 2025

a(0) = 1, a(n) = A060482(2n+1). For n > 0, a(n+1) = 2*a(n)+3.
G.f.: (1+2*x^2)/((1-2*x)*(1-x)). - Paul Barry, Feb 28 2003
a(n) = 3*2^n+0^n-3. - Paul Barry, Sep 04 2003
a(n) = A099257(A033484(n)+1) = 2*A033484(n) + 1. - Reinhard Zumkeller, Oct 09 2004
a(n) = 3*a(n-1) - 2*a(n-2), n > 1. - Vincenzo Librandi, Nov 11 2011
a(n) = a(n-1)+ 3*2^(n-1); a(1)=3. - Ctibor O. Zizka, Apr 17 2008
E.g.f.: 1 + 3*(exp(x) - 1)*exp(x). - Ilya Gutkovskiy, May 22 2016

A163403 a(n) = 2*a(n-2) for n > 2; a(1) = 1, a(2) = 2.

Original entry on oeis.org

Offset: 1

Klaus Brockhaus, Jul 26 2009

a(n+1) is the number of palindromic words of length n using a two-letter alphabet. - Michael Somos, Mar 20 2011

			x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 8*x^6 + 8*x^7 + 16*x^8 + 16*x^9 + 32*x^10 + ...

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

Equals A016116 without initial 1. Unsigned version of A152166.
Partial sums are in A136252.
Binomial transform is A078057, second binomial transform is A007070, third binomial transform is A102285, fourth binomial transform is A163350, fifth binomial transform is A163346.
Cf. A000079 (powers of 2), A009116, A009545, A051032.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

[ n le 2 select n else 2*Self(n-2): n in [1..43] ];

LinearRecurrence[{0, 2}, {1, 2}, 50] (* Paolo Xausa, Feb 02 2024 *)

{a(n) = if( n<1, 0, 2^(n\2))} /* Michael Somos, Mar 20 2011 */

def A163403():
    x, y = 1, 1
    while True:
        yield x
        x, y = x + y, x - y
a = A163403(); [next(a) for i in range(40)]  # Peter Luschny, Jul 11 2013

a(n) = 2^((1/4)*(2*n - 1 + (-1)^n)).
G.f.: x*(1 + 2*x)/(1 - 2*x^2).
a(n) = A051032(n) - 1.
G.f.: x / (1 - 2*x / (1 + x / (1 + x))) = x * (1 + 2*x / (1 - x / (1 - x / (1 + 2*x)))). - Michael Somos, Jan 03 2013
From R. J. Mathar, Aug 06 2009: (Start)
a(n) = A131572(n).
a(n) = A060546(n-1), n > 1. (End)
a(n+3) = a(n+2)*a(n+1)/a(n). - Reinhard Zumkeller, Mar 04 2011
a(n) = |A009116(n-1)| + |A009545(n-1)|. - Bruno Berselli, May 30 2011
E.g.f.: cosh(sqrt(2)*x) + sinh(sqrt(2)*x)/sqrt(2) - 1. - Stefano Spezia, Feb 05 2023

A136252 a(n) = a(n-1) + 2a(n-2) - 2a(n-3).

Original entry on oeis.org

1, 3, 5, 9, 13, 21, 29, 45, 61, 93, 125, 189, 253, 381, 509, 765, 1021, 1533, 2045, 3069, 4093, 6141, 8189, 12285, 16381, 24573, 32765, 49149, 65533, 98301, 131069, 196605, 262141, 393213, 524285, 786429, 1048573, 1572861, 2097149, 3145725, 4194301, 6291453, 8388605

Offset: 0

Paul Curtz, Mar 17 2008

For n >= 2, number of n X n arrays with values that are squares of integers, having all 2 X 2 subblocks summing to 4. - R. H. Hardin, Apr 03 2009

Number of moves required in 4-peg Tower of Hanoi solution using a (suboptimal) recursive algorithm: Move (n-2) disks, move bottom 2 disks, move (n-2) disks. Cf. A007664. - Toby Gottfried, Nov 29 2010

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

Same recurrence as in A135530.
Partial sums of A163403.
A060482 without the term 2.
Cf. A007664 (Optimal 4-peg Tower of Hanoi).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

a:=proc(n) options operator,arrow: 2^((1/2)*n-1)*(4+4*(-1)^n+3*sqrt(2)*(1-(-1)^n))-3 end proc: seq(a(n),n=0..40); # Emeric Deutsch, Mar 31 2008

LinearRecurrence[{1, 2, -2}, {1, 3, 5}, 100] (* G. C. Greubel, Feb 18 2017 *)

x='x+O('x^50); Vec((1+2*x)/((1-x)*(1-2*x^2))) \\ G. C. Greubel, Feb 18 2017

a(n) = 2^((1/2)*n-1)*(4 + 4(-1)^n + 3*sqrt(2)*(1-(-1)^n)) - 3. - Emeric Deutsch, Mar 31 2008
G.f.: (1+2*x)/((1-x)*(1-2*x^2)). - Jaume Oliver Lafont, Aug 30 2009
a(n) = 2*a(n-2) + 3; first differences are powers of 2, occurring in pairs. - Toby Gottfried, Nov 29 2010
a(n) = A027383(n+1) - 1. - Jason Kimberley, Nov 01 2011
a(2n+1) = (a(2n) + a(2n+2))/2. - Richard R. Forberg, Nov 30 2013
E.g.f.: 4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x) - 3*cosh(x) - 3*sinh(x). - Stefano Spezia, May 13 2023

Edited by N. J. A. Sloane, Apr 18 2008

More terms from Emeric Deutsch, Mar 31 2008

A152166 a(2n) = 2^n; a(2n+1) = -(2^(n+1)).

Original entry on oeis.org

1, -2, 2, -4, 4, -8, 8, -16, 16, -32, 32, -64, 64, -128, 128, -256, 256, -512, 512, -1024, 1024, -2048, 2048, -4096, 4096, -8192, 8192, -16384, 16384, -32768, 32768, -65536, 65536, -131072, 131072, -262144, 262144, -524288, 524288, -1048576, 1048576

Offset: 0

Philippe Deléham, Nov 27 2008

Ratios of successive terms are -2,-1,-2,-1,-2,-1,-2,-1,... - Philippe Deléham, Dec 12 2008

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A000079, A016116, A147703.

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

LinearRecurrence[{0, 2}, {1, -2}, 50] (* Paolo Xausa, Jul 19 2024 *)

G.f.: (1 - 2*x)/(1 - 2*x^2).
a(n) = 2*a(n-2); a(0)=1, a(1)=-2.
a(n) = Sum_{k=0..n} A147703(n,k)*(-3)^k.
E.g.f.: cosh(sqrt(2)*x) - sqrt(2)*sinh(sqrt(2)*x). - Stefano Spezia, Feb 05 2023

A117575 Expansion of (1-x^3)/((1-x)(1+2x^2)).

Original entry on oeis.org

1, 1, -1, -2, 2, 4, -4, -8, 8, 16, -16, -32, 32, 64, -64, -128, 128, 256, -256, -512, 512, 1024, -1024, -2048, 2048, 4096, -4096, -8192, 8192, 16384, -16384, -32768, 32768, 65536, -65536, -131072, 131072, 262144, -262144, -524288, 524288

Offset: 0

Paul Barry, Mar 29 2006

Row sums of A116949.
From Paul Curtz, Oct 24 2012: (Start)
b(n) = abs(a(n)) = A158780(n+1) = 1,1,1,2,2,4,4,8,8,8,... .
Consider the autosequence (that is a sequence whose inverse binomial transform is equal to the signed sequence) of the first kind of the example. Its numerator is A046978(n), its denominator is b(n). The numerator of the first column is A075553(n).
The denominator corresponding to the 0's is a choice.
The classical denominator is 1,1,1,2,1,4,4,8,1,16,16,32,1,... . (End)

			   0/1,  1/1    1/1,   1/2,   0/2,  -1/4,  -1/4,  -1/8, ...
   1/1,  0/1,  -1/2,  -1/2,  -1/4,   0/4,   1/8,   1/8, ...
  -1/1, -1/2,   0/2,   1/4,   1/4,   1/8,   0/8, -1/16, ...
   1/2,  1/2,   1/4,   0/4   -1/8,  -1/8, -1/16,  0/16, ...
   0/2, -1/4,  -1/4,  -1/8,   0/8,  1/16,  1/16,  1/32, ...
  -1/4,  0/4,   1/8,   1/8,  1/16,  0/16, -1/32, -1/32, ...
   1/4,  1/8,   0/8, -1/16, -1/16, -1/32,  0/32,  1/64, ...
  -1/8, -1/8, -1/16,  0/16,  1/32,  1/32,  1/64,  0/64. - _Paul Curtz_, Oct 24 2012

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

Cf. A016116, A046978, A075553, A116949, A122016, A191754/A192366.

[1] cat [(-1)^Floor(n/2)*2^Floor((n-1)/2): n in [1..50]]; // G. C. Greubel, Apr 19 2023

CoefficientList[Series[(1-x^3)/((1-x)(1+2x^2)),{x,0,40}],x] (* or *) LinearRecurrence[{0,-2},{1,1,-1},45] (* Harvey P. Dale, Apr 09 2018 *)

a(n)=if(n,(-1)^(n\2)<<((n-1)\2),1) \\ Charles R Greathouse IV, Jan 31 2012

def A117575(n): return 1 if (n==0) else (-1)^(n//2)*2^((n-1)//2)
[A117575(n) for n in range(51)] # G. C. Greubel, Apr 19 2023

a(n) = a(n-1) - 2*a(n-2) + 2*a(n-3) for n >= 3.
a(n) = (cos(Pi*n/2) + sin(Pi*n/2)) * (2^((n-1)/2)*(1-(-1)^n)/2 + 2^((n-2)/2)*(1+(-1)^n)/2 + 0^n/2).
a(n+1) = Sum_{k=0..n} A122016(n,k)*(-1)^k. - Philippe Deléham, Jan 31 2012
E.g.f.: (1 + cos(sqrt(2)*x) + sqrt(2)*sin(sqrt(2)*x))/2. - Stefano Spezia, Feb 05 2023
a(n) = (-1)^floor(n/2)*2^floor((n-1)/2), with a(0) = 1. - G. C. Greubel, Apr 19 2023

cp's OEIS Frontend

A016116 a(n) = 2^floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

Python

Sage

Formula

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A029744 Numbers of the form 2^n or 3*2^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Perl

Python

Sage

Formula

Extensions

A060546 a(n) = 2^ceiling(n/2).

Views

Author

Keywords

Comments

Links

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

A068156 G.f.: (x+2)(x+1)/((x-1)(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

A136252 a(n) = a(n-1) + 2a(n-2) - 2a(n-3).

A152166 a(2n) = 2^n; a(2n+1) = -(2^(n+1)).

A117575 Expansion of (1-x^3)/((1-x)(1+2x^2)).