A051638 -id:A051638 - 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

A083093 Triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 3.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 2, 1, 1, 0, 0, 2, 0, 0, 1, 1, 1, 0, 2, 2, 0, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1

Offset: 0

Benoit Cloitre, Apr 22 2003

Start with [1], repeatedly apply the map 0 -> [000/000/000], 1 -> [111/120/100], 2 -> [222/210/200]. - Philippe Deléham, Apr 16 2009

{T(n,k)} is a fractal gasket with fractal (Hausdorff) dimension log(A000217(3))/log(3) = log(6)/log(3) = 1.63092... (see Reiter reference). Replacing values greater than 1 with 1 produces a binary gasket with the same dimension (see Bondarenko reference). - Richard L. Ollerton, Dec 14 2021

			.            Rows 0 .. 3^3:
.    0:                             1
.    1:                            1 1
.    2:                           1 2 1
.    3:                          1 0 0 1
.    4:                         1 1 0 1 1
.    5:                        1 2 1 1 2 1
.    6:                       1 0 0 2 0 0 1
.    7:                      1 1 0 2 2 0 1 1
.    8:                     1 2 1 2 1 2 1 2 1
.    9:                    1 0 0 0 0 0 0 0 0 1
.   10:                   1 1 0 0 0 0 0 0 0 1 1
.   11:                  1 2 1 0 0 0 0 0 0 1 2 1
.   12:                 1 0 0 1 0 0 0 0 0 1 0 0 1
.   13:                1 1 0 1 1 0 0 0 0 1 1 0 1 1
.   14:               1 2 1 1 2 1 0 0 0 1 2 1 1 2 1
.   15:              1 0 0 2 0 0 1 0 0 1 0 0 2 0 0 1
.   16:             1 1 0 2 2 0 1 1 0 1 1 0 2 2 0 1 1
.   17:            1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1
.   18:           1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1
.   19:          1 1 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 1 1
.   20:         1 2 1 0 0 0 0 0 0 2 1 2 0 0 0 0 0 0 1 2 1
.   21:        1 0 0 1 0 0 0 0 0 2 0 0 2 0 0 0 0 0 1 0 0 1
.   22:       1 1 0 1 1 0 0 0 0 2 2 0 2 2 0 0 0 0 1 1 0 1 1
.   23:      1 2 1 1 2 1 0 0 0 2 1 2 2 1 2 0 0 0 1 2 1 1 2 1
.   24:     1 0 0 2 0 0 1 0 0 2 0 0 1 0 0 2 0 0 1 0 0 2 0 0 1
.   25:    1 1 0 2 2 0 1 1 0 2 2 0 1 1 0 2 2 0 1 1 0 2 2 0 1 1
.   26:   1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
.   27:  1 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 1 .
- _Reinhard Zumkeller_, Jul 11 2013

Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Disc. Appl. Math. 66 (1996) 1-22.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132.
Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
Lin Jiu and Christophe Vignat, On Binomial Identities in Arbitrary Bases, arXiv:1602.04149 [math.CO], 2016.
Y. Moshe, The density of 0's in recurrence double sequences, J. Number Theory, 103 (2003), 109-121.
Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
Index entries for triangles and arrays related to Pascal's triangle

Cf. A007318, A051638 (row sums), A090044, A047999, A034931, A034930, A008975, A034932, A062296, A006047.
Cf. A006996 (central terms), A173019, A206424, A227428.
Sequences based on the triangles formed by reading Pascal's triangle mod m: A047999 (m = 2), (this sequence) (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).

a083093 n k = a083093_tabl !! n !! k
a083093_row n = a083093_tabl !! n
a083093_tabl = iterate
   (\ws -> zipWith (\u v -> mod (u + v) 3) ([0] ++ ws) (ws ++ [0])) [1]
-- Reinhard Zumkeller, Jul 11 2013

