A005836 -id:A005836 - cp's OEIS frontend

A007088 The binary numbers (or binary words, or binary vectors, or binary expansion of n): numbers written in base 2.

0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111

Offset: 0

N. J. A. Sloane, Robert G. Wilson v

List of binary numbers. (This comment is to assist people searching for that particular phrase. - N. J. A. Sloane, Apr 08 2016)
Or, numbers that are sums of distinct powers of 10.
Or, numbers having only digits 0 and 1 in their decimal representation.
Complement of A136399; A064770(a(n)) = a(n). - Reinhard Zumkeller, Dec 30 2007
From Rick L. Shepherd, Jun 25 2009: (Start)
Nonnegative integers with no decimal digit > 1.
Thus nonnegative integers n in base 10 such that kn can be calculated by normal addition (i.e., n + n + ... + n, with k n's (but not necessarily k + k + ... + k, with n k's)) or multiplication without requiring any carry operations for 0 <= k <= 9. (End)
For n > 1: A257773(a(n)) = 10, numbers that are Belgian-k for k=0..9. - Reinhard Zumkeller, May 08 2015
For any integer n>=0, find the binary representation and then interpret as decimal representation giving a(n). - Michael Somos, Nov 15 2015
N is in this sequence iff A007953(N) = A101337(N). A028897 is a left inverse. - M. F. Hasler, Nov 18 2019
For n > 0, numbers whose largest decimal digit is 1. - Stefano Spezia, Nov 15 2023

			a(6)=110 because (1/2)*((1-(-1)^6)*10^0 + (1-(-1)^3)*10^1 + (1-(-1)^1)*10^2) = 10 + 100.
G.f. = x + 10*x^2 + 11*x^3 + 100*x^4 + 101*x^5 + 110*x^6 + 111*x^7 + 1000*x^8 + ...
.
  000    The numbers < 2^n can be regarded as vectors with
  001    a fixed length n if padded with zeros on the left
  010    side. This represents the n-fold Cartesian product
  011    over the set {0, 1}. In the example on the left,
  100    n = 3. (See also the second Python program.)
  101    Binary vectors in this format can also be seen as a
  110    representation of the subsets of a set with n elements.
  111    - _Peter Luschny_, Jan 22 2024

John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 21.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §2.8 Binary, Octal, Hexadecimal, p. 64.
Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991, p. 383.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..32768 (first 8192 terms from Franklin T. Adams-Watters)
Heinz Gumin, Herrn von Leibniz' Rechnung mit Null und Eins, Siemens AG, 3. Auflage 1979 -- contains facsimiles of Leibniz's papers from 1679 and 1703.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 45.
G. W. Leibniz, Explication de l'arithmétique binaire, qui se sert des seuls caractères 0 & 1; avec des remarques sur son utilité, et sur ce qu'elle donne le sens des anciennes figures chinoises de Fohy, Mémoires de l'Académie Royale des Sciences, 1703, pp. 85-89; reprinted in Gumin (1979).
N. J. A. Sloane, Table of a(n) for n = 0..1048576 (A large file).
Robert G. Wilson v, Letter to N. J. A. Sloane, Sep. 1992.
Index entries for sequences related to Most Wanted Primes video.
Index entries for 10-automatic sequences.
Index entries for sequences related to binary expansion of n.

The basic sequences concerning the binary expansion of n are this one, A000120 (Hammingweight: sum of bits), A000788 (partial sums of A000120), A000069 (A000120 is odd), A001969 (A000120 is even), A023416 (number of bits 0), A059015 (partial sums). Bisections A099820 and A099821.
Cf. A028897 (convert binary to decimal).
Cf. A000042, A007089-A007095, A000695, A005836, A033042-A033052, A159918, A004290, A169965, A169966, A169967, A169964, A204093, A204094, A204095, A097256, A257773, A257770.
Cf. A000290, A001737, A007953, A030308, A054055, A064770, A101337, A136399.

a007088 0 = 0
a007088 n = 10 * a007088 n' + m where (n',m) = divMod n 2
-- Reinhard Zumkeller, Jan 10 2012

A007088 := n-> convert(n, binary): seq(A007088(n), n=0..50); # R. J. Mathar, Aug 11 2009

Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 39}]
Table[Sum[ (Floor[( Mod[f/2 ^n, 2])])*(10^n) , {n, 0, Floor[Log[2, f]]}], {f, 1, 100}] (* José de Jesús Camacho Medina, Jul 24 2014 *)
FromDigits/@Tuples[{1,0},6]//Sort (* Harvey P. Dale, Aug 10 2017 *)

{a(n) = subst( Pol( binary(n)), x, 10)}; /* Michael Somos, Jun 07 2002 */

{a(n) = if( n<=0, 0, n%2 + 10*a(n\2))}; /* Michael Somos, Jun 07 2002 */

a(n)=fromdigits(binary(n),10) \\ Charles R Greathouse IV, Apr 08 2015

def a(n): return int(bin(n)[2:])
print([a(n) for n in range(40)]) # Michael S. Branicky, Jan 10 2021

from itertools import product
n = 4
for p in product([0, 1], repeat=n): print(''.join(str(x) for x in p))
# Peter Luschny, Jan 22 2024

a(n) = Sum_{i=0..m} d(i)*10^i, where Sum_{i=0..m} d(i)*2^i is the base 2 representation of n.
a(n) = (1/2)*Sum_{i>=0} (1-(-1)^floor(n/2^i))*10^i. - Benoit Cloitre, Nov 20 2001
a(n) = A097256(n)/9.
a(2n) = 10*a(n), a(2n+1) = a(2n)+1.
G.f.: 1/(1-x) * Sum_{k>=0} 10^k * x^(2^k)/(1+x^(2^k)) - for sequence as decimal integers. - Franklin T. Adams-Watters, Jun 16 2006
a(A000290(n)) = A001737(n). - Reinhard Zumkeller, Apr 25 2009
a(n) = Sum_{k>=0} A030308(n,k)*10^k. - Philippe Deléham, Oct 19 2011
For n > 0: A054055(a(n)) = 1. - Reinhard Zumkeller, Apr 25 2012
a(n) = Sum_{k=0..floor(log_2(n))} floor((Mod(n/2^k, 2)))*(10^k). - José de Jesús Camacho Medina, Jul 24 2014

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Original entry on oeis.org

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285

Offset: 0

N. J. A. Sloane

