A048896 -id:A048896 - cp's OEIS frontend

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

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

A007931 Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.

Original entry on oeis.org

1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222, 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122

Offset: 1

R. Muller

Numbers written in the dyadic system [Smullyan, Stillwell]. - N. J. A. Sloane, Feb 13 2019
Logic-binary sequence: prefix it by the empty word to have all binary words on the alphabet {1,2}.
The least binary word of length k is a(2^k - 1).
See Mathematica program for logic-binary sequence using (0,1) in place of (1,2); the sequence starts with 0,1,00,01,10. - Clark Kimberling, Feb 09 2012
A007953(a(n)) = A014701(n+1); A007954(a(n)) = A048896(n). - Reinhard Zumkeller, Oct 26 2012
a(n) is n written in base 2 where zeros are not allowed but twos are. The two distinct digits used are 1, 2 instead of 0, 1. To obtain this sequence from the "canonical" base 2 sequence with zeros allowed, just replace any 0 with a 2 and then subtract one from the group of digits situated on the left: (10-->2; 100-->12; 110-->22; 1000-->112; 1010-->122). - Robin Garcia, Jan 31 2014
For numbers made of only two different digits, see also A007088 (digits 0 & 1), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5), A256291 (digits 5 & 6), A256292 (digits 6 & 7), A256340(digits 7 & 8), A256341 (digits 8 & 9), and A032804-A032816 (in other bases). Numbers with exactly two distinct (but unspecified) digits in base 10 are listed in A031955, for other bases in A031948-A031954. - M. F. Hasler, Apr 04 2015
The variant with digits {0, 1} instead of {1, 2} is obtained by deleting all initial digits in sequence A007088 (numbers written in base 2). - M. F. Hasler, Nov 03 2020

			Positive numbers may not start with 0 in the OEIS, otherwise this sequence would have been written as: 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, ...
From _Hieronymus Fischer_, Jun 06 2012: (Start)
a(10)   = 122.
a(100)  = 211212.
a(10^3) = 222212112.
a(10^4) = 1122211121112.
a(10^5) = 2111122121211112.
a(10^6) = 2221211112112111112.
a(10^7) = 11221112112122121111112.
a(10^8) = 12222212122221111211111112.
a(10^9) = 22122211221212211212111111112. (End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 2. - From N. J. A. Sloane, Jul 26 2012
K. Atanassov, On the 97th, 98th and the 99th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 89-93.
R. M. Smullyan, Theory of Formal Systems, Princeton, 1961.
John Stillwell, Reverse Mathematics, Princeton, 2018. See p. 90.

Hieronymus Fischer, Table of n, a(n) for n = 1..10000 (terms up to 2^10-2 from T. D. Noe, corrected by Sean A. Irvine, April 18 2019)
K. Atanassov, On Some of Smarandache's Problems, American Research Press, 1999, 16-21.
EMIS, Mirror site for Southwest Journal of Pure and Applied Mathematics
R. R. Forslund, A logical alternative to the existing positional number system, Southwest Journal of Pure and Applied Mathematics, Vol. 1, 1995.
R. R. Forslund, Positive Integer Pages
James E. Foster, A Number System without a Zero-Symbol, Mathematics Magazine, Vol. 21, No. 1. (1947), pp. 39-41.
F. Smarandache, Only Problems, Not Solutions!.
Index entries for 10-automatic sequences.

Cf. A007932 (digits 1-3), A059893, A045670, A052382 (digits 1-9), A059939, A059941, A059943, A032924, A084544, A084545, A046034 (prime digits 2,3,5,7), A089581, A084984 (no prime digits); A001742, A001743, A001744: loops; A202267 (digits 0, 1 and primes), A202268 (digits 1,4,6,8,9), A014261 (odd digits), A014263 (even digits).
Cf. A007088 (digits 0 & 1), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5), A256291 (digits 5 & 6), A256292 (digits 6 & 7), A256340 (digits 7 & 8), A256341 (digits 8 & 9), and A032804-A032816 (in other bases).
Cf. A020450 (primes).