/* As triangle: */ [[Binomial(n,k) mod 3: k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Feb 15 2016

A083093 := proc(n,k)
    modp(binomial(n,k),3) ;
end proc:
seq(seq(A083093(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Jul 26 2017

Mod[ Flatten[ Table[ Binomial[n, k], {n, 0, 13}, {k, 0, n}]], 3] (* Robert G. Wilson v, Jan 19 2004 *)

from sympy import binomial
def T(n, k):
    return binomial(n, k) % 3
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Jul 26 2017

from math import comb, isqrt
def A083093(n):
    def f(m,k):
        if m<3 and k<3: return comb(m,k)%3
        c,a = divmod(m,3)
        d,b = divmod(k,3)
        return f(c,d)*f(a,b)%3
    return f(r:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)),n-comb(r+1,2)) # Chai Wah Wu, Apr 30 2025

T(i, j) = binomial(i, j) mod 3.
T(n+1,k) = (T(n,k) + T(n,k-1)) mod 3. - Reinhard Zumkeller, Jul 11 2013
T(n,k) = Product_{i>=0} binomial(n_i,k_i) mod 3, where n = Sum_{i>=0} n_i*3^i and k = Sum_{i>=0} k_i*3^i, 0<=n_i, k_i <=2 [Allouche et al.]. - R. J. Mathar, Jul 26 2017

A037301 Numbers whose base-2 and base-3 expansions have the same digit sum.

Original entry on oeis.org

0, 1, 6, 7, 10, 11, 12, 13, 18, 19, 21, 36, 37, 46, 47, 58, 59, 60, 61, 86, 92, 102, 103, 114, 115, 120, 121, 166, 167, 172, 173, 180, 181, 198, 199, 216, 217, 222, 223, 261, 273, 282, 283, 285, 298, 299, 300, 301, 306, 307, 309, 318

Offset: 1

Clark Kimberling

If Sum_{i=0..k} (binomial(k,i) mod 2) == Sum_{i=0..k} (binomial(k,i) mod 3) then k is in the sequence. (The converse does not hold.) - Benoit Cloitre, Nov 16 2003
Problem: To prove that the sequence is infinite. A generalization: Let s_m(k) denote the sum of digits of k in base m; does the Diophantine equation s_p(k) = s_q(k), where p,q are fixed distinct primes, have infinitely many solutions? - Vladimir Shevelev, Jul 30 2009
Also, numbers k such that the exponent of the largest power of 2 dividing k! is exactly twice the exponent of the largest power of 3 dividing k!. - Ivan Neretin, Mar 08 2015
a(5) = 10, a(6) = 11, a(7) = 12 and a(8) = 13 is the first time that four consecutive terms appear in this sequence. Conjecture: There is no occurrence of five or more consecutive terms of a(n). Tested by exhaustive search up to a(n) = 3^29. - Thomas König, Aug 15 2020

Stanislav Sykora, Table of n, a(n) for n = 1..10000
Vladimir Shevelev, Compact integers and factorials, Acta Arith. 126 (2007), no. 3, 195-236.
Vladimir Shevelev, Binomial predictors, arXiv:0907.3302 [math.NT], 2009.
Lukas Spiegelhofer, Collisions of the binary and ternary sum-of-digits functions, arXiv:2105.11173 [math.NT], 2021. Proves that sequence is infinite.

Cf. A000120, A053735, A180017.

Cf. A001316, A051638, A212222, A330904, A334765.

Select[ Range@ 320, Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 3] &] (* Robert G. Wilson v, Oct 24 2014 *)

is(n)=sumdigits(n,3)==hammingweight(n) \\ Charles R Greathouse IV, May 21 2015

A053735(a(n)) = A000120(a(n)); A180017(a(n)) = 0. - Reinhard Zumkeller, Aug 06 2010

Zero prepended by Zak Seidov, May 31 2010

A384715 a(n) = Sum_{k=0..n} (binomial(n, k) mod 4).

Original entry on oeis.org

1, 2, 4, 8, 4, 8, 12, 16, 4, 8, 12, 24, 12, 24, 24, 32, 4, 8, 12, 24, 12, 24, 32, 48, 12, 24, 32, 48, 24, 48, 48, 64, 4, 8, 12, 24, 12, 24, 32, 48, 12, 24, 32, 64, 32, 64, 64, 96, 12, 24, 32, 48, 32, 64, 64, 96, 24, 48, 64, 96, 48, 96, 96, 128, 4, 8, 12, 24

Offset: 0

David Radcliffe, Jun 23 2025

This is a 2-automatic sequence.

			Let b(n) be the binary expansion of n. Then a(n) = (1 + p10 + p11) * 2^c, where c is the number of set bits in b(n), p10 is the number of '10' patterns in b(n), and p11 is 1 or 0 depending on whether the pattern '11' is occurring in b(n) or not. This formula is used by _Chai Wah Wu_ in the Python function below. For instance:
  n = 25 -> b(n) = 11001 -> a(n) = (1+1+1) * 2^3 = 24.
  n = 26 -> b(n) = 11010 -> a(n) = (1+2+1) * 2^3 = 32.
  n = 27 -> b(n) = 11011 -> a(n) = (1+1+1) * 2^4 = 48.
- _Peter Luschny_, Jun 25 2025

David Radcliffe, Table of n, a(n) for n = 0..10000
Kenneth S. Davis and William A. Webb, Pascal's triangle modulo 4, Fib. Quart., 29 (1991), 79-83.

Cf. A001316, A014081, A033264, A051638 (mod 3 analog), A085357. Row sums of triangle A034931.

A384715[n_] := 2^DigitSum[n, 2]*(StringCount[IntegerString[n, 2], "10"] - Boole[BitAnd[n,2*n] == 0] + 2);
Array[A384715, 100, 0] (* Paolo Xausa, Jun 26 2025 *)

a(n) = sum(k=0, n, binomial(n,k)%4); \\ Michel Marcus, Jun 25 2025

def A001316(n): return (1 + (n % 2)) * A001316(n // 2) if n else 1
def A033264(n): return (n % 4 == 2) + A033264(n // 2) if n else 0
def A085357(n): return int(n & (n<<1) == 0)
def A384715(n): return A001316(n) * (A033264(n) - A085357(n) + 2)

def A384715(n): return (((n>>1)&~n).bit_count()+bool(n&(n<<1))+1)<Chai Wah Wu, Jun 25 2025

def a(n: int) -> int:  # after Chai Wah Wu
    b = bin(n)[2:]; p = b.count("10"); q = b.count("11")
    return (p + (2 if q else 1)) * 2**n.bit_count()  # Peter Luschny, Jun 25 2025

a(n) = A001316(n) * (A033264(n) - A085357(n) + 2) for n > 0.
Recurrences:
a(4n) = a(2n),
a(4n+1) = 2a(2n),
a(8n+2) = a(4n+2) + 2a(2n) - a(2n+1),
a(8n+3) = a(4n+3) + 4a(2n) - 4a(n),
a(8n+6) = a(4n+3) + 2a(4n+2) - 2a(2n+1),
a(8n+7) = 2a(4n+3).

A083095 a(n) = A083094(n)/4.

Original entry on oeis.org

0, 2, 5, 6, 14, 15, 18, 20, 41, 42, 45, 47, 54, 56, 59, 60, 122, 123, 126, 128, 135, 137, 140, 141, 162, 164, 167, 168, 176, 177, 180, 182, 365, 366, 369, 371, 378, 380, 383, 384, 405, 407, 410, 411, 419, 420, 423, 425, 486, 488, 491, 492, 500

Offset: 1

Benoit Cloitre, Apr 22 2003

Is this the same as A083097? - Andrew S. Plewe, May 30 2007

Hugo Pfoertner, Table of n, a(n) for n = 1..16384 (terms 1..106 from Paul F. Marrero Romero)

Cf. A010060, A051638, A083093, A083094, A083097, A074939.

Select[Range[0,2000], OddQ[Sum[Mod[Binomial[#,j],3],{j,0,#}]]&]/4 (* Paul F. Marrero Romero, Dec 28 2024 *)

def A083095(n): return int(bin(((m:=n-1).bit_count()&1)+(m<<1))[2:],3)>>1 # Chai Wah Wu, Jun 26 2025

Apparently (2*a(n)) mod 3 = A010060(n-1), the Thue-Morse sequence.
Numbers k such that C(4*k, 2*k) == 1 (mod 3). - Benoit Cloitre, Jul 30 2003
Numbers k such that the base-3 digits of 2k contains no 2's, i.e. a(n) = A074939(n-1)/2. - Chai Wah Wu, Jun 26 2025

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 29 2003

A083094 Numbers k such that Sum_{j=0..k} (binomial(k,j) mod 3) is odd.

Original entry on oeis.org

0, 8, 20, 24, 56, 60, 72, 80, 164, 168, 180, 188, 216, 224, 236, 240, 488, 492, 504, 512, 540, 548, 560, 564, 648, 656, 668, 672, 704, 708, 720, 728, 1460, 1464, 1476, 1484, 1512, 1520, 1532, 1536, 1620, 1628, 1640, 1644, 1676, 1680, 1692, 1700, 1944, 1952

Offset: 1

Benoit Cloitre, Apr 22 2003

Apparently a(n)/2 (mod 3) = A010060(n), the Thue-Morse sequence.

Cf. A010060, A051638, A074939, A083093, A083095 (gives a b-file of 16384 terms).

Select[Range[0, 2000],OddQ[Sum[Mod[Binomial[#, j], 3], {j, 0, #}]] &] (* Paul F. Marrero Romero, Dec 28 2024 *)

isok(n) = sum(k=0, n, binomial(n,k) % 3) % 2; \\ Michel Marcus, Dec 05 2013

def A083094(n): return int(bin(((m:=n-1).bit_count()&1)+(m<<1))[2:],3)<<1 # Chai Wah Wu, Jun 26 2025

a(n) = 4*A083095(n). - Hugo Pfoertner, Jan 12 2025

Numbers that are multiples of 4 and such that base-3 digits contain no 1's, or equivalently, numbers such that base-3 digits contains an even number of 2's and no 1's, i.e. a(n) = 2*A074939(n-1). This characterization can be derived from the formula in A051638. - Chai Wah Wu, Jun 26 2025

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 29 2003

A385741 a(n) = Sum_{k=0..n} (binomial(n, k) mod 9).

Original entry on oeis.org

1, 2, 4, 8, 16, 14, 28, 38, 31, 8, 16, 32, 28, 56, 49, 62, 52, 68, 28, 56, 76, 62, 79, 122, 91, 92, 112, 8, 16, 32, 28, 56, 76, 80, 124, 140, 28, 56, 103, 80, 142, 158, 145, 146, 184, 62, 124, 158, 100, 146, 184, 188, 232, 230, 28, 56, 76, 80, 151, 158, 136, 236

Offset: 0

Chai Wah Wu, Jul 09 2025

nonn

Sum of n-th row of Pascal's triangle mod 9, A095143.

Chai Wah Wu, Table of n, a(n) for n = 0..10000
James G. Huard, Blair K. Spearman, and Kenneth S. Williams, Pascal's triangle (mod 9), Acta Arithmetica, 78 (1997), 331-349.

Cf. A001316, A051638, A384715, A385285.

a[n_]:=Sum[Mod[Binomial[n,k],9],{k,0,n}];Table[a[n],{n,0,61}] (* James C. McMahon, Jul 10 2025 *)

a(n) = sum(k=0, n, binomial(n, k) % 9); \\ Michel Marcus, Jul 10 2025

from gmpy2 import digits
import re, sympy
from sympy import S, I, sqrt, simplify, Rational
def A385741(n):
    s = digits(n,3)
    n1 = s.count('1')
    n2 = s.count('2')
    n01 = s.count('10')
    n02 = s.count('20')
    n11 = len(re.findall('(?=11)',s))
    n12 = s.count('21')
    n121 = len(re.findall('(?=121)',s))
    n122 = s.count('221')
    n21 = s.count('12')
    n22 = len(re.findall('(?=22)',s))
    x1 = (3*(3**n2*(12*n01+(n02<<4)+3*n11+(n12<<2))-(n01+n12<<2)+(n02<<4)+n11)<>3
    beta = S.Half*(I*sqrt(3)-1)
    def ind2(t): return (0,0,1,0,2,5,0,4,3)[t]
    def X(t): return beta**(ind2(t)-n11-n12+n121-n122)*(2-beta)**(n21-n121)*(3+beta)**(n2-n12-n21-n22+n121+n122)
    def Y(t): return beta**(n11-ind2(t))*(1-beta)**(n21-n121)*(2+beta)**(n2-n21-n22)*(1+2*beta)**n121
    def f(t): return ((3**n2<

A385825 a(n) = Sum_{k=0..n} (binomial(n, k) mod 5).

Original entry on oeis.org

1, 2, 4, 8, 11, 2, 4, 8, 16, 22, 4, 8, 16, 22, 34, 8, 16, 22, 44, 48, 11, 22, 34, 48, 61, 2, 4, 8, 16, 22, 4, 8, 16, 32, 44, 8, 16, 32, 44, 68, 16, 32, 44, 88, 96, 22, 44, 68, 96, 122, 4, 8, 16, 22, 34, 8, 16, 32, 44, 68, 16, 32, 59, 68, 106, 22, 44, 68, 116, 142

Offset: 0

Chai Wah Wu, Jul 09 2025

nonn

Chai Wah Wu, Table of n, a(n) for n = 0..10000
Richard Garfield and Herbert S. Wilf, The distribution of the binomial coefficients modulo p, Journal of Number Theory, 41 (1) (1992), 1-5.

Cf. A001316, A051638, A384715, A385285, A385741.

a[n_]:=Sum[Mod[Binomial[n,k],5],{k,0,n}];Array[a,60,0] (* James C. McMahon, Jul 10 2025 *)

from gmpy2 import digits
from sympy.abc import x
from sympy import Poly, rem
def A385825(n):
    k = (1,2,4,3)
    s = digits(n,5)
    t = [s.count(str(i)) for i in range(1,5)]
    G = 2**t[0]*(x+2)**t[1]*(2*x**2+3)**t[3]*(2*x**3+2)**t[2]
    c = Poly(rem(G,x**4-1),x).all_coeffs()[::-1]
    return int(sum(k[i]*c[i] for i in range(len(c)) if c[i]))

Row sums of A095140. - R. J. Mathar, Jul 19 2025

A385435 Row sums of A385434.

Original entry on oeis.org

1, 2, 2, 4, 4, 8, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 13, 26, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 32, 8, 16, 16, 32, 26, 52, 4, 8, 8, 16, 13, 26, 8, 16, 16, 32, 26, 52, 13, 26, 26, 52, 40, 80, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 32, 8, 16, 16, 32, 26, 52, 4, 8, 8

Offset: 0

David Radcliffe, Jun 28 2025

Donald E. Knuth and Herbert S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math., 396:212-219, 1989.
Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014. (See Equation (80) on p. 31.)

Cf. A007318, A051638, A022166, A385434.

Total/@Table[Mod[QBinomial[n, k, 2], 3], {n, 0,74}, {k, 0, n}]  (* James C. McMahon, Jun 29 2025 *)

from gmpy2 import digits
def A385435(n): return 3*3**(s:=digits(n>>1,3)).count('2')-1<>1,3)).count('2')-1<>1 # Chai Wah Wu, Jul 10 2025

a(2n) = A051638(n), a(2n+1) = 2*A051638(n).

A385826 a(n) = Sum_{k=0..n} (binomial(n, k) mod 7).

Original entry on oeis.org

1, 2, 4, 8, 16, 18, 22, 2, 4, 8, 16, 32, 36, 44, 4, 8, 16, 32, 43, 58, 67, 8, 16, 32, 36, 72, 60, 92, 16, 32, 43, 72, 81, 120, 121, 18, 36, 58, 60, 120, 100, 144, 22, 44, 67, 92, 121, 144, 169, 2, 4, 8, 16, 32, 36, 44, 4, 8, 16, 32, 64, 72, 88, 8, 16, 32, 64, 86

Offset: 0

Chai Wah Wu, Jul 09 2025

nonn

Sum of n-th row of Pascal's triangle mod 7, A095142.

Chai Wah Wu, Table of n, a(n) for n = 0..10000
Richard Garfield and Herbert S. Wilf, The distribution of the binomial coefficients modulo p, Journal of Number Theory, 41 (1) (1992), 1-5.

Cf. A001316, A051638, A384715, A385285, A385741, A385825.

from gmpy2 import digits
from sympy.abc import x
from sympy import Poly, rem
def A385826(n):
    k = (1,3,2,6,4,5)
    s = digits(n,7)
    t = [s.count(str(i)) for i in range(1,7)]
    G = 2**t[0]*(2*x+2)**t[2]*(x**2+2)**t[1]*(3*x**3+4)**t[5]*(2*x**4+x**3+2)**t[3]*(2*x**5+2*x+2)**t[4]
    c = Poly(rem(G,x**6-1),x).all_coeffs()[::-1]
    return int(sum(k[i]*c[i] for i in range(len(c)) if c[i]))

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Scheme

Formula

Extensions

A083093 Triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Python

Python

Formula

A037301 Numbers whose base-2 and base-3 expansions have the same digit sum.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A384715 a(n) = Sum_{k=0..n} (binomial(n, k) mod 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Python

Formula

A083095 a(n) = A083094(n)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A083094 Numbers k such that Sum_{j=0..k} (binomial(k,j) mod 3) is odd.