Although this is a list, it has offset 0 for both historical and mathematical reasons.
Numbers whose set of base-4 digits is a subset of {0,1}. - Ray Chandler, Aug 03 2004, corrected by M. F. Hasler, Oct 16 2018
Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - Clark Kimberling
Numbers having the same representation in both binary and negabinary (A039724). - Eric W. Weisstein
This sequence has many other interesting and useful properties. Every term k corresponds to a unique pair i,j with k = a(i) + 2*a(j) (i=A059905(n), j=A059906(n)) -- see A126684. Every list of numbers L = [L1,L2,L3,...] can be encoded uniquely by "recursive binary interleaving", where f(L) = a(L1) + 2*a(f([L2,L3,...])) with f([])=0. - Marc LeBrun, Feb 07 2001
This may be described concisely using the "rebase" notation b[n]q, which means "replace b with q in the expansion of n", thus "rebasing" n from base b into base q. The present sequence is 2[n]4. Many interesting operations (e.g., 10[n](1/10) = digit reverse, shifted) are nicely expressible this way. Note that q[n]b is (roughly) inverse to b[n]q. It's also natural to generalize the idea of "basis" so as to cover the likes of F[n]2, the so-called "fibbinary" numbers (A003714) and provide standard ready-made images of entities obeying other arithmetics, say like GF2[n]2 (e.g., primes = A014580, squares = the present sequence, etc.). - Marc LeBrun, Mar 24 2005
a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - Henry Bottomley, Jul 03 2001
Numbers k such that A004117(k) is odd. - Pontus von Brömssen, Nov 25 2008
Fixed point of the morphism: 0 -> 01; 1 -> 45; 2 -> 89; ...; n -> (4n)(4n+1), starting from a(0)=0. - Philippe Deléham, Oct 22 2011
If n is even and present, so is n+1. - Robert G. Wilson v, Oct 24 2014
Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - M. F. Hasler, Oct 16 2018
Named after the Austrian-Canadian mathematician Leo Moser (1921-1970) and the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 19 2021
Conjecture: The sums of distinct powers of k > 2 can be constructed as the following (k-1)-ary rooted tree. For each n the tree grows and a(n) is then the total number of nodes. For n = 1, the root of the tree is added. For n > 1, if n is odd one leaf of depth n-2 grows one child. If n is even all leaves of depth >= (n - 1 - A000225(A001511(n/2))) grow the maximum number of children. An illustration is provided in the links. - John Tyler Rascoe, Oct 09 2022

			G.f.: x + 4*x^2 + 5*x^3 + 16*x^4 + 17*x^5 + 20*x^6 + 21*x^7 + 64*x^8 + ...
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = 4^4 + 4^3 + 4 + 1 = 325; k = b_0 + b_2*2 + b_4*2^2 = 5, l = b_1 + b_3*2 = 3, such that a(5)=17, a(3)=5 and 27 = 17 + 2*5. - _Vladimir Shevelev_, Nov 10 2008

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1023
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
David Applegate, Marc LeBrun and N. J. A. Sloane, Carryless Arithmetic (I): The Mod 10 Version.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq., Vol. 14 (2011), Article 11.9.8.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 59-60, pp. 750-751.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., Vol. 18, No. 88 (1964), pp. 537-546.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22, No. 2 (2015), #P2.24.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
S. J. Eigen, Y. Ito, and V. S. Prasad, Universally bad integers and the 2-adics, J. Number Theory, Vol. 107, No. 2 (2004), pp. 322-334.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 44.
Bin Lan and James A. Sellers, Properties of a Restricted Binary Partition Function a la Andrews and Lewis, Electronic Journal of Combinatorial Number Theory, Volume 15 #A23.
Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018. See m(n) p. 11.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38. [Annotated scanned copy]
John Tyler Rascoe, Illustration of terms.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016-2017.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Stephen Nicholas Swatman, Ana-Lucia Varbanescu, Andy D. Pimentel, Andreas Salzburger, and Attila Krasznahorkay, Finding Morton-Like Layouts for Multi-Dimensional Arrays Using Evolutionary Algorithms, arXiv:2309.07002 [cs.NE], 2023.
Eric Weisstein's World of Mathematics, Moser-de Bruijn Sequence.
Eric Weisstein's World of Mathematics, Negabinary.
Wikipedia, Morton code. (also known as Z-order curve. Cf. Marc LeBrun's comments about binary interleaving.)
Index entries for 2-automatic sequences.

For generating functions Product_{k>=0} (1 + a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
Main diagonal of A048720, second column of A048723.
Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
A062880(n) = 2*a(n); A001196(n) = 3*a(n).
Row 4 of array A104257.

uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* Falk Hüffner, Jan 24 2022 */

a000695 n = if n == 0 then 0 else 4 * a000695 n' + b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014, Dec 03 2011

function a(n)
    m, r, b = n, 0, 1
    while m > 0
        m, q = divrem(m, 2)
        r += b * q
        b *= 4
    end
r end; [a(n) for n in 0:51] |> println # Peter Luschny, Jan 03 2021

m:=60; R:=PowerSeriesRing(Integers(), m); [0] cat Coefficients(R!( (&+[4^k*x^(2^k)/(1+x^(2^k)): k in [0..20]])/(1-x) )); // G. C. Greubel, Dec 06 2018

a:= proc(n) local m, r, b; m, r, b:= n, 0, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 16 2013

Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* Jacob A. Siehler, Jun 30 2010 *)
Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* IWABUCHI Yu(u)ki, Apr 06 2013 *)
Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* Robert G. Wilson v, Aug 30 2014 *)
Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* Robert G. Wilson v, Oct 24 2014 *)
Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* Harvey P. Dale, Oct 03 2015 *)
a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* Michael Somos, Nov 30 2016 *)

a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ Charles R Greathouse IV, Mar 04 2013

{a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* Michael Somos, Nov 30 2016 */

A000695(n)=fromdigits(binary(n),4) \\ M. F. Hasler, Oct 16 2018

def a(n):
    n = bin(n)[2:]
    x = len(n)
    return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x))
[a(n) for n in range(101)] # Indranil Ghosh, Jun 25 2017

def a():
    x = 0
    while True:
        yield x
        y = ~(x << 1)
        x = (x - y) & y # Falk Hüffner, Dec 21 2021

from itertools import count, islice
def A000695_gen(): # generator of terms
    yield (a:=0)
    for n in count(1):
        yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3)
A000695_list = list(islice(A000695_gen(),30)) # Chai Wah Wu, Feb 22 2023

def A000695(n): return int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

s=(sum(4^k*x^(2^k)/(1+x^(2^k)) for k in range(10))/(1-x)).series(x, 60); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 06 2018