a007931 n = f (n + 1) where
   f x = if x < 2 then 0 else (10 * f x') + m + 1
     where (x', m) = divMod x 2
-- Reinhard Zumkeller, Oct 26 2012

[n: n in [1..100000] | Set(Intseq(n)) subset {1,2}]; // Vincenzo Librandi, Aug 19 2016

# Maple program to produce the sequence:
a:= proc(n) local m, r, d; m, r:= n, 0;
      while m>0 do d:= irem(m, 2, 'm');
        if d=0 then d:=2; m:= m-1 fi;
        r:= d, r
      od; parse(cat(r))/10
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 26 2016
# Maple program to invert this sequence: given a(n), it returns n. - N. J. A. Sloane, Jul 09 2012
invert7931:=proc(u)
local t1,t2,i;
t1:=convert(u,base,10);
[seq(t1[i]-1,i=1..nops(t1))];
[op(%),1];
t2:=convert(%,base,2,10);
add(t2[i]*10^(i-1),i=1..nops(t2))-1;
end;

f[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[f, 42] (* Robert G. Wilson v Sep 14 2006 *)
(* Next, A007931 using (0,1) instead of (1,2) *)
d[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[FromCharacterCode[ToCharacterCode[ToString[d[#]]] - 1] &, 100] (* Peter J. C. Moses, at request of Clark Kimberling, Feb 09 2012 *)
Flatten[Table[FromDigits/@Tuples[{1,2},n],{n,5}]] (* Harvey P. Dale, Sep 13 2014 *)

apply( {A007931(n)=fromdigits([d+1|d<-binary(n+1)[^1]])}, [1..44]) \\ M. F. Hasler, Nov 03 2020, replacing older code from Mar 26 2015

/* inverse function */ apply( {A007931_inv(N)=fromdigits([d-1|d<-digits(N)],2)+2<M. F. Hasler, Nov 09 2020

def a(n): return int(bin(n+1)[3:].replace('1', '2').replace('0', '1'))
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, May 13 2021

def A007931(n): return int(s:=bin(n+1)[3:])+(10**(len(s))-1)//9 # Chai Wah Wu, Jun 13 2025

To get a(n), write n+1 in base 2, remove initial 1, add 1 to all remaining digits: e.g., eleven (11) in base 2 is 1011; remove initial 1 and add 1 to remaining digits: a(10)=122. - Clark Kimberling, Mar 11 2003
Conversely, given a(n), to get n: subtract 1 from all digits, prefix with an initial 1, convert this binary number to base 10, subtract 1. E.g., a(6)=22 -> 11 -> 111 -> 7 -> 6. - N. J. A. Sloane, Jul 09 2012
a(n) = A053645(n+1)+A002275(A000523(n)) = a(n-2^b(n))+10^b(n) where b(n) = A059939(n) = floor(log_2(n+1)-1). - Henry Bottomley, Feb 14 2001
From Hieronymus Fischer, Jun 06 2012 and Jun 08 2012: (Start)
The formulas are designed to calculate base-10 numbers only using the digits 1 and 2.
a(n) = Sum_{j=0..m-1} (1 + b(j) mod 2)*10^j, where m = floor(log_2(n+1)), b(j) = floor((n+1-2^m)/(2^j)).
Special values:
a(k*(2^n-1)) = k*(10^n-1)/9, k= 1,2.
a(3*2^n-2) = (11*10^n-2)/9 = 10^n+2*(10^n-1)/9.
a(2^n-2) = 2*(10^(n-1)-1)/9, n>1.
Inequalities:
a(n) <= (10^log_2(n+1)-1)/9, equality holds for n=2^k-1, k>0.
a(n) > (2/10)*(10^log_2(n+1)-1)/9.
Lower and upper limits:
lim inf a(n)/10^log_2(n) = 1/45, for n --> infinity.
lim sup a(n)/10^log_2(n) = 1/9, for n --> infinity.
G.f.: g(x) = (1/(x(1-x)))*sum_{j=0..infinity} 10^j* x^(2*2^j)*(1 + 2 x^2^j)/(1 + x^2^j).
Also: g(x) = (1/(1-x))*(h_(2,0)(x) + h_(2,1)(x) - 2*h_(2,2)(x)), where h_(2,k)(x) = sum_{j>=0} 10^j*x^(2^(j+1)-1)*x^(k*2^j)/(1-x^2^(j+1)).
Also: g(x) = (1/(1-x)) sum_{j>=0} (1 - 3(x^2^j)^2 + 2(x^2^j)^3)*x^2^j*f_j(x)/(1-x^2^j), where f_j(x) = 10^j*x^(2^j-1)/(1-(x^2^j)^2). The f_j obey the recurrence f_0(x) = 1/(1-x^2), f_(j+1)(x) = 10x*f_j(x^2). (End)

Some crossrefs added by Hieronymus Fischer, Jun 06 2012

Edited by M. F. Hasler, Mar 26 2015

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521

Offset: 0

Jeffrey Shallit

The graph has a blancmange or Takagi appearance. For the asymptotics, see the references by Flajolet with "Mellin" in the title. - N. J. A. Sloane, Mar 11 2021
The following alternative construction of this sequence is due to Thomas Nordhaus, Oct 31 2000: For each n >= 0 let f_n be the piecewise linear function given by the points (k /(2^n), a(k) / 3^n), k = 0, 1, ..., 2^n. f_n is a monotonic map from the interval [0,1] into itself, f_n(0) = 0, f_n(1) = 1. This sequence of functions converges uniformly. But the limiting function is not differentiable on a dense subset of this interval.
I submitted a problem to the Amer. Math. Monthly about an infinite family of non-convex sequences that solve a recurrence that involves minimization: a(1) = 1; a(n) = max { ua(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1; here u is any real-valued constant >= 1. The case u=2 gives the present sequence. Cf. A130665 - A130667. - Don Knuth, Jun 18 2007
a(n) = sum of (n-1)-th row terms of triangle A166556. - Gary W. Adamson, Oct 17 2009
From Gary W. Adamson, Dec 06 2009: (Start)
Let M = an infinite lower triangular matrix with (1, 3, 2, 0, 0, 0, ...) in every column shifted down twice:
  1;
  3;
  2; 1;
  0, 3;
  0, 2, 1;
  0, 0, 3;
  0, 0, 2, 1;
  0, 0, 0, 3;
  0, 0, 0, 2, 1;
  ...
This sequence starting with "1" = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. (End)
a(n) is also the sum of all entries in rows 0 to n of Sierpiński's triangle A047999. - Reinhard Zumkeller, Apr 09 2012
The production matrix of Dec 06 2009 is equivalent to the following: Let p(x) = (1 + 3x + 2x^2). The sequence = P(x) * p(x^2) * p(x^4) * p(x^8) * .... The sequence divided by its aerated variant = (1, 3, 2, 0, 0, 0, ...). - Gary W. Adamson, Aug 26 2016
Also the total number of ON cells, rows 1 through n, for cellular automaton Rule 90 (Cf. A001316, A038183, also Mathworld Link). - Bradley Klee, Dec 22 2018

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.
Flajolet, Philippe, and Mordecai Golin. "Mellin transforms and asymptotics." Acta Informatica 31.7 (1994): 673-696.
Flajolet, Philippe, Mireille Régnier, and Robert Sedgewick. "Some uses of the Mellin integral transform in the analysis of algorithms." in Combinatorial algorithms on words. Springer, 1985. 241-254.
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..16383 (first 1000 terms from T. D. Noe)
L. Carlitz, The number of binomial coefficients divisible by a fixed power of a prime, Rend. Circ. Mat. Palermo (2) 16 (1967), pp. 299-320.
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
Prerona Chatterjee, Kshitij Gajjar, and Anamay Tengse, Transparency Beyond VNP in the Monotone Setting, arXiv:2202.13103 [cs.CC], 2022.
S. R. Finch, P. Sebah, and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54:10 (1947), pp. 89-92.
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, and Robert F. Tichy, Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, Mellin transforms and asymptotics: harmonic sums Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
Philippe Flajolet and Robert Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice's integrals, Theoretical Computer Science 144.1-2 (1995): 101-124.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp 149-179.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62, 19-22, 1977.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62.1 (1977), 19-22. (Annotated scanned copy)
F. T. Howard, The number of binomial coefficients divisible by a fixed power of 2, Proceedings of the American Mathematical Society, Vol. 29:2 (Jul 1971), pp. 236-242.
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, pp. 6, 27, 29-31.
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. See p. 1.
Akhlesh Lakhtakia and Russell Messier, Self-similar sequences and chaos from Gauss sums, Computers & graphics 13.1 (1989): 59-62.
Akhlesh Lakhtakia and Russell Messier, Self-similar sequences and chaos from Gauss sums, Computers & Graphics 13.1 (1989), 59-60. (Annotated scanned copy)
A. Lakhtakia et al., Fractal sequences derived from the self-similar extensions of the Sierpinski gasket, J. Phys. A 21 (1988), 1925-1928.
Giuseppe Lancia and Paolo Serafini, Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data, Algorithms (2021) Vol. 14, No. 8, 235.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
Eric Weisstein's World of Mathematics, Pascal's Triangle
Eric Weisstein's World of Mathematics, Rule 90
Eric Weisstein's World of Mathematics, Stolarsky-Harborth Constant
Index entries for triangles and arrays related to Pascal's triangle

Partial sums of A001316.
See A130665 for Sum 3^wt(n).
a(n) = A074330(n-1) + 1 for n >= 2. A080978(n) = 2*a(n) + 1. Cf. A080263.
Cf. also A159912, A166556, A038183, A048896, A360189.
Sequences of form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

a006046 = sum . concat . (`take` a047999_tabl)
-- Reinhard Zumkeller, Apr 09 2012

[0] cat [n le 1 select 1 else 2*Self(Floor(n/2)) + Self(Floor(Ceiling(n/2))): n in [1..60]]; // Vincenzo Librandi, Aug 30 2016

f:=proc(n) option remember;
if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
else 2*f((n-1)/2)+f((n+1)/2); fi; end;
[seq(f(n),n=0..130)]; # N. J. A. Sloane, Jul 29 2014

f[n_] := Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ]; Table[ Sum[ f[k], {k, 0, n} ], {n, 0, 100} ]
Join[{0},Accumulate[Count[#,?OddQ]&/@Table[Binomial[n,k],{n,0,60},{k,0,n}]]] (* _Harvey P. Dale, Dec 10 2014 *)
FoldList[Plus, 0, Total /@ CellularAutomaton[90, Join[Table[0, {#}], {1}, Table[0, {#}]], #]][[2 ;; -1]] &@50 (* Bradley Klee, Dec 23 2018 *)
Join[{0}, Accumulate[2^DigitCount[Range[0, 127], 2, 1]]] (* Paolo Xausa, Oct 24 2024 *)
Join[{0}, Accumulate[2^Nest[Join[#, #+1]&, {0}, 7]]] (* Paolo Xausa, Oct 24 2024, after IWABUCHI Yu(u)ki in A000120 *)

A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2,1<M. F. Hasler, May 03 2009

a(n) = if(!n, 0, my(r=0, t=1); forstep(i=logint(n, 2), 0, -1, r*=3; if(bittest(n, i), r+=t; t*=2)); r); \\ Ruud H.G. van Tol, Jul 06 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006046(n):return n if n<=1 else 2*A006046((n-1)//2)+A006046((n+1)//2)if n%2 else 3*A006046(n//2) # Guillermo Hernández, Dec 31 2023

from math import prod
def A006046(n):
    d = list(map(lambda x:int(x)+1,bin(n)[:1:-1]))
    return sum((b-1)*prod(d[a:])*3**a for a, b in enumerate(d))>>1 # Chai Wah Wu, Aug 13 2025

a(n) = Sum_{k=0..n-1} 2^A000120(k). - Paul Barry, Jan 05 2005; simplified by N. J. A. Sloane, Apr 05 2014
For asymptotics see Stolarsky (1977). - N. J. A. Sloane, Apr 05 2014
a(n) = a(n-1) + A001316(n-1). a(2^n) = 3^n. - Henry Bottomley, Apr 05 2001
a(n) = n^(log_2(3))*G(log_2(n)) where G(x) is a function of period 1 defined by its Fourier series. - Benoit Cloitre, Aug 16 2002; formula modified by S. R. Finch, Dec 31 2007
G.f.: (x/(1-x))*Product_{k>=0} (1 + 2*x^2^k). - Ralf Stephan, Jun 01 2003; corrected by Herbert S. Wilf, Jun 16 2005
a(1) = 1, a(n) = 2*a(floor(n/2)) + a(ceiling(n/2)).
a(n) = 3*a(floor(n/2)) + (n mod 2)*2^A000120(n-1). - M. F. Hasler, May 03 2009
a(n) = Sum_{k=0..floor(log_2(n))} 2^k * A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

More terms from James Sellers, Aug 21 2000

Definition expanded by N. J. A. Sloane, Feb 16 2016

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.

Original entry on oeis.org

1, 3, 2, 10, 3, 7, 4, 36, 5, 11, 6, 26, 7, 15, 8, 136, 9, 19, 10, 42, 11, 23, 12, 100, 13, 27, 14, 58, 15, 31, 16, 528, 17, 35, 18, 74, 19, 39, 20, 164, 21, 43, 22, 90, 23, 47, 24, 392, 25, 51, 26, 106, 27, 55, 28, 228, 29, 59, 30, 122, 31, 63, 32, 2080, 33, 67, 34, 138, 35

Offset: 1

Johannes W. Meijer, Dec 24 2012

The a(n) appeared in the analysis of A220002, a sequence related to the Catalan numbers.
The first Maple program makes use of a program by Peter Luschny for the calculation of the a(n) values. The second Maple program shows that this sequence has a beautiful internal structure, see the first formula, while the third Maple program makes optimal use of this internal structure for the fast calculation of a(n) values for large n.
The cross references lead to sequences that have the same internal structure as this sequence.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences with simple ordinary generating functions, The OEIS, Jan 01 2004.

Cf. A000027 (the natural numbers), A000120 (1's-counting sequence), A000265 (remove 2's from n), A001316 (Gould's sequence), A001511 (the ruler function), A003484 (Hurwitz-Radon numbers), A003602 (a fractal sequence), A006519 (highest power of 2 dividing n), A007814 (binary carry sequence), A010060 (Thue-Morse sequence), A014577 (dragon curve), A014707 (dragon curve), A025480 (nim-values), A026741, A035263 (first Feigenbaum symbolic sequence), A037227, A038712, A048460, A048896, A051176, A053381 (smooth nowhere-zero vector fields), A055975 (Gray code related), A059134, A060789, A060819, A065916, A082392, A085296, A086799, A088837, A089265, A090739, A091512, A091519, A096268, A100892, A103391, A105321 (a fractal sequence), A109168 (a continued fraction), A117973, A129760, A151930, A153733, A160467, A162728, A181988, A182241, A191488 (a companion to Gould's sequence), A193365, A220466 (this sequence).

-- Following Ralf Stephan's recurrence:
import Data.List (transpose)
a220466 n = a006519_list !! (n-1)
a220466_list = 1 : concat
   (transpose [zipWith (-) (map (* 4) a220466_list) a006519_list, [2..]])
-- Reinhard Zumkeller, Aug 31 2014

# First Maple program
a := n -> 2^padic[ordp](n, 2)*(n+1)/2 : seq(a(n), n=1..69); # Peter Luschny, Dec 24 2012
# Second Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 4^p*(n-1)  + 2^(p-1)*(1+2^p) od: od: seq(a(n), n=1..nmax);
# Third Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do n:=2^p: n1:=1: while n <= nmax do a(n) := 4^p*(n1-1)+2^(p-1)*(1+2^p): n:=n+2^(p+1): n1:= n1+1: od: od:  seq(a(n), n=1..nmax);

A220466 = Module[{n, p}, p = IntegerExponent[#, 2]; n = (#/2^p + 1)/2; 4^p*(n - 1) + 2^(p - 1)*(1 + 2^p)] &; Array[A220466, 50] (* JungHwan Min, Aug 22 2016 *)

a(n)=if(n%2,n\2+1,4*a(n/2)-2^valuation(n/2,2)) \\ Ralf Stephan, Dec 17 2013

a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1. Observe that a(2^p) = A007582(p).
a(n) = ((n+1)/2)*(A060818(n)/A060818(n-1))
a(n) = (-1/64)*(q(n+1)/q(n))/(2*n+1) with q(n) = (-1)^(n+1)*2^(4*n-5)*(2*n)!*A060818(n-1) or q(n) = (1/8)*A220002(n-1)*1/(A098597(2*n-1)/A046161(2*n))*1/(A008991(n-1)/A008992(n-1))
Recurrence: a(2n) = 4a(n) - 2^A007814(n), a(2n+1) = n+1. - Ralf Stephan, Dec 17 2013

A135416 a(n) = A036987(n)*(n+1)/2.

Original entry on oeis.org

1, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane, based on a message from Guy Steele and Don Knuth, Mar 01 2008

nonn

Guy Steele defines a family of 36 integer sequences, denoted here by GS(i,j) for 1 <= i, j <= 6, as follows. a[1]=1; a[2n] = i-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}; a[2n+1] = j-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}. The present sequence is GS(1,5).
The full list of 36 sequences:
GS(1,1) = A000007
GS(1,2) = A000035
GS(1,3) = A036987
GS(1,4) = A007814
GS(1,5) = A135416 (the present sequence)
GS(1,6) = A135481
GS(2,1) = A135528
GS(2,2) = A000012
GS(2,3) = A000012
GS(2,4) = A091090
GS(2,5) = A135517
GS(2,6) = A135521
GS(3,1) = A036987
GS(3,2) = A000012
GS(3,3) = A000012
GS(3,4) = A000120
GS(3,5) = A048896
GS(3,6) = A038573
GS(4,1) = A135523
GS(4,2) = A001511
GS(4,3) = A008687
GS(4,4) = A070939
GS(4,5) = A135529
GS(4,6) = A135533
GS(5,1) = A048298
GS(5,2) = A006519
GS(5,3) = A080100
GS(5,4) = A087808
GS(5,5) = A053644
GS(5,6) = A000027
GS(6,1) = A135534
GS(6,2) = A038712
GS(6,3) = A135540
GS(6,4) = A135542
GS(6,5) = A054429
GS(6,6) = A003817
(with a(0)=1): Moebius transform of A038712.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to binary expansion of n

Equals A048298(n+1)/2. Cf. A036987, A182660.

GS:=proc(i,j,M) local a,n; a:=array(1..2*M+1); a[1]:=1;
for n from 1 to M do
a[2*n] :=[0,1,a[n],a[n]+1,2*a[n],2*a[n]+1][i];
a[2*n+1]:=[0,1,a[n],a[n]+1,2*a[n],2*a[n]+1][j];
od: a:=convert(a,list); RETURN(a); end;
GS(1,5,200):

i = 1; j = 5; Clear[a]; a[1] = 1; a[n_?EvenQ] := a[n] = {0, 1, a[n/2], a[n/2]+1, 2*a[n/2], 2*a[n/2]+1}[[i]]; a[n_?OddQ] := a[n] = {0, 1, a[(n-1)/2], a[(n-1)/2]+1, 2*a[(n-1)/2], 2*a[(n-1)/2]+1}[[j]]; Array[a, 105] (* Jean-François Alcover, Sep 12 2013 *)

A048298(n) = if(!n,0,if(!bitand(n,n-1),n,0));
A135416(n) = (A048298(n+1)/2); \\ Antti Karttunen, Jul 22 2018

def A135416(n): return int(not(n&(n+1)))*(n+1)>>1 # Chai Wah Wu, Jul 06 2022

G.f.: sum{k>=1, 2^(k-1)*x^(2^k-1) }.

Recurrence: a(2n+1) = 2a(n), a(2n) = 0, starting a(1) = 1.

Formulae and comments by Ralf Stephan, Jun 20 2014

A002425 Denominator of Pi^(2n)/(Gamma(2n)(1-2^(-2n))zeta(2n)).

Original entry on oeis.org

1, 1, 1, 17, 31, 691, 5461, 929569, 3202291, 221930581, 4722116521, 968383680827, 14717667114151, 2093660879252671, 86125672563201181, 129848163681107301953, 868320396104950823611, 209390615747646519456961

Offset: 1

N. J. A. Sloane

Differs from the absolute values of A275994 the first time at index 60.
Consider the C(k)-summation process for divergent series: the series Sum((-1)^n*(n+1)^k) == 1 - 2^k + 3^k - 4^k + ..., summable C(1) to the value 1/2 for k = 0, is for each k >= 1 exactly summable C(k+1) to the sum s(k+1) = (2^(k+1)-1)*B(k+1)/ (k+1) and so a(n) = abs(numerator(s(2n))). - Benoit Cloitre, Apr 27 2002
Odd part of tangent numbers A000182 (even part is 2^A101921(n)). - Ralf Stephan, Dec 21 2004
(-1)^n*a(n+1) is the numerator of Euler(2n+1,1). - N. J. A. Sloane, Nov 10 2009 (a misprint corrected by Vladimir Shevelev, Sep 18 2017)
a(n) is the absolute value of the constant term of the Euler polynomial E_{2n-1} times the even part of 2n. - Peter Luschny, Nov 26 2010
From Vladimir Shevelev, Aug 31 2017: (Start)
Let E_m(x) = x^m + Sum_{odd k=1..m} e_k(m)*x^(m-k) be the Euler polynomial, let 2*n-1 <= m. Show that the expression c(m,n) = |e_(2*n-1)(m)|/binomial(m,2*n-1) does not depend on m and c(m,n) = a(n)/A006519(2*n). Indeed, by the formula in the Shevelev link |e_(2*n-1)(m)| = binomial(m,2*n-1)*(4^n-1)*B_(2*n)/n. On the other hand, by Cloitre's formula, we have a(n) = (4^n-1)*|B_(2*n)|*2^A001511(n) /n. Taking into account that 2^A001511 = A006519(2*n) we obtain the claimed equality. Since sign(e_k(n)) = (-1)^((k+1)/2), we have the following application of the sequence: e_k(n) = (-1)^((k+1)/2))*a((k+1)/2)*binomial(n,k)/A006519(k+1). (End)

A. Fletcher, J. C. P. Miller, L. Rosenhead and L. J. Comrie, An Index of Mathematical Tables. Vols. 1 and 2, 2nd ed., Blackwell, Oxford and Addison-Wesley, Reading, MA, 1962, Vol. 1, p. 73.
S. A. Joffe, Sums of like powers of natural numbers, Quart. J. Pure Appl. Math. 46 (1914), 33-51.
Konrad Knopp, Theory and application of infinite series, Divergent series, Dover, p. 479
L. Oettinger, Archiv. Math. Phys., 26 (1856), see esp. p. 5.
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).

N. J. A. Sloane, Table of n, a(n) for n = 1..300
H. Cohn, Some elementary aspects of modular functions in several variables, Bull. Am. Math. Soc., Sept. 1965, 681ff, esp. p. 688.
Ren Guan, K_0 groups of noncommutative R^2n, arXiv:2208.06253 [math.RA], 2022. See p. 22.
S. A. Joffe, Sums of like powers of natural numbers, Quart. J. Pure Appl. Math. 46 (1914), 33-51. [Annotated scanned copy of pages 38-51 only, plus notes]
Konrad Knopp, Theorie und Anwendung der unendlichen Reihen, Berlin, J. Springer, 1922. (Original german edition of "Theory and Application of Infinite Series")
Vladimir Shevelev, On a Luschny question, arXiv:1708.08096 [math.NT], 2017.

Numerator given by A037239.
Different from A089171, A275994.
Cf. A048896, A089170, A089171, A160469, A335956.

[Denominator(4*n/((4^n-1)*Bernoulli(2*n))): n in [1..20]]; // G. C. Greubel, Jul 03 2019

A002425 := n -> (-1)^n*euler(2*n-1,0)*2^padic[ordp](2*n,2); # Peter Luschny, Nov 26 2010
A002425_list := proc(n) 1/(1+1/exp(z)); series(%,z,2*n+4);
seq(numer((-1)^i*(2*i+1)!*coeff(%,z,2*i+1)),i=0..n) end;
A002425_list(17); # Peter Luschny, Jul 12 2012

a[n_]:= (-1)^(n-1) * Numerator[EulerE[2n-1, 1]]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2011, after N. J. A. Sloane's comment *)
a[n_]:= If[n<1, 0, With[{m = 2n-1}, Numerator[ m! SeriesCoefficient[ Tan[x/2], {x, 0, m}]]]] (* Michael Somos, Sep 14 2013 *)
Table[2*(4^n-1)*Zeta[1-2n] // Abs // Numerator, {n, 1, 20}] (* Jean-François Alcover, Oct 16 2013 *)

for(n=1,20,print1(abs(numerator(2*bernfrac(2*n)*(4^n-1)/(2*n))),","))

a(n)=if(n<1,0,(-1)^n/n*(1-4^n)*bernfrac(2*n)*2^valuation(2*n,2))

a(n)=(-1)^n*4*bitand(n,-n)*polylog(1-2*n,-1); \\ Peter Luschny, Nov 22 2012

def A002425_list(n):
    T = [0]*n; T[0] = 1; S = [0]*n; k2 = 0
    for k in (1..n-1): T[k] = k*T[k-1]
    for k in (1..n):
        if is_odd(k): S[k-1] = 4*k2; k2 += 1
        else: S[k-1] = S[k2-1]+2*k2-1
        for j in (k..n-1): T[j] = (j-k)*T[j-1]+(j-k+2)*T[j]
    return [T[j]>>S[j] for j in (0..n-1)]
A002425_list(20)  # Peter Luschny, Nov 17 2012

[denominator(4*n/((4^n-1)*bernoulli(2*n))) for n in (1..20)] # G. C. Greubel, Jul 03 2019

a(n) = (-1)^n/n*(1 - 4^n)*B(2*n)*2^A001511(n) where B(k) denotes the k-th Bernoulli number. - Benoit Cloitre, Dec 30 2003
This is different from the sequence of numerators of the expansion of cosec(x) - cot(x) - see A089171.
From Johannes W. Meijer, May 24 2009: (Start)
a(n) = denominator(4*n/((2^(2*n)-1)*bernoulli(2*n))).
Equals A160469(n)/A048896(n-1).
Equals A089171(n)*A089170(n-1). (End)
E.g.f.: a(n) = numerator((2*n+1)!*[x^(2*n+1)](1/(1+1/exp(x)))). - Peter Luschny, Jul 12 2012
a(n) = numerator(abs(2*(4^n-1)*zeta(1-2*n))). - Jean-François Alcover, Oct 16 2013
For every positive integers n,k we have a(n) = (-1)^(n+k)*N(2*n-1,k) + 2*(-1)^(n-1)*A006519(2*n)*(1^(2*n-1)-2^(2*n-1)+..+(-1)^k*(k-1)^(2*n-1)), where N(n,k) is the numerator of Euler(n,k). So, the right hand side is an invariant of k. - Vladimir Shevelev, Sep 19 2017
a(n) = numerator(r(n)) where r(n) = (-1)^binomial(2*n, 2)*Sum_{k=1..2*n}(-1)^k*Stirling2(2*n, k)*2^(-k)*(k-1)!. - Peter Luschny, May 24 2020
a(n) = 2*(-1)^n*A335956(2*n)*zeta(1-2*n). - Peter Luschny, Aug 30 2020

The n=15 term was formerly incorrectly given as 86125672563301143.

Formula and cross-references edited by Johannes W. Meijer, May 21 2009

A100258 Triangle of coefficients of normalized Legendre polynomials, with increasing exponents.

Original entry on oeis.org

1, 0, 1, -1, 0, 3, 0, -3, 0, 5, 3, 0, -30, 0, 35, 0, 15, 0, -70, 0, 63, -5, 0, 105, 0, -315, 0, 231, 0, -35, 0, 315, 0, -693, 0, 429, 35, 0, -1260, 0, 6930, 0, -12012, 0, 6435, 0, 315, 0, -4620, 0, 18018, 0, -25740, 0, 12155, -63, 0, 3465, 0, -30030, 0, 90090, 0, -109395, 0, 46189

Offset: 0

Ralf Stephan, Nov 13 2004

For a relation to Jacobi quartic elliptic curves, see the MathOverflow link. For a self-convolution of the polynomials relating them to the Chebyshev and Fibonacci polynomials, see A049310 and A053117. For congruences and connections to other polynomials (Jacobi, Gegenbauer, and Chebyshev) see the Allouche et al. link. For relations to elliptic cohomology and modular forms, see references in Copeland link.- Tom Copeland, Feb 04 2016

			Triangle begins:
   1;
   0,   1;
  -1,   0,     3;
   0,  -3,     0,   5;
   3,   0,   -30,   0,   35;
   0,  15,     0, -70,    0,   63;
  -5,   0,   105,   0, -315,    0,    231;
   0, -35,     0, 315,    0, -693,      0, 429;
  35,   0, -1260,   0, 6930,    0, -12012,   0, 6435;
  ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 798.

T. D. Noe, Rows n=0..100 of triangle, flattened
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
J. Allouche and G. Skordev, Schur congruences, Carlitz sequences of polynomials and automaticity, Discrete Mathematics, Vol. 214, Issue 1-3, 21 March 2000, p. 21-49.
Tom Copeland, The Elliptic Lie Triad: Riccati and KdV Equations, Infinigens, and Elliptic Genera
H. N. Laden, An historical, and critical development of the theory of Legendre polynomials before 1900, Master of Arts Thesis, University of Maryland 1938.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
MathOverflow, Geometric picture of invariant differential of an elliptic curve, Dec 4 2011.

Without zeros: A008316. Row sums are A060818.
Columns (with interleaved zeros and signs) include A001790, A001803, A100259. Diagonals include A001790, A001800, A001801, A001802.
Cf. A049310, A005187, A049600, A053117.

row[n_] := CoefficientList[ LegendreP[n, x], x]*2^IntegerExponent[n!, 2]; Table[row[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 15 2015 *)

a(k,n)=polcoeff(pollegendre(k,x),n)*2^valuation(k!,2)

from mpmath import *
mp.dps=20
def a007814(n):
    return 1 + bin(n - 1)[2:].count('1') - bin(n)[2:].count('1')
for n in range(11):
    y=2**sum(a007814(i) for i in range(2, n+1))
    l=chop(taylor(lambda x: legendre(n, x), 0, n))
    print([int(i*y) for i in l]) # Indranil Ghosh, Jul 02 2017

The n-th normalized Legendre polynomial is generated by 2^(-n-a(n)) (d/dx)^n (x^2-1)^n / n! with a(n) = A005187(n/2) for n even and a(n) = A005187((n-1)/2) for n odd. The non-normalized polynomials have the o.g.f. 1 / sqrt(1 - 2xz + z^2). - Tom Copeland, Feb 07 2016

The consecutive nonzero entries in the m-th row are, in order, (c+b)!/(c!(m-b)!(2b-m)!*A048896(m-1)) with sign (-1)^b where c = m/2-1, m/2, m/2+1, ..., (m-1) and b = c+1 if m is even and sign (-1)^c with c = (m-1)/2, (m-1)/2+1, (m-1)/2+2, ..., (m-1) with b = c+1 if m is odd. For the 9th row the 5 consecutive nonzero entries are 315, -4620, 18018, -25740, 12155 given by c = 4,5,6,7,8 and b = 5,6,7,8,9. - Richard Turk, Aug 22 2017

cp's OEIS Frontend

A225081 Gray code variant of A048896.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A127973 a(2n)=A060632(n); a(2n+1)=A048896(n)/2.

Views

Author

Keywords

Comments

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Scheme

Formula

Extensions

A007931 Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A220466 a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1.

Views

Author

Keywords

Comments

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.

A002425 Denominator of Pi^(2n)/(Gamma(2n)(1-2^(-2n))zeta(2n)).