G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003
Numbers k such that the coefficient of x^k is > 0 in Product_{n>=0} 1+x^(4^n). - Benoit Cloitre, Jul 29 2003
For n >= 1, a(n) = a(n-1) + (4^t+2)/6, where t is such that 2^t||2n,or t=A007814(2n). a(n) = (A145812(n+1) - 1)/2. - Vladimir Shevelev, Nov 07 2008
To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_j*2^(2j). The Diophantine equation a(k)+2a(l)=n has the unique solution: k=Sum b_(2j)*2^j, l=Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 10 2008
If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - Vladimir Shevelev, Nov 21 2008
Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - Joerg Arndt, May 12 2010
a(n+1) = (a(n) + 1/3) & -1/3, where & is bitwise AND, -1/3 is represented as the infinite dyadic ...010101 (just as -1 is ...111111 in two's complement) and +1/3 is ...101011. - Marc LeBrun, Sep 30 2010
a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - Philippe Deléham, Oct 18 2011
A182560(6*a(n)) = 0. - Reinhard Zumkeller, May 05 2012
G.f.: x/(1-x^2) + 4*x^2/((1-x)*(W(0) - 4*x - 4*x^2)), where W(k) = 1 + 4*x^(2^k) + 5*x^(2^(k+1)) - 4*x^(2^(k+1))*(1 + x^(2^(k+1)))^2/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 04 2014
liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - Gheorghe Coserea, Sep 15 2015
Let f(x) = (Sum_{k=-oo..oo} floor(x*2^k)/4^k)/2. Then f(x) is a real-valued extension of a(n), which a(n) approximates in the sense that f(x) = lim_{k->oo} a(floor(x*2^k))/a(2^k). - Velin Yanev, Nov 28 2016
G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - Michael Somos, Nov 30 2016
a(2^k) = 4^k = A000302(k). a(n + 2^k) = a(n) + a(2^k) for 2^k > n >= 1. - David A. Corneth, Oct 16 2018
Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

A002426 Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.

Original entry on oeis.org

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of ordered trees with n + 1 edges, having root of odd degree and nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 02 2002
Number of paths of length n with steps U = (1,1), D = (1,-1) and H = (1,0), running from (0,0) to (n,0) (i.e., grand Motzkin paths of length n). For example, a(3) = 7 because we have HHH, HUD, HDU, UDH, DUH, UHD and DHU. - Emeric Deutsch, May 31 2003
Number of lattice paths from (0,0) to (n,n) using steps (2,0), (0,2), (1,1). It appears that 1/sqrt((1 - x)^2 - 4*x^s) is the g.f. for lattice paths from (0,0) to (n,n) using steps (s,0), (0,s), (1,1). - Joerg Arndt, Jul 01 2011
Number of lattice paths from (0,0) to (n,n) using steps (1,0), (1,1), (1,2). - Joerg Arndt, Jul 05 2011
Binomial transform of A000984, with interpolated zeros. - Paul Barry, Jul 01 2003
Number of leaves in all 0-1-2 trees with n edges, n > 0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) - Emeric Deutsch, Nov 30 2003
a(n) is the number of UDU-free paths of n + 1 upsteps (U) and n downsteps (D) that start U. For example, a(2) = 3 counts UUUDD, UUDDU, UDDUU. - David Callan, Aug 18 2004
Diagonal sums of triangle A063007. - Paul Barry, Aug 31 2004
Number of ordered ballots from n voters that result in an equal number of votes for candidates A and B in a three candidate election. Ties are counted even when candidates A and B lose the election. For example, a(3) = 7 because ballots of the form (voter-1 choice, voter-2 choice, voter-3 choice) that result in equal votes for candidates A and B are the following: (A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A) and (C,C,C). - Dennis P. Walsh, Oct 08 2004
a(n) is the number of weakly increasing sequences (a_1,a_2,...,a_n) with each a_i in [n]={1,2,...,n} and no element of [n] occurring more than twice. For n = 3, the sequences are 112, 113, 122, 123, 133, 223, 233. - David Callan, Oct 24 2004
Note that n divides a(n+1) - a(n). In fact, (a(n+1) - a(n))/n = A007971(n+1). - T. D. Noe, Mar 16 2005
Row sums of triangle A105868. - Paul Barry, Apr 23 2005
Number of paths of length n with steps U = (1,1), D = (1,-1) and H = (1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having no H steps on the x-axis. Example: a(3) = 7 because we have UDU, UHD, UHH, UHU, UUD, UUH and UUU. - Emeric Deutsch, Oct 07 2007
Equals right border of triangle A152227; starting with offset 1, the row sums of triangle A152227. - Gary W. Adamson, Nov 29 2008
Starting with offset 1 = iterates of M * [1,1,1,...] where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 07 2009
Hankel transform is 2^n. - Paul Barry, Aug 05 2009
a(n) is prime for n = 2, 3 and 4, with no others for n <= 10^5 (E. W. Weisstein, Mar 14 2005). It has apparently not been proved that no [other] prime central trinomials exist. - Jonathan Vos Post, Mar 19 2010
a(n) is not divisible by 3 for n whose base-3 representation contains no 2 (A005836).
a(n) = number of (n-1)-lettered words in the alphabet {1,2,3} with as many occurrences of the substring (consecutive subword) [1,2] as those of [2,1]. See the papers by Ekhad-Zeilberger and Zeilberger. - N. J. A. Sloane, Jul 05 2012
a(n) = coefficient of x^n in (1 + x + x^2)^n. - L. Edson Jeffery, Mar 23 2013
a(n) is the number of ordered pairs (A,B) of subsets of {1,2,...,n} such that (i.) A and B are disjoint and (ii.) A and B contain the same number of elements. For example, a(2) = 3 because we have: ({},{}) ; ({1},{2}) ; ({2},{1}). - Geoffrey Critzer, Sep 04 2013
Also central terms of A082601. - Reinhard Zumkeller, Apr 13 2014
a(n) is the number of n-tuples with entries 0, 1, or 2 and with the sum of entries equal to n. For n=3, the seven 3-tuples are (1,1,1), (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), and (2,1,0). - Dennis P. Walsh, May 08 2015
The series 2*a(n) + 3*a(n+1) + a(n+2) = 2*A245455(n+3) has Hankel transform of L(2n+1)*2^n, offset n = 1, L being a Lucas number, see A002878 (empirical observation). - Tony Foster III, Sep 05 2016
The series (2*a(n) + 3*a(n+1) + a(n+2))/2 = A245455(n+3) has Hankel transform of L(2n+1), offset n=1, L being a Lucas number, see A002878 (empirical observation). - Tony Foster III, Sep 05 2016
Conjecture: An integer n > 3 is prime if and only if a(n) == 1 (mod n^2). We have verified this for n up to 8*10^5, and proved that a(p) == 1 (mod p^2) for any prime p > 3 (cf. A277640). - Zhi-Wei Sun, Nov 30 2016
This is the analog for Coxeter type B of Motzkin numbers (A001006) for Coxeter type A. - F. Chapoton, Jul 19 2017
a(n) is also the number of solutions to the equation x(1) + x(2) + ... + x(n) = 0, where x(1), ..., x(n) are in the set {-1,0,1}. Indeed, the terms in (1 + x + x^2)^n that produce x^n are of the form x^i(1)*x^i(2)*...*x^i(n) where i(1), i(2), ..., i(n) are in {0,1,2} and i(1) + i(2) + ... + i(n) = n. By setting j(t) = i(t) - 1 we obtain that j(1), ..., j(n) satisfy j(1) + ... + j(n) =0 and j(t) in {-1,0,1} for all t = 1..n. - Lucien Haddad, Mar 10 2018
If n is a prime greater than 3 then a(n)-1 is divisible by n^2. - Ira M. Gessel, Aug 08 2021
Let f(m) = ceiling((q+log(q))/log(9)), where q = -log(log(27)/(2*m^2*Pi)) then f(a(n)) = n, for n > 0. - Miko Labalan, Oct 07 2024
Diagonal of the rational function 1 / (1 - x^2 - y^2 - x*y). - Ilya Gutkovskiy, Apr 23 2025

			For n = 2, (x^2 + x + 1)^2 = x^4 + 2*x^3 + 3*x^2 + 2*x + 1, so a(2) = 3. - _Michael B. Porter_, Sep 06 2016

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 78 and 163, #19.
L. Euler, Exemplum Memorabile Inductionis Fallacis, Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 15, p. 59.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 575.
P. Henrici, Applied and Computational Complex Analysis. Wiley, NY, 3 vols., 1974-1986. (Vol. 1, p. 42.)
Shara Lalo and Zagros Lalo, Polynomial Expansion Theorems and Number Triangles, Zana Publishing, 2018, ISBN: 978-1-9995914-0-3, pp. 579.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 74.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 6.3.8.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 22.
Lin Yang and S.-L. Yang, The parametric Pascal rhombus. Fib. Q., 57:4 (2019), 337-346. See p. 341.

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
George E. Andrews, Three aspects of partitions, Séminaire Lotharingien de Combinatoire, B25f (1990), 1 p.
George E. Andrews, Euler's 'exemplum memorabile inductionis fallacis' and q-trinomial coefficients, J. Amer. Math. Soc. 3 (1990) 653-669.
Armen G. Bagdasaryan and Ovidiu Bagdasar, On some results concerning generalized arithmetic triangles, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 71-77.
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
Frank R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
N. M. Bogoliubov, Enumerative combinatorics of XX0 Heisenberg chain, Scientific Notes, POMI Workshops, Russian Academy of Sciences (St. Petersburg, Russia, 2019), Vol. 487.
Jan Bok, Graph-indexed random walks on special classes of graphs, arXiv:1801.05498 [math.CO], 2018.
Johann Cigler, Some nice Hankel determinants. arXiv preprint arXiv:1109.1449 [math.CO], 2011.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
Steffen Eger, Restricted Weighted Integer Compositions and Extended Binomial Coefficients, J. Integer. Seq., Vol. 16 (2013), #13.1.3. - From _N. J. A. Sloane_, Feb 03 2013
Steffen Eger, Stirling's Approximation for Central Extended Binomial Coefficients, American Mathematical Monthly, 121 (2014), 344-349.
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207 [math.CO], 2011.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014) #14.1.5
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011.
Francesc Fite and Andrew V. Sutherland, Sato-Tate distributions of twists of y^2=x^5-x and y^2=x^6+1, arXiv preprint arXiv:1203.1476 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 14 2012
Rigoberto Flórez, Leandro Junes and José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
R. K. Guy, editor, Western Number Theory Problems, 1985-12-21 & 23, Typescript, Jul 13 1986, Dept. of Math. and Stat., Univ. Calgary, 11 pages. Annotated scan of pages 1, 3, 7, 9, with permission. See Problem 85:03.
R. K. Guy, Letter to N. J. A. Sloane, 1987
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990) 3-20, esp. 18-19.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
V. E. Hoggatt, Jr. and M. Bicknell, Diagonal sums of generalized Pascal triangles, Fib. Quart., 7 (1969), 341-358, 393.
Po-Yi Huang, Shu-Chung Liu, and Yeong-Nan Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
Cynthia Huffman, Analytical Observations (Translation of E326), Euleriana (2023) Vol. 3, Issue 1.
Anders Hyllengren, Four integer sequences, Oct 04 1985. Observes essentially that A000984 and A002426 are inverse binomial transforms of each other, as are A000108 and A001006.
Veronika Irvine, Stephen Melczer and Frank Ruskey, Vertically constrained Motzkin-like paths inspired by bobbin lace, arXiv:1804.08725 [math.CO], 2018.
L. Kleinrock, Uniform permutation of sequences, JPL Space Programs Summary, Vol. 37-64-III, Apr 30, 1970, pp. 32-43. [Annotated scanned copy]
Nadav Kohen, Density and Symmetry in the Generalized Motzkin Numbers mod p, arXiv:2411.03681 [math.CO], 2024. See p. 2.
Dmitry Kruchinin and Vladimir Kruchinin, A Generating Function for the Diagonal T2n,n in Triangles, Journal of Integer Sequence, Vol. 18 (2015), article 15.4.6.
Shara Lalo and Zagros Lalo, Formula for the Central terms in triangle A027907 ((1 + x + x^2)^n).
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Andrew Lohr, Several Topics in Experimental Mathematics, arXiv:1805.00076 [math.CO], 2018.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See pp. 28, 32.
Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.
Thorsten Neuschel, A Note on Extended Binomial Coefficients, J. Int. Seq. 17 (2014) # 14.10.4.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
Paul Peart and Wen-Jin Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Ed. Pegg, Jr., Number of combinations of n coins when have 3 kinds of coin
E. Pergola, R. Pinzani, S. Rinaldi and R. A. Sulanke, A bijective approach to the area of generalized Motzkin paths, Adv. Appl. Math., 28, 2002, 580-591.
José L. Ramírez, The Pascal Rhombus and the Generalized Grand Motzkin Paths, arXiv:1511.04577 [math.CO], 2015.
José L. Ramírez and Víctor F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Dan Romik, Some formulas for the central trinomial and Motzkin numbers, J. Integer Seqs., Vol. 6, 2003.
Eric Rowland and Reem Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013.
Michelle Rudolph-Lilith and Lyle E. Muller, On an explicit representation of central (2k+1)-nomial coefficients, arXiv preprint arXiv:1403.5942 [math.CO], 2014.
Michelle Rudolph-Lilith and Lyle E. Muller, On a link between Dirichlet kernels and central multinomial coefficients, Discrete Mathematics, Volume 338, Issue 9, Sep 06 2015, Pages 1567-1572.
Jesus Salas and Alan D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009; J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738 [cond-mat.stat-mech]. Mentions this sequence.
Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon C. Woodson, The Riordan group, Discrete Applied Math., 34 (1991), 229-239.
T. Sillke, Middle Trinomial Coefficient
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
Robert A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
Zhi-Wei Sun, Conjectures involving combinatorial sequences, arXiv preprint arXiv:1208.2683 [math.CO], 2012. - _N. J. A. Sloane_, Dec 25 2012
Zhi-Wei Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258. - _N. J. A. Sloane_, Dec 28 2012
Zhi-Wei Sun, On central trinomial coefficients, Question 491563 at MathOverflow, April 23, 2025.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 96.
Dennis P. Walsh, The Probability of a Tie in a Three Candidate Election.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.
Chenying Wang, Piotr Miska, and István Mező, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.
Chen Wang, Supercongruences and hypergeometric transformations, arXiv:2003.09888 [math.NT], 2020.
Chen Wang and Zhi-Wei Sun, Congruences involving central trinomial coefficients, arXiv:1910.06850 [math.NT], 2019.
Eric Weisstein's World of Mathematics, Central Trinomial Coefficient and Trinomial Coefficient.
Doron Zeilberger, Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610 for ALL pairs of words of length, 2, in an alphabet of, 3 letters. See Proposition 5.
Doron Zeilberger, Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610 for ALL pairs of words of length, 2, in an alphabet of, 3 letters. [Local copy]
Index entries for sequences of k-nomial coefficients
Index entries for "core" sequences

INVERT transform is A007971. Partial sums are A097893. Squares are A168597.
Main column of A027907. Column k=2 of A305161. Column k=0 of A328347. Column 1 of A201552(?).
Cf. A001006, A002878, A005043, A005717, A082758 (bisection), A273055 (bisection), A102445, A113302, A113303, A113304, A113305 (divisibility of central trinomial coefficients), A152227, A277640.

a002426 n = a027907 n n  -- Reinhard Zumkeller, Jan 22 2013

P:=PolynomialRing(Integers()); [Max(Coefficients((1+x+x^2)^n)): n in [0..26]]; // Bruno Berselli, Jul 05 2011

A002426 := proc(n) local k;
    sum(binomial(n, k)*binomial(n-k, k), k=0..floor(n/2));
end proc: # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
# Alternatively:
a := n -> simplify(GegenbauerC(n,-n,-1/2)):
seq(a(n), n=0..29); # Peter Luschny, May 07 2016

Table[ CoefficientList[ Series[(1 + x + x^2)^n, {x, 0, n}], x][[ -1]], {n, 0, 27}] (* Robert G. Wilson v *)
a=b=1; Join[{a,b}, Table[c=((2n-1)b + 3(n-1)a)/n; a=b; b=c; c, {n,2,100}]]; Table[Sqrt[-3]^n LegendreP[n,1/Sqrt[-3]],{n,0,26}] (* Wouter Meeussen, Feb 16 2013 *)
a[ n_] := If[ n < 0, 0, 3^n Hypergeometric2F1[ 1/2, -n, 1, 4/3]]; (* Michael Somos, Jul 08 2014 *)
Table[4^n *JacobiP[n,-n-1/2,-n-1/2,-1/2], {n,0,29}] (* Peter Luschny, May 13 2016 *)
a[n_] := a[n] = Sum[n!/((n - 2*i)!*(i!)^2), {i, 0, n/2}]; Table[a[n], {n, 0, 29}] (* Shara Lalo and Zagros Lalo, Oct 03 2018 *)

trinomial(n,k):=coeff(expand((1+x+x^2)^n),x,k);
makelist(trinomial(n,n),n,0,12); /* Emanuele Munarini, Mar 15 2011 */

makelist(ultraspherical(n,-n,-1/2),n,0,12); /* Emanuele Munarini, Dec 20 2016 */

{a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n))};

/* as lattice paths: same as in A092566 but use */
steps=[[2, 0], [0, 2], [1, 1]];
/* Joerg Arndt, Jul 01 2011 */

a(n)=polcoeff(sum(m=0, n, (2*m)!/m!^2 * x^(2*m) / (1-x+x*O(x^n))^(2*m+1)), n) \\ Paul D. Hanna, Sep 21 2013

from math import comb
def A002426(n): return sum(comb(n,k)*comb(k,n-k) for k in range(n+1)) # Chai Wah Wu, Nov 15 2022

A002426 = lambda n: hypergeometric([-n/2, (1-n)/2], [1], 4)
[simplify(A002426(n)) for n in (0..29)]
# Peter Luschny, Sep 17 2014

def A():
    a, b, n = 1, 1, 1
    yield a
    while True:
        yield b
        n += 1
        a, b = b, ((3 * (n - 1)) * a + (2 * n - 1) * b) // n
A002426 = A()
print([next(A002426) for  in range(30)])  # _Peter Luschny, May 16 2016

G.f.: 1/sqrt(1 - 2*x - 3*x^2).
E.g.f.: exp(x)*I_0(2x), where I_0 is a Bessel function. - Michael Somos, Sep 09 2002
a(n) = 2*A027914(n) - 3^n. - Benoit Cloitre, Sep 28 2002
a(n) is asymptotic to d*3^n/sqrt(n) with d around 0.5.. - Benoit Cloitre, Nov 02 2002, d = sqrt(3/Pi)/2 = 0.4886025119... - Alec Mihailovs (alec(AT)mihailovs.com), Feb 24 2005
D-finite with recurrence: a(n) = ((2*n - 1)*a(n-1) + 3*(n - 1)*a(n-2))/n; a(0) = a(1) = 1; see paper by Barcucci, Pinzani and Sprugnoli.
Inverse binomial transform of A000984. - Vladeta Jovovic, Apr 28 2003
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(k, k/2)*(1 + (-1)^k)/2; a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*binomial(2*k, k). - Paul Barry, Jul 01 2003
a(n) = Sum_{k>=0} binomial(n, 2*k)*binomial(2*k, k). - Philippe Deléham, Dec 31 2003
a(n) = Sum_{i+j=n, 0<=j<=i<=n} binomial(n, i)*binomial(i, j). - Benoit Cloitre, Jun 06 2004
a(n) = 3*a(n-1) - 2*A005043(n). - Joost Vermeij (joost_vermeij(AT)hotmail.com), Feb 10 2005
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(k, n-k). - Paul Barry, Apr 23 2005
a(n) = (-1/4)^n*Sum_{k=0..n} binomial(2*k, k)*binomial(2*n-2*k, n-k)*(-3)^k. - Philippe Deléham, Aug 17 2005
a(n) = A111808(n,n). - Reinhard Zumkeller, Aug 17 2005
a(n) = Sum_{k=0..n} (((1 + (-1)^k)/2)*Sum_{i=0..floor((n-k)/2)} binomial(n, i)*binomial(n-i, i+k)*((k + 1)/(i + k + 1))). - Paul Barry, Sep 23 2005
a(n) = 3^n*Sum_{j=0..n} (-1/3)^j*C(n, j)*C(2*j, j); follows from (a) in A027907. - Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006
a(n) = (1/2)^n*Sum_{j=0..n} 3^j*binomial(n, j)*binomial(2*n-2*j, n) = (3/2)^n*Sum_{j=0..n} (1/3)^j*binomial(n, j)*binomial(2*j, n); follows from (c) in A027907. - Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006
a(n) = (1/Pi)*Integral_{x=-1..3} x^n/sqrt((3 - x)*(1 + x)) is moment representation. - Paul Barry, Sep 10 2007
G.f.: 1/(1 - x - 2x^2/(1 - x - x^2/(1 - x - x^2/(1 - ... (continued fraction). - Paul Barry, Aug 05 2009
a(n) = sqrt(-1/3)*(-1)^n*hypergeometric([1/2, n+1], [1], 4/3). - Mark van Hoeij, Nov 12 2009
a(n) = (1/Pi)*Integral_{x=-1..1} (1 + 2*x)^n/sqrt(1 - x^2) = (1/Pi)*Integral_{t=0..Pi} (1 + 2*cos(t))^n. - Eli Wolfhagen, Feb 01 2011
In general, g.f.: 1/sqrt(1 - 2*a*x + x^2*(a^2 - 4*b)) = 1/(1 - a*x)*(1 - 2*x^2*b/(G(0)*(a*x - 1) + 2*x^2*b)); G(k) = 1 - a*x - x^2*b/G(k+1); for g.f.: 1/sqrt(1 - 2*x - 3*x^2) = 1/(1 - x)*(1 - 2*x^2/(G(0)*(x - 1) + 2*x^2)); G(k) = 1 - x - x^2/G(k+1), a = 1, b = 1; (continued fraction). - Sergei N. Gladkovskii, Dec 08 2011
a(n) = Sum_{k=0..floor(n/3)} (-1)^k*binomial(2*n-3*k-1, n-3*k)*binomial(n, k). - Gopinath A. R., Feb 10 2012
G.f.: A(x) = x*B'(x)/B(x) where B(x) satisfies B(x) = x*(1 + B(x) + B(x)^2). - Vladimir Kruchinin, Feb 03 2013 (B(x) = x*A001006(x) - Michael Somos, Jul 08 2014)
G.f.: G(0), where G(k) = 1 + x*(2 + 3*x)*(4*k + 1)/(4*k + 2 - x*(2 + 3*x)*(4*k + 2)*(4*k + 3)/(x*(2 + 3*x)*(4*k + 3) + 4*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013
E.g.f.: exp(x) * Sum_{k>=0} (x^k/k!)^2. - Geoffrey Critzer, Sep 04 2013
G.f.: Sum_{n>=0} (2*n)!/n!^2*(x^(2*n)/(1 - x)^(2*n+1)). - Paul D. Hanna, Sep 21 2013
0 = a(n)*(9*a(n+1) + 9*a(n+2) - 6*a(n+3)) + a(n+1)*(3*a(n+1) + 4*a(n+2) - 3*a(n+3)) + a(n+2)*(-a(n+2) + a(n+3)) for all n in Z. - Michael Somos, Jul 08 2014
a(n) = hypergeometric([-n/2, (1-n)/2], [1], 4). - Peter Luschny, Sep 17 2014
a(n) = A132885(n,0), that is, a(n) = A132885(A002620(n+1)). - Altug Alkan, Nov 29 2015
a(n) = GegenbauerC(n,-n,-1/2). - Peter Luschny, May 07 2016
a(n) = 4^n*JacobiP[n,-n-1/2,-n-1/2,-1/2]. - Peter Luschny, May 13 2016
From Alexander Burstein, Oct 03 2017: (Start)
G.f.: A(4*x) = B(-x)*B(3*x), where B(x) is the g.f. of A000984.
G.f.: A(2*x)*A(-2*x) = B(x^2)*B(9*x^2).
G.f.: A(x) = 1 + x*M'(x)/M(x), where M(x) is the g.f. of A001006. (End)
a(n) = Sum_{i=0..n/2} n!/((n - 2*i)!*(i!)^2). [Cf. Lalo and Lalo link. It is Luschny's terminating hypergeometric sum.] - Shara Lalo and Zagros Lalo, Oct 03 2018
From Peter Bala, Feb 07 2022: (Start)
a(n)^2 = Sum_{k = 0..n} (-3)^(n-k)*binomial(2*k,k)^2*binomial(n+k,n-k) and has g.f. Sum_{n >= 0} binomial(2*n,n)^2*x^n/(1 + 3*x)^(2*n+1). Compare with the g.f. for a(n) given above by Hanna.
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all prime p and positive integers n and k.
Conjecture: The stronger congruences a(n*p^k) == a(n*p^(k-1)) (mod p^(2*k)) hold for all prime p >= 5 and positive integers n and k. (End)
a(n) = A005043(n) + A005717(n) for n >= 1. - Amiram Eldar, May 17 2024
For even n, a(n) = (n-1)!!* 2^{n/2}/ (n/2)!* 2F1(-n/2,-n/2;1/2;1/4). For odd n, a(n) = n!! *2^(n/2-1/2) / (n/2-1/2)! * 2F1(1/2-n/2,1/2-n/2;3/2;1/4). - R. J. Mathar, Mar 19 2025

A001316 Gould's sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal's triangle (A007318); a(n) = 2^A000120(n).

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32

Offset: 0

N. J. A. Sloane

Also called Dress's sequence.
This sequence might be better called Glaisher's sequence, since James Glaisher showed that odd binomial coefficients are counted by 2^A000120(n) in 1899. - Eric Rowland, Mar 17 2017 [However, the name "Gould's sequence" is deeply entrenched in the literature. - N. J. A. Sloane, Mar 17 2017] [Named after the American mathematician Henry Wadsworth Gould (b. 1928). - Amiram Eldar, Jun 19 2021]
All terms are powers of 2. The first occurrence of 2^k is at n = 2^k - 1; e.g., the first occurrence of 16 is at n = 15. - Robert G. Wilson v, Dec 06 2000
a(n) is the highest power of 2 dividing binomial(2n,n) = A000984(n). - Benoit Cloitre, Jan 23 2002
Also number of 1's in n-th row of triangle in A070886. - Hans Havermann, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90, starting with a single live cell. - Ben Branman, Feb 28 2009. Ditto for Rule 18. - N. J. A. Sloane, Aug 09 2014. This is also the odd-rule cellular automaton defined by OddRule 003 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. - Reinhard Zumkeller, Jan 28 2003
To construct the sequence, start with 1 and use the rule: If k >= 0 and a(0),a(1),...,a(2^k-1) are the first 2^k terms, then the next 2^k terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre, Jan 30 2003
Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004
The odd entries in Pascal's triangle form the Sierpiński Gasket (a fractal). - Amarnath Murthy, Nov 20 2004
Row sums of Sierpiński's Gasket A047999. - Johannes W. Meijer, Jun 05 2011
Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 -> 1224 -> = 12242448 -> 122424482448488(16) -> ... . - Philippe Deléham, Jun 18 2005
a(n) = number of 1's of stage n of the one-dimensional cellular automaton with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 01 2006
a(33)..a(63) = A117973(1)..A117973(31). - Stephen Crowley, Mar 21 2007
Or the number of solutions of the equation: A000120(x) + A000120(n-x) = A000120(n). - Vladimir Shevelev, Jul 19 2009
For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - John M. Campbell, May 26 2011
Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p >= 0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - Johannes W. Meijer, Jun 05 2011
a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - Reinhard Zumkeller, Nov 30 2012
This is the Run Length Transform of S(n) = {1,2,4,8,16,...} (cf. A000079). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014
A105321(n+1) = a(n+1) + a(n). - Reinhard Zumkeller, Nov 14 2014
a(n) = A261363(n,n) = number of distinct terms in row n of A261363 = number of odd terms in row n+1 of A261363. - Reinhard Zumkeller, Aug 16 2015
From Gary W. Adamson, Aug 26 2016: (Start)
A production matrix for the sequence is lim_{k->infinity} M^k, the left-shifted vector of M:
  1, 0, 0, 0, 0, ...
  2, 0, 0, 0, 0, ...
  0, 1, 0, 0, 0, ...
  0, 2, 0, 0, 0, ...
  0, 0, 1, 0, 0, ...
  0, 0, 2, 0, 0, ...
  0, 0, 0, 1, 0, ...
  ...
The result is equivalent to the g.f. of Apr 06 2003: Product_{k>=0} (1 + 2*z^(2^k)). (End)
Number of binary palindromes of length n for which the first floor(n/2) symbols are themselves a palindrome (Ji and Wilf 2008). - Jeffrey Shallit, Jun 15 2017

			Has a natural structure as a triangle:
  1,
  2,
  2,4,
  2,4,4,8,
  2,4,4,8,4,8,8,16,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32,64,
  ...
The rows converge to A117973.
From _Omar E. Pol_, Jun 07 2009: (Start)
Also, triangle begins:
   1;
   2,2;
   4,2,4,4;
   8,2,4,4,8,4,8,8;
  16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;
  32,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32;
  64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,...
(End)
G.f. = 1 + 2*x + 2*x^2 + 4*x^3 + 2*x^4 + 4*x^5 + 4*x^6 + 8*x^7 + 2*x^8 + ... - _Michael Somos_, Aug 26 2015

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, p. 75ff.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.
James W. L. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quarterly Journal of Pure and Applied Mathematics, Vol. 30 (1899), pp. 150-156.
H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sep 1961.
Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, Algebraic properties of cellular automata, Comm. Math. Physics, Vol. 93 (1984), pp. 219-258. Reprinted in Theory and Applications of Cellular Automata, S Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113
Manfred R. Schroeder, Fractals, Chaos, Power Laws, W. H. Freeman, NY, 1991, page 383.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Andrew Wuensche, Exploring Discrete Dynamics, Luniver Press, 2011. See Fig. 2.3.

Indranil Ghosh, Table of n, a(n) for n = 0..50000 (terms 0..1000 from T. D. Noe)
David Applegate, Omar E. Pol, and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Christina Talar Bekaroğlu, Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry, Master's thesis, Calif. State Univ. Northridge (2023). See pp. 91-92.
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1, Article 1.
Neil J. Calkin, Eunice Y. S. Chan, Robert M. Corless, David J. Jeffrey, and Piers W. Lawrence, A Fractal Eigenvector, arXiv:2104.01116 [math.DS], 2021.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory, Vol. 117 (2006), pp. 191-215.
Philippe Dumas, Diviser pour régner Comportement asymptotique.
Philippe Dumas, Diviser pour régner Comportement asymptotique. (has many references)
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
Steven R. Finch, Stolarsky-Harborth Constant. [Broken link]
Steven R. Finch, Stolarsky-Harborth Constant. [From the Wayback machine]
Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 28.
Michael Gilleland, Some Self-Similar Integer Sequences.
Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1, 2, ..., k}, arXiv:2307.07733 [math.CO], 2023.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, Amer. Math. Monthly, Vol. 115, No. 5 (2008), pp. 447-451.
Alan J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata....
Hans Montanus and Ron Westdijk, Cellular Automation and Binomials, Green Blue Mathematics (2022), p. 57.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
Tomaz Pisanski and Thomas W. Tucker, Growth in Repeated Truncations of Maps, Atti Sem. Mat. Fis. Univ. Modena, Vol. 49 (2001), suppl., pp. 167-176.
David G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., Vol. 67, No. 5 (1994), pp. 323-344.
Joseph M. Shunia, A Polynomial Ring Connecting Central Binomial Coefficients and Gould's Sequence, arXiv:2312.00302 [math.GM], 2023.
N. J. A. Sloane, Illustration of first 20 generations of Rule 90.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.
Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of two, arXiv:1710.10884 [math.NT], 2017.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 12.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
Stephen Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., Vol. 55 (1983), pp. 601-644.
Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Vol. 91, No. 9 (November 1984), pp. 566-571.
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv preprint arXiv:1610.06166 [math.CO], 2016.
Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).
Index entries for sequences related to cellular automata
Index entries for sequences that are fixed points of mappings
Index entries for sequences computed with run length transform

Equals left border of triangle A166548. - Gary W. Adamson, Oct 16 2009
For generating functions Product_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
For partial sums see A006046. For first differences see A151930.
This is the numerator of 2^n/n!, while A049606 gives the denominator.
Cf. A051638, A048967, A007318, A094959, A048896, A117973, A008977, A139541, A048883, A102376, A038573, A159913, A000079, A166548, A006047, A089898, A105321, A061142.
Cf. A047999, A261363, A261366.
If we subtract 1 from the terms we get a pair of essentially identical sequences, A038573 and A159913.
A163000 and A163577 count binomial coefficients with 2-adic valuation 1 and 2. A275012 gives a measure of complexity of these sequences. - Eric Rowland, Mar 15 2017
Cf. A286575 (run-length transform), A368655 (binomial transform), also A037445.

import Data.List (transpose)
a001316 = sum . a047999_row  -- Reinhard Zumkeller, Nov 24 2012
a001316_list = 1 : zs where
   zs = 2 : (concat $ transpose [zs, map (* 2) zs])
-- Reinhard Zumkeller, Aug 27 2014, Sep 16 2011
(Sage, Python)
from functools import cache
@cache
def A001316(n):
    if n <= 1: return n+1
    return A001316(n//2) << n%2
print([A001316(n) for n in range(88)])  # Peter Luschny, Nov 19 2012

A001316 := proc(n) local k; add(binomial(n,k) mod 2, k=0..n); end;
S:=[1]; S:=[op(S),op(2*s)]; # repeat ad infinitum!
a := n -> 2^add(i,i=convert(n,base,2)); # Peter Luschny, Mar 11 2009

Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]
Nest[ Join[#, 2#] &, {1}, 7] (* Robert G. Wilson v, Jan 24 2006 and modified Jul 27 2014 *)
Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[90,{{1},0},100]] (* Produces counts of ON cells. N. J. A. Sloane, Aug 10 2009 *)
ArrayPlot[CellularAutomaton[90, {{1}, 0}, 20]] (* Illustration of first 20 generations. - N. J. A. Sloane, Aug 14 2014 *)
Table[2^(RealDigits[n - 1, 2][[1]] // Total), {n, 1, 100}] (* Gabriel C. Benamy, Dec 08 2009 *)
CoefficientList[Series[Exp[2*x], {x, 0, 100}], x] // Numerator (* Jean-François Alcover, Oct 25 2013 *)
Count[#,?OddQ]&/@Table[Binomial[n,k],{n,0,90},{k,0,n}] (* _Harvey P. Dale, Sep 22 2015 *)
2^DigitSum[Range[0, 100], 2] (* Paolo Xausa, Jul 31 2025 *)

{a(n) = if( n<0, 0, numerator(2^n / n!))};

PARI
```
A001316(n)=1<M. F. Hasler, May 03 2009
```

a(n)=2^hammingweight(n) \\ Charles R Greathouse IV, Jan 04 2013

def A001316(n):
    return 2**bin(n)[2:].count("1") # Indranil Ghosh, Feb 06 2017

def A001316(n): return 1<Karl-Heinz Hofmann, Aug 01 2025

import numpy # (version >= 2.0.0)
n_up_to = 2**22
A000079 = 1 << numpy.arange(n_up_to.bit_length())
A001316 = A000079[numpy.bitwise_count(numpy.arange(n_up_to))]
print(A001316[0:100]) # Karl-Heinz Hofmann, Aug 01 2025

(define (A001316 n) (let loop ((n n) (z 1)) (cond ((zero? n) z) ((even? n) (loop (/ n 2) z)) (else (loop (/ (- n 1) 2) (* z 2)))))) ;; Antti Karttunen, May 29 2017

a(n) = 2^A000120(n).
a(0) = 1; for n > 0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 2*a(j).
a(n) = 2*a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n).
a(n) = A038573(n) + 1.
G.f.: Product_{k>=0} (1+2*z^(2^k)). - Ralf Stephan, Apr 06 2003
a(n) = Sum_{i=0..2*n} (binomial(2*n, i) mod 2)*(-1)^i. - Benoit Cloitre, Nov 16 2003
a(n) mod 3 = A001285(n). - Benoit Cloitre, May 09 2004
a(n) = 2^n - 2*Sum_{k=0..n} floor(binomial(n, k)/2). - Paul Barry, Dec 24 2004
a(n) = Product_{k=0..log_2(n)} 2^b(n, k), b(n, k) = coefficient of 2^k in binary expansion of n. - Paul D. Hanna
Sum_{k=0..n-1} a(k) = A006046(n).
a(n) = n/2 + 1/2 + (1/2)*Sum_{k=0..n} (-(-1)^binomial(n,k)). - Stephen Crowley, Mar 21 2007
G.f. for a(n)/A156769(n): (1/2)*z^(1/2)*sinh(2*z^(1/2)). - Johannes W. Meijer, Feb 20 2009
Equals infinite convolution product of [1,2,0,0,0,0,0,0,0] aerated (A000079 - 1) times, i.e., [1,2,0,0,0,0,0,0,0] * [1,0,2,0,0,0,0,0,0] * [1,0,0,0,2,0,0,0,0]. - Mats Granvik, Gary W. Adamson, Oct 02 2009
a(n) = f(n, 1) with f(x, y) = if x = 0 then y otherwise f(floor(x/2), y*(1 + x mod 2)). - Reinhard Zumkeller, Nov 21 2009
a(n) = 2^(number of 1's in binary form of (n-1)). - Gabriel C. Benamy, Dec 08 2009
a((2*n+1)*2^p-1) = (2^p)*a(n), p >= 0. - Johannes W. Meijer, Jun 05 2011
a(n) = A000120(A001317(n)). - Reinhard Zumkeller, Nov 24 2012
a(n) = A226078(n,1). - Reinhard Zumkeller, May 25 2013
a(n) = lcm(n!, 2^n) / n!. - Daniel Suteu, Apr 28 2017
a(n) = A061142(A005940(1+n)). - Antti Karttunen, May 29 2017
a(0) = 1, a(2*n) = a(n), a(2*n+1) = 2*a(n). - Daniele Parisse, Feb 15 2024
a(n*m) <= a(n)^A000120(m). - Joe Amos, Mar 27 2025

Additional comments from Henry Bottomley, Mar 12 2001

Further comments from N. J. A. Sloane, May 30 2009

A034472 a(n) = 3^n + 1.

Original entry on oeis.org

2, 4, 10, 28, 82, 244, 730, 2188, 6562, 19684, 59050, 177148, 531442, 1594324, 4782970, 14348908, 43046722, 129140164, 387420490, 1162261468, 3486784402, 10460353204, 31381059610, 94143178828, 282429536482, 847288609444, 2541865828330, 7625597484988

Offset: 0

N. J. A. Sloane

Companion numbers to A003462.
a(n) = A024101(n)/A024023(n). - Reinhard Zumkeller, Feb 14 2009
Mahler exhibits this sequence with n>=2 as a proof that there exists an infinite number of x coprime to 3, such that x belongs to A005836 and x^2 belong to A125293. - Michel Marcus, Nov 12 2012
a(n-1) is the number of n-digit base 3 numbers that have an even number of digits 0. - Yifan Xie, Jul 13 2024

			a(3)=28 because 4*a(2)-3*a(1)=4*10-3*4=28 (28 is also 3^3 + 1).
G.f. = 2 + 4*x + 10*x^2 + 28*x^3 + 82*x^4 + 244*x^5 + 730*x^5 + ...

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 148 and 220, Problem 191.
P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, pp. 35-36, 53.

T. D. Noe, Table of n, a(n) for n=0..200
T. A. Gulliver, Divisibility of sums of powers of odd integers, Int. Math. For. 5 (2010) 3059-3066, eq 5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 454
Kurt Mahler, The representation of squares to the base 3, Acta Arith. Vol. 53, Issue 1 (1989), p. 99-106.
Burkard Polster, Special numbers in 3-coloring of Pascal's triangle, Mathologer video (2019).
Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
D. Suprijanto and I. W. Suwarno, Observation on Sums of Powers of Integers Divisible by 3k-1, Applied Mathematical Sciences, Vol. 8, 2014, no. 45, 2211 - 2217.
Eric Weisstein's World of Mathematics, Lucas Sequence
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A003462, A000204, A007051, A000051, A052539, A034474, A062394, A034491, A062395, A062396, A062397, A007689, A063376, A063481, A074600 - A074624, A034524, A178248, A228081, A279396.

[3^n+1: n in [0..30]]; // Vincenzo Librandi, Jan 11 2017

ZL:= [S, {S=Union(Sequence(Z), Sequence(Union(Z, Z, Z)))}, unlabeled]: seq(combstruct[count](ZL, size=n), n=0..25); # Zerinvary Lajos, Jun 19 2008
g:=1/(1-3*z): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)+1, n=0..31); # Zerinvary Lajos, Jan 09 2009

Mathematica
```
Table[3^n + 1, {n, 0, 24}]
```
PARI
```
a(n) = 3^n + 1
```

Vec(2*(1-2*x)/((1-x)*(1-3*x)) + O(x^50)) \\ Altug Alkan, Nov 15 2015

[lucas_number2(n,4,3) for n in range(27)] # Zerinvary Lajos, Jul 08 2008

[sigma(3,n) for n in range(27)] # Zerinvary Lajos, Jun 04 2009

[3^n+1 for n in range(30)] # Bruno Berselli, Jan 11 2017

a(n) = 3*a(n-1) - 2 = 4*a(n-1) - 3*a(n-2). (Lucas sequence, with A003462, associated to the pair (4, 3).)
G.f.: 2*(1-2*x)/((1-x)*(1-3*x)). Inverse binomial transforms yields 2,2,4,8,16,... i.e., A000079 with the first entry changed to 2. Binomial transform yields A063376 without A063376(-1). - R. J. Mathar, Sep 05 2008
E.g.f.: exp(x) + exp(3*x). - Mohammad K. Azarian, Jan 02 2009
a(n) = A279396(n+3,3). - Wolfdieter Lang, Jan 10 2017
a(n) = 2*A007051(n). - R. J. Mathar, Apr 07 2022

Additional comments from Rick L. Shepherd, Feb 13 2002

A003278 Szekeres's sequence: a(n)-1 in ternary = n-1 in binary; also: a(1) = 1, a(2) = 2, and thereafter a(n) is smallest number k which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k.

Original entry on oeis.org

1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, 112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, 326, 328, 329, 334, 335, 337, 338, 352, 353

Offset: 1

N. J. A. Sloane and Richard Stanley

That is, there are no three elements A, B and C such that B - A = C - B.
Positions of 1's in Richard Stanley's Forest Fire sequence A309890. - N. J. A. Sloane, Dec 01 2019
Subtracting 1 from each term gives A005836 (ternary representation contains no 2's). - N. J. A. Sloane, Dec 01 2019
Difference sequence related to Gray code bit sequence (A001511). The difference patterns follows a similar repeating pattern (ABACABADABACABAE...), but each new value is the sum of the previous values, rather than simply 1 more than the maximum of the previous values. - Hal Burch (hburch(AT)cs.cmu.edu), Jan 12 2004
Sums of distinct powers of 3, translated by 1.
Positions of 0 in A189820; complement of A189822. - Clark Kimberling, May 26 2011
Also, Stanley sequence S(1): see OEIS Index under Stanley sequences (link below). - M. F. Hasler, Jan 18 2016
Named after the Hungarian-Australian mathematician George Szekeres (1911-2005). - Amiram Eldar, May 07 2021
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+3^n). - Arie Bos, Jul 24 2022

			G.f. = x + 2*x^2 + 4*x^3 + 5*x^4 + 10*x^5 + 11*x^6 + 13*x^7 + 14*x^8 + 28*x^9 + ...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 164.
Richard K. Guy, Unsolved Problems in Number Theory, E10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David W. Wilson, Table of n, a(n) for n = 1..10000 [a(1..1024) from T. D. Noe]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Paul Erdős and Paul Turan, On some sequences of integers, J. London Math. Soc., 11 (1936), 261-264.
Joseph Gerver, James Propp and Jamie Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions Proc. Amer. Math. Soc. 102 (1988), no. 3, 765-772.
Fanel Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.
Henry Ibstedt, A Few Smarandache Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.
Gabor Korvin, Short note: Every large set of integers contains a three term arithmetic progression arXiv 1404.1557 [math.NT], Apr 6 2014.
Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group, 2011 (written in 1957). See pp. 61-62.
James Propp and N. J. A. Sloane, Email, March 1994
Florentin Smarandache, Sequences of Numbers Involved in Unsolved Problems.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
Eric Weisstein's World of Mathematics, Smarandache Sequences.
Index entries for sequences related to binary expansion of n
Index entries related to non-averaging sequences
Index entries related to Stanley sequences

Equals 1 + A005836. Cf. A001511, A098871.
Row 0 of array in A093682.
Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
3-term AP: A005836 (>=0), A003278 (>0);
4-term AP: A005839 (>=0), A005837 (>0);
5-term AP: A020654 (>=0), A020655 (>0);
6-term AP: A020656 (>=0), A005838 (>0);
7-term AP: A020657 (>=0), A020658 (>0);
8-term AP: A020659 (>=0), A020660 (>0);
9-term AP: A020661 (>=0), A020662 (>0);
10-term AP: A020663 (>=0), A020664 (>0).
Cf. A003002, A229037 (the Forest Fire sequence), A309890 (Stanley's version).
Similar formula:
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+4^n) produces A098871;
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+2*3^n) produces  A191106.

function a(n)
    return 1 + parse(Int, bitstring(n-1), base=3)
end # Gabriel F. Lipnik, Apr 16 2021

a:= proc(n) local m, r, b; m, r, b:= n-1, 1, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*3 od; r
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Aug 17 2013

Take[ Sort[ Plus @@@ Subsets[ Table[3^n, {n, 0, 6}]]] + 1, 58] (* Robert G. Wilson v, Oct 23 2004 *)
a[1] = 0; h = 180;
Table[a[3 k - 2] = a[k], {k, 1, h}];
Table[a[3 k - 1] = a[k], {k, 1, h}];
Table[a[3 k] = 1, {k, 1, h}];
Table[a[n], {n, 1, h}]   (* A189820 *)
Flatten[Position[%, 0]]  (* A003278 *)
Flatten[Position[%%, 1]] (* A189822 *)
(* A003278 from A189820, from Clark Kimberling, May 26 2011 *)
Table[FromDigits[IntegerDigits[n, 2], 3] + 1, {n, 0, 57}] (* Amit Munje, Jun 03 2018 *)

a(n)=1+sum(i=1,n-1,(1+3^valuation(i,2))/2) \\ Ralf Stephan, Jan 21 2014

$nxt = 1; @list = (); for ($cnt = 0; $cnt < 1500; $cnt++) { while (exists $legal{$nxt}) { $nxt++; } print "$nxt "; last if ($nxt >= 1000000); for ($i = 0; $i <= $#list; $i++) { $t = 2*$nxt - $list[$i]; $legal{$t} = -1; } $cnt++; push @list, $nxt; $nxt++; } # Hal Burch

def A003278(n):
    return int(format(n-1,'b'),3)+1 # Chai Wah Wu, Jan 04 2015

a(2*k + 2) = a(2*k + 1) + 1, a(2^k + 1) = 2*a(2^k).
a(n) = b(n+1) with b(0) = 1, b(2*n) = 3*b(n)-2, b(2*n+1) = 3*b(n)-1. - Ralf Stephan, Aug 23 2003
G.f.: x/(1-x)^2 + x * Sum_{k>=1} 3^(k-1)*x^(2^k)/((1-x^(2^k))*(1-x)). - Ralf Stephan, Sep 10 2003, corrected by Robert Israel, May 25 2011
Conjecture: a(n) = (A191107(n) + 2)/3 = (A055246(n) + 5)/6. - L. Edson Jeffery, Nov 26 2015
a(n) mod 2 = A010059(n). - Arie Bos, Aug 13 2022

If n and k have no common one bit in base 2 representation (n AND k = 0), then n = A289813(T(n,k)) and k = A289814(T(n,k)).

This sequence, when restricted to the pairs of numbers without common bits in base 2 representation, is the inverse of the function n -> (A289813(n), A289814(n)).

Consider the lexicographically earliest sequence of nonnegative numbers that does not contain the arithmetic mean of any pair of terms (such sequences are called 3-free sequences as they do not contain 3-term arithmetic progressions): 0,1,3,4 and so on. This sequence is Stanley sequence S(0,1). Remove numbers in the Stanley sequence from nonnegative integers and repeat the process of finding the earliest 3-free sequence. The result is this sequence.

When written in base three these are numbers that contain exactly one 2 that might be followed by zeros.

cp's OEIS Frontend

A273516 List of arithmetic triples (three numbers in arithmetic progression) derived from pairs of terms in A005836.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A289869 Square array T(n,k) (n>=0, k>=0) read by antidiagonals downwards: T(n,k) = A005836(n) + 2*A005836(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A323398 Lexicographically first 3-free sequence on nonnegative integers not containing the Stanley sequence S(0,1), which is A005836.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A273515 The number of times n is rejected from the Stanley sequence S(0,1), A005836.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A007088 The binary numbers (or binary words, or binary vectors, or binary expansion of n): numbers written in base 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

Sage

Formula