A038183 -id:A038183 - cp's OEIS frontend

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1

Offset: 0

N. J. A. Sloane

Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - N. J. A. Sloane, Jan 18 2016
Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002
Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - Philippe Deléham, Oct 02 2003
Self-inverse when regarded as an infinite lower triangular matrix over GF(2).
Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]
Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - Philippe Deléham, Jun 18 2005
J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17, ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005
When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - David Callan, Oct 27 2006
Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1, ...). - Gary W. Adamson, Jul 10 2008
T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010
The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - Johannes W. Meijer, Jun 05 2011
Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - Marcus Jaiclin, Feb 07 2012
T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012
T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012
From Vladimir Shevelev, Dec 31 2013: (Start)
Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.
Note that: s_n(1)  = A001316(n),
           s_n(2)  = A001317(n),
           s_n(3)  = A100307(n),
           s_n(4)  = A001317(2*n),
           s_n(5)  = A100308(n),
           s_n(6)  = A100309(n),
           s_n(7)  = A100310(n),
           s_n(8)  = A100311(n),
           s_n(9)  = A100307(2*n),
           s_n(10) = A006943(n),
           s_n(16) = A001317(4*n),
           s_n(25) = A100308(2*n), etc.
The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)
Comment from N. J. A. Sloane, Jan 18 2016: (Start)
Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:
  [1, 1, 1, 1, 1, 1]
  [1, 0, 1, 0, 1, 0]
  [1, 1, 0, 0, 1, 1]
  [1, 0, 0, 0, 1, 0]
  [1, 1, 1, 1, 0, 0]
  [1, 0, 1, 0, 0, 0].
Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)
See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - M. F. Hasler, Sep 18 2016
From Valentin Bakoev, Jul 11 2020: (Start)
The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:
1 0     1 0 0 0      1 0 0 0 0 0 0 0
1 1     1 1 0 0      1 1 0 0 0 0 0 0   - It is seen the self-similarity of the
        1 0 1 0      1 0 1 0 0 0 0 0     matrices M_1, M_2, ..., M_n, ...,
        1 1 1 1      1 1 1 1 0 0 0 0     analogously to the Sierpinski's fractal.
                     1 0 0 0 1 0 0 0
                     1 1 0 0 1 1 0 0
                     1 0 1 0 1 0 1 0
                     1 1 1 1 1 1 1 1
M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)
Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - Richard L. Ollerton, Dec 14 2021

			Triangle begins:
              1,
             1,1,
            1,0,1,
           1,1,1,1,
          1,0,0,0,1,
         1,1,0,0,1,1,
        1,0,1,0,1,0,1,
       1,1,1,1,1,1,1,1,
      1,0,0,0,0,0,0,0,1,
     1,1,0,0,0,0,0,0,1,1,
    1,0,1,0,0,0,0,0,1,0,1,
   1,1,1,1,0,0,0,0,1,1,1,1,
  1,0,0,0,1,0,0,0,1,0,0,0,1,
  ...

Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).
John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).
H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].
J.-P. Allouche and V. Berthe, Triangle de Pascal, complexité et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.
J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],
J. Baer, Explore patterns in Pascal's Triangle
Valentin Bakoev, Fast Bitwise Implementation of the Algebraic Normal Form Transform, Serdica J. of Computing 11 (2017), No 1, 45-57.
Valentin Bakoev, Properties and links concerning M_n
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
A. Bogomolny, Dot Patterns and Sierpinski Gasket
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.
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.
S. Butkevich, Pascal Triangle Applet
David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II
C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.
Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
Brady Haran, Chaos Game, Numberphile video, YouTube (April 27, 2017).
I. Kobayashi et al., Pascal's Triangle
Dr. Math, Regular polygon formulas [Broken link?]
Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
National Curve Bank, Sierpinski Triangles
Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.
S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.
A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.
N. J. A. Sloane, Illustration of rows 0 to 32 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 64 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 128 (encoignure style)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102
Index entries for sequences related to cellular automata
Index entries for triangles and arrays related to Pascal's triangle
Index entries for sequences generated by sieves

Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (m = 2), A083093 (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).
Other versions: A090971, A038183.
Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.
From Johannes W. Meijer, Jun 05 2011: (Start)
A106344 is a skew version of this triangle.
Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

import Data.Bits (xor)
a047999 :: Int -> Int -> Int
a047999 n k = a047999_tabl !! n !! k
a047999_row n = a047999_tabl !! n
a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010

A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >;
[A047999(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 03 2024

# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016
ST:=[1,1,1]; a:=1; b:=2; M:=10;
for n from 2 to M do ST:=[op(ST),1];
for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od:
ST:=[op(ST),1];
a:=a+n; b:=a+n; od:
ST; # N. J. A. Sloane
# alternative
A047999 := proc(n,k)
    modp(binomial(n,k),2) ;
end proc:
seq(seq(A047999(n,k),k=0..n),n=0..12) ; # R. J. Mathar, May 06 2016

Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* Robert G. Wilson v, May 26 2004 *)
rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)
Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* Harvey P. Dale, Jun 26 2019 *)
A047999[n_,k_]:= Boole[BitAnd[n-k,k]==0];
Table[A047999[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 03 2025 *)

\\ Recurrence for Pascal's triangle mod p, here p = 2.
p = 2; s=13; T=matrix(s,s); T[1,1]=1;
for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p ));
for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ Gerald McGarvey, Oct 10 2009

A011371(n)=my(s);while(n>>=1,s+=n);s
T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013

T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016

def A047999_T(n,k):
    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 09 2016 and N. J. A. Sloane, Feb 10 2016
Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).
T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0 < k < n; T(n,0) = T(n,n) = 1. - Reinhard Zumkeller, Dec 13 2009
T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0 < k < n; T(n,0) = T(n,n) = 1. - Rick L. Shepherd, Feb 23 2018
From Vladimir Shevelev, Dec 31 2013: (Start)
For polynomial {s_n(x)} we have
s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),
if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;
G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0Let x>1, t>0 be real numbers. Then
Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);
Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).
In particular, for t=1, x>1, we have
Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)
From Valentin Bakoev, Jul 11 2020: (Start)
(See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and kT(i,0) = T(i,i) = 1, or
T(i,j) = 0 if i < j, or
T(i,j) = T(i-k,j), if j < k, or
T(i,j) = T(i-k,j-k), if j >= k.
Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)

Additional links from Lekraj Beedassy, Jan 22 2004

A001317 Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.

Original entry on oeis.org

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, 4294967297, 12884901891, 21474836485, 64424509455, 73014444049, 219043332147, 365072220245, 1095216660735, 1103806595329, 3311419785987

Offset: 0

N. J. A. Sloane

The members are all palindromic in binary, i.e., a subset of A006995. - Ralf Stephan, Sep 28 2004
J. H. Conway writes (in Math Forum): at least the first 31 numbers give odd-sided constructible polygons. See also A047999. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005 [This observation was also made in 1982 by N. L. White (see letter). - N. J. A. Sloane, Jun 15 2015]
Decimal number generated by the binary bits of the n-th generation of the Rule 60 elementary cellular automaton. Thus: 1; 0, 1, 1; 0, 0, 1, 0, 1; 0, 0, 0, 1, 1, 1, 1; 0, 0, 0, 0, 1, 0, 0, 0, 1; ... . - Eric W. Weisstein, Apr 08 2006
Limit_{n->oo} log(a(n))/n = log(2). - Bret Mulvey, May 17 2008
Equals row sums of triangle A166548; e.g., 17 = (2 + 4 + 6 + 4 + 1). - Gary W. Adamson, Oct 16 2009
Equals row sums of triangle A166555. - Gary W. Adamson, Oct 17 2009
For n >= 1, all terms are in A001969. - Vladimir Shevelev, Oct 25 2010
Let n,m >= 0 be such that no carries occur when adding them. Then a(n+m) = a(n)*a(m). - Vladimir Shevelev, Nov 28 2010
Let phi_a(n) be the number of a(k) <= a(n) and respectively prime to a(n) (i.e., totient function over {a(n)}). Then, for n >= 1, phi_a(n) = 2^v(n), where v(n) is the number of 0's in the binary representation of n. - Vladimir Shevelev, Nov 29 2010
Trisection of this sequence gives rows of A008287 mod 2 converted to decimal. See also A177897, A177960. - Vladimir Shevelev, Jan 02 2011
Converting the rows of the powers of the k-nomial (k = 2^e where e >= 1) term-wise to binary and reading the concatenation as binary number gives every (k-1)st term of this sequence. Similarly with powers p^k of any prime. It might be interesting to study how this fails for powers of composites. - Joerg Arndt, Jan 07 2011
This sequence appears in Pascal's triangle mod 2 in another way, too. If we write it as
  1111111...
  10101010...
  11001100...
  10001000...
we get (taking the period part in each row):
  .(1) (base 2) = 1
  .(10) = 2/3
  .(1100) = 12/15 = 4/5
  .(1000) = 8/15
The k-th row, treated as a binary fraction, seems to be equal to 2^k / a(k). - Katarzyna Matylla, Mar 12 2011
From Daniel Forgues, Jun 16-18 2011: (Start)
Since there are 5 known Fermat primes, there are 32 products of distinct Fermat primes (thus there are 31 constructible odd-sided polygons, since a polygon has at least 3 sides). a(0)=1 (empty product) and a(1) to a(31) are those 31 non-products of distinct Fermat primes.
It can be proved by induction that all terms of this sequence are products of distinct Fermat numbers (A000215):
a(0)=1 (empty product) are products of distinct Fermat numbers in { };
a(2^n+k) = a(k) * (2^(2^n)+1) = a(k) * F_n, n >= 0, 0 <= k <= 2^n - 1.
Thus for n >= 1, 0 <= k <= 2^n - 1, and
  a(k) = Product_{i=0..n-1} F_i^(alpha_i), alpha_i in {0, 1},
this implies
  a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}.
(Cf. OEIS Wiki links below.)  (End)
The bits in the binary expansion of a(n) give the coefficients of the n-th power of polynomial (X+1) in ring GF(2)[X]. E.g., 3 ("11" in binary) stands for (X+1)^1, 5 ("101" in binary) stands for (X+1)^2 = (X^2 + 1), and so on. - Antti Karttunen, Feb 10 2016

			Given a(5)=51, a(6)=85 since a(5) XOR 2*a(5) = 51 XOR 102 = 85.
From _Daniel Forgues_, Jun 18 2011: (Start)
  a(0) = 1 (empty product);
  a(1) = 3 = 1 * F_0 = a(2^0+0) = a(0) * F_0;
  a(2) = 5 = 1 * F_1 = a(2^1+0) = a(0) * F_1;
  a(3) = 15 = 3 * 5 = F_0 * F_1 = a(2^1+1) = a(1) * F_1;
  a(4) = 17 = 1 * F_2 = a(2^2+0) = a(0) * F_2;
  a(5) = 51 = 3 * 17 = F_0 * F_2 = a(2^2+1) = a(1) * F_2;
  a(6) = 85 = 5 * 17 = F_1 * F_2 = a(2^2+2) = a(2) * F_2;
  a(7) = 255 = 3 * 5 * 17 = F_0 * F_1 * F_2 = a(2^2+3) = a(3) * F_2;
  ... (End)

Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, 2003, p. 113.
Henry Wadsworth Gould, Exponential Binomial Coefficient Series, Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sept. 1961.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 136-137.

Amiram Eldar, Table of n, a(n) for n = 0..3321 (terms 0..300 from T. D. Noe, terms 301..1023 from Tilman Piesk)
Gary W. Adamson, Letter to N. J. A. Sloane, Apr 29 1994, and MS "Algorithm for the Chinese Remainder Theorem".
Gary W. Adamson and N. J. A. Sloane, Correspondence, May 1994, including Adamson's MSS "Algorithm for Generating nth Row of Pascal's Triangle, mod 2, from n", and "The Tower of Hanoi Wheel".
Cristian Cobeli and Alexandru Zaharescu, Promenade around Pascal Triangle-Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104), No. 1 (2013), pp. 73-98; alternative link.
Richard K. Guy, The Second Strong Law of Small Numbers, Math. Mag, Vol. 63, No. 1 (1990), pp. 3-20. [Annotated scanned copy]
Richard K. Guy and N. J. A. Sloane, Correspondence, 1988.
Denton Hewgill, A relationship between Pascal's triangle and Fermat numbers, Fib. Quart., Vol. 15, No. 2 (1977), pp. 183-184.
A. J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata with even rule numbers, Fig. 4.
Dr. Math, Regular polygon formulas.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
OEIS Wiki, Constructible odd-sided polygons and Sierpinski's triangle.
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2, J. Alg. Number Theory, Vol. 7, No. 1 (2012) pp. 11-29, preprint, arXiv:1011.6083 [math.NT], 2010-2012.
John Frederick Sweeney, Clifford Clock and the Moolakaprithi Cube, 2014. See p. 26. - _N. J. A. Sloane_, Mar 20 2014
Eric Weisstein's World of Mathematics, Rule 60 and Rule 102.
Neil L. White, Letter to N. J. A. Sloane, Apr 15 1982.
R. G. Wilson, V, Letter to N. J. A. Sloane, Aug. 1993.
Index entries for sequences related to cellular automata
Index entries for sequences operating on polynomials in ring GF(2)[X]

Cf. A000079, A000215 (Fermat numbers), A047999, A048720, A054432, A173019, A177882, A177897, A177960, A193231, A230116, A247282, A249184, A268391.
Cf. A038183 (odd bisection, 1D Cellular Automata Rule 90).
Iterates of A048724 (starting from 1).
Row 3 of A048723.
Positions of records in A268389.
Positions of ones in A268669 and A268384 (characteristic function).
Not the same as A045544 nor as A053576.
Cf. A045544.

a001317 = foldr (\u v-> 2*v + u) 0 . map toInteger . a047999_row
-- Reinhard Zumkeller, Nov 24 2012
(Scheme, with memoization-macro definec, two variants)
(definec (A001317 n) (if (zero? n) 1 (A048724 (A001317 (- n 1)))))
(definec (A001317 n) (if (zero? n) 1 (A048720bi 3 (A001317 (- n 1))))) ;; Where A048720bi implements the dyadic function given in A048720.
;; Antti Karttunen, Feb 10 2016

[&+[(Binomial(n, i) mod 2)*2^i: i in [0..n]]: n in [0..41]]; // Vincenzo Librandi, Feb 12 2016

A001317 := proc(n) local k; add((binomial(n,k) mod 2)*2^k, k=0..n); end;

a[n_] := Nest[ BitXor[#, BitShiftLeft[#, 1]] &, 1, n]; Array[a, 42, 0] (* Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007 *)
NestList[BitXor[#,2#]&,1,50] (* Harvey P. Dale, Aug 02 2021 *)

PARI
```
a(n)=sum(i=0,n,(binomial(n,i)%2)*2^i)
```

a=1; for(n=0, 66, print1(a,", "); a=bitxor(a,a<<1) ); \\ Joerg Arndt, Mar 27 2013

A001317(n,a=1)={for(k=1,n,a=bitxor(a,a<<1));a} \\ M. F. Hasler, Jun 06 2016

a(n) = subst(lift(Mod(1+'x,2)^n), 'x, 2); \\ Gheorghe Coserea, Nov 09 2017

from sympy import binomial
def a(n): return sum([(binomial(n, i)%2)*2**i for i in range(n + 1)]) # Indranil Ghosh, Apr 11 2017

def A001317(n): return int(''.join(str(int(not(~n&k))) for k in range(n+1)),2) # Chai Wah Wu, Feb 04 2022

a(n+1) = a(n) XOR 2*a(n), where XOR is binary exclusive OR operator. - Paul D. Hanna, Apr 27 2003
a(n) = Product_{e(j, n) = 1} (2^(2^j) + 1), where e(j, n) is the j-th least significant digit in the binary representation of n (Roberts: see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
a(2*n+1) = 3*a(2*n). Proof: Since a(n) = Product_{k in K} (1 + 2^(2^k)), where K is the set of integers such that n = Sum_{k in K} 2^k, clearly K(2*n+1) = K(2*n) union {0}, hence a(2*n+1) = (1+2^(2^0))*a(2*n) = 3*a(2*n). - Emmanuel Ferrand and Ralf Stephan, Sep 28 2004
a(32*n) = 3 ^ (32 * n * log(2) / log(3)) + 1. - Bret Mulvey, May 17 2008
For n >= 1, A000120(a(n)) = 2^A000120(n). - Vladimir Shevelev, Oct 25 2010
a(2^n) = A000215(n); a(2^n-1) = a(2^n)-2; for n >= 1, m >= 0,
a(2^(n-1)-1)*a(2^n*m + 2^(n-1)) = 3*a(2^(n-1))*a(2^n*m + 2^(n-1)-2). - Vladimir Shevelev, Nov 28 2010
Sum_{k>=0} 1/a(k) = Product_{n>=0} (1 + 1/F_n), where F_n=A000215(n);
Sum_{k>=0} (-1)^(m(k))/a(k) = 1/2, where {m(n)} is Thue-Morse sequence (A010060).
If F_n is defined by F_n(z) = z^(2^n) + 1 and a(n) by (1/2)*Sum_{i>=0}(1-(-1)^{binomial(n,i)})*z^i, then, for z > 1, the latter two identities hold as well with the replacement 1/2 in the right hand side of the 2nd one by 1-1/z. - Vladimir Shevelev, Nov 29 2010
G.f.: Product_{k>=0} ( 1 + z^(2^k) + (2*z)^(2^k) ). - conjectured by Shamil Shakirov, proved by Vladimir Shevelev
a(n) = A000225(n+1) - A219843(n). - Reinhard Zumkeller, Nov 30 2012
From Antti Karttunen, Feb 10 2016: (Start)
a(0) = 1, and for n > 1, a(n) = A048720(3, a(n-1)) = A048724(a(n-1)).
a(n) = A048723(3,n).
a(n) = A193231(A000079(n)).
For all n >= 0: A268389(a(n)) = n.
(End)

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

A048723 Binary "exponentiation" without carries: {0..y}^{0..x}, where y (column index) is binary encoding of GF(2)-polynomial and x (row index) is the exponent.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 8, 5, 4, 1, 0, 1, 16, 15, 16, 5, 1, 0, 1, 32, 17, 64, 17, 6, 1, 0, 1, 64, 51, 256, 85, 20, 7, 1, 0, 1, 128, 85, 1024, 257, 120, 21, 8, 1, 0, 1, 256, 255, 4096, 1285, 272, 107, 64, 9, 1

Offset: 0

Antti Karttunen, Apr 26 1999

			1 0 0 0 0 0 0 0 0 ...
1 1 1 1 1 1 1 1 1 ...
1 2 4 8 16 32 64 128 256 ...
1 3 5 15 17 51 85 255 257 ...
1 4 16 64 256 1024 4096 16384 65536 ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Cf. ordinary power table A004248 and A034369, A034373.
Cf. A048710. Row 3: A001317, Row 5: A038183 (bisection of row 3), Row 7: A038184. Column 2: A000695, diagonal of A048720.
Main diagonal: A048731.

# Xmult and trinv have been given in A048720.
Xpower := proc(nn,mm) option remember; if(0 = mm) then RETURN(1); # By definition, also 0^0 = 1. else RETURN(Xmult(nn,Xpower(nn,mm-1))); fi; end;

trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; s];
Xpower[nn_, mm_] := Xpower[nn, mm] = If[0 == mm, 1, Xmult[nn, Xpower[nn, mm - 1]]];
a[n_] := Xpower[n - (trinv[n]*(trinv[n] - 1))/2, (trinv[n] - 1)*((1/2)* trinv[n] + 1) - n];
Table[a[n], {n, 0, 65}] (* Jean-François Alcover, Mar 04 2016, adapted from Maple *)

a(n) = Xpower( (n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n) );

A048725 a(n) = Xmult(n,5) or rule90(n,1).

Original entry on oeis.org

0, 5, 10, 15, 20, 17, 30, 27, 40, 45, 34, 39, 60, 57, 54, 51, 80, 85, 90, 95, 68, 65, 78, 75, 120, 125, 114, 119, 108, 105, 102, 99, 160, 165, 170, 175, 180, 177, 190, 187, 136, 141, 130, 135, 156, 153, 150, 147, 240, 245, 250, 255, 228, 225, 238, 235, 216, 221, 210

Offset: 0

Antti Karttunen, Apr 26 1999

The orbit of 1 under iteration of this function is the Sierpinski gasket A038183. It is called "rule 90" because the 8 bits of 90 = 01011010 in binary give bit k of the result as function of the value in {0,...,7} made out of bits k,k+1,k+2 of the input (i.e., floor(input / 2^k) mod 8). - M. F. Hasler, Oct 09 2017

			   n (in binary) | 4n [binary] | n XOR 4n [binary] | [decimal] = a(n)
          0      |        0    |           0       |        0
          1      |      100    |         101       |        5
         10      |     1000    |        1010       |       10
         11      |     1100    |        1111       |       15
        100      |    10000    |       10100       |       20
        101      |    10100    |       10001       |       17
   etc.

Alois P. Heinz, Table of n, a(n) for n = 0..16383

Cf. A048720, A048705, A048710, A048724, A048727, A048729.
Cf. A038183.
Cf. A353167 (terms sorted).

a:= n-> Bits[Xor](n*4, n):
seq(a(n), n=0..120);  # Alois P. Heinz, Aug 24 2019

Table[ BitXor[4n, n], {n, 0, 60}] (* Robert G. Wilson v, Jul 06 2006 *)

a(n)=bitxor(n,4*n) \\ Charles R Greathouse IV, Oct 03 2016

def A048725(n): return n^ n<<2 # Chai Wah Wu, Jun 29 2022

a(n) = n XOR n*2 XOR (n XOR n*2)*2 = A048724(A048724(n)). - Reinhard Zumkeller, Nov 12 2004

a(n) = n XOR (4n). - M. F. Hasler, Oct 09 2017

A038184 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, converted to a decimal number.

Original entry on oeis.org

1, 7, 21, 107, 273, 1911, 5189, 28123, 65793, 460551, 1381653, 7039851, 17829905, 124809335, 340873541, 1840690907, 4295032833, 30065229831, 90195689493, 459568513131, 1172543963409, 8207807743863, 22286925370437

Offset: 0

Antti Karttunen, Feb 15 1999

nonn

Generation n (starting from the generation 0: 1) interpreted as a binary number, but written in base 10.
Rows of the mod 2 trinomial triangle (A027907), interpreted as binary numbers: 1, 111, 10101, 1101011, ... (A118110). - Jacob A. Siehler, Aug 25 2006
See A071053 for number of ON cells. - N. J. A. Sloane, Jul 28 2014

			Bit patterns with "0" replaced by "." for visibilty [_Georg Fischer_, Dec 16 2021]:
  0:                    1
  1:                   111
  2:                  1.1.1
  3:                 11.1.11
  4:                1...1...1
  5:               111.111.111
  6:              1.1...1...1.1
  7:             11.11.111.11.11
  8:            1.......1.......1
  9:           111.....111.....111
  10:         1.1.1...1.1.1...1.1.1
  11:        11.1.11.11.1.11.11.1.11
  12:       1...1.......1.......1...1
  13:      111.111.....111.....111.111
  14:     1.1...1.1...1.1.1...1.1...1.1
  15:    11.11.11.11.11.1.11.11.11.11.11

Gheorghe Coserea, Table of n, a(n) for n = 0..200
Alan J. Macfarlane, On generating functions of some sequences of integers defined in the evolution of the cellular automaton Rule 150, Preprint 2016.
Eric Weisstein's World of Mathematics, Rule 150
Index entries for sequences related to cellular automata

Cf. A006977, A006978, A038183, A038185 (other cellular automata).
Cf. A048710, A048720, A027907, A001317, A071053.
This sequence, A071036 and A118110 are equivalent descriptions of the Rule 150 automaton.

bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
sigmagen := proc(n) option remember: if (0 = n) then (1)
else sum('((bit_n(sigmagen(n-1),i)+bit_n(sigmagen(n-1),i-1)+bit_n(sigmagen(n-1),i-2)) mod 2)*(2^i)', 'i'=0..(2*n)) fi: end:

f[n_] := Sum[2^k*Coefficient[ #, x, k], {k, 0, 2n}] & @ Expand[(1 + x + x^2)^n, Modulus -> 2] (* Jacob A. Siehler, Aug 25 2006 *)

a(n) = subst(lift(Pol(Mod([1,1,1],2),'x)^n),'x,2);
vector(23,n,a(n-1))  \\ Gheorghe Coserea, Jun 12 2016

A048757 Sum_{i=0..2n} (C(2n,i) mod 2)Fibonacci(i+2) = Sum_{i=0..n} (C(n,i) mod 2)Fibonacci(2i+2).

Original entry on oeis.org

1, 4, 9, 33, 56, 203, 441, 1596, 2585, 9353, 20304, 73461, 124033, 448756, 974169, 3524577, 5702888, 20633243, 44791065, 162055596, 273617239, 989956471, 2149017696, 7775219067, 12591974497, 45558191716, 98898651657

Offset: 0

Antti Karttunen, Jul 13 1999

The history of 1-D CA Rule 90 starting from the seed pattern 1 interpreted as Zeckendorffian expansion.

Also, product of distinct terms of A001566 and appropriate Fibonacci or Lucas numbers: a(n) = FL(n+2)Product(L(2^i)^bit(n,i),i=0..) Here L(2^i) = A001566 and FL(n) = n-th Fibonacci number if n even, n-th Lucas number if n odd. bit(n,i) is the i-th digit (0 or 1) in the binary expansion of n, with the least significant digit being bit(n,0).

			1 = Fib(2) = 1;
101 = Fib(4) + Fib(2) = 3 + 1 = 4;
10001 = Fib(6) + Fib(2) = 8 + 1 = 9;
1010101 = Fib(8) + Fib(6) + Fib(4) + Fib(2) = 21 + 8 + 3 + 1 = 33; etc.

Antti Karttunen, On Pascal's Triangle Modulo 2 in Fibonacci Representation, Fibonacci Quarterly, 42 (2004), 38-46.

a(n) = A022290(A038183(n)) = A022290(A048723(5, n)) = A003622(A051656(n)) = A075148(n, 2)*A050613(n). Third row of A050609, third column of A050610.

Cf. A054433.

Table[Sum[Mod[Binomial[2n, i], 2] Fibonacci[i + 2], {i, 0, 2n}], {n, 0, 19}] (* Alonso del Arte, Apr 27 2014 *)

A070886 Triangle read by rows giving successive states of cellular automaton generated by "Rule 90".

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0

Offset: 0

N. J. A. Sloane, May 19 2002

If either neighbor is 1 then new state is 1, otherwise new state is 0.
Row n has length 2n+1.
Rules #18, #26, #82, #90, #146, #154, #210, #218 all give rise to this sequence. - Hans Havermann

			1; 1,0,1; 1,0,0,0,1; 1,0,1,0,1,0,1; ...

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 25.

Robert Price, Table of n, a(n) for n = 0..9999
Eric Weisstein's World of Mathematics, Rule 90
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata

Cf. A070950, A070887. Alternate rows of A047999. Interpreted as binary numbers: A038183. Interpreted as Zeckendorf-expansions: A048757. Drawn as binary trees: A080263.

rows = 10; ca = CellularAutomaton[90, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, rows-k+1 ;; rows+k-1]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)

More terms from Hans Havermann, May 26 2002

A100311 Modulo 2 binomial transform of 8^n.

Original entry on oeis.org

1, 9, 65, 585, 4097, 36873, 266305, 2396745, 16777217, 150994953, 1090519105, 9814671945, 68736258049, 618626322441, 4467856773185, 40210710958665, 281474976710657, 2533274790395913, 18295873486192705, 164662861375734345

Offset: 0

Paul Barry, Dec 06 2004

8^n may be retrieved through 8^n = Sum_{k=0..n} (-1)^A010060(n-k) * (binomial(n,k) mod 2) * A100311(k).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, arXiv:1011.6083 [math.NT], 2010-2012; J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29.

Cf. A001316, A001317, A010060, A038183, A047999.

Cf. A100307, A100308, A100309, A100310.

[(&+[(Binomial(n,k) mod 2)*8^k: k in [0..n]]): n in [0..40]]; // G. C. Greubel, Jan 25 2023

A100311[n_]:= A100311[n]= Sum[Mod[Binomial[n, k], 2]*8^k, {k, 0, n}];
Table[A100311[n], {n, 0, 30}] (* G. C. Greubel, Jan 25 2023 *)

a=1
for i in range(33):
    print(a, end=", ")
    a = (a*8) ^ a
# Alex Ratushnyak, Apr 22 2012

def A100311(n): return sum((bool(~n&n-k)^1)<<3*k for k in range(n+1)) # Chai Wah Wu, May 02 2023

def A100311(n): return sum( (binomial(n, k)%2)*8^k for k in range(n+1))
[A100311(n) for n in range(41)] # G. C. Greubel, Jan 25 2023

a(n) = Sum_{k=0..n} (binomial(n, k) mod 2)*8^k.
Conjecture: a(0)=1, a(n+1) = (a(n)*8) XOR a(n), where XOR is the bitwise exclusive-or operator. - Alex Ratushnyak, Apr 22 2012
From Vladimir Shevelev, Dec 26-27 2013: (Start)
Sum_{n>=0} 1/a(n)^r = Product_{k>=0} (1 + 1/(8^(2^k)+1)^r),
Sum_{n>=0} (-1)^A000120(n)/a(n)^r = Product_{k>=0} (1 - 1/(8^(2^k)+1)^r), where r>0 is a real number.
In particular,
Sum_{n>=0} 1/a(n) = Product_{k>=0} (1 + 1/(8^(2^k)+1)) = 1.1284805...;
Sum_{n>=0} (-1)^A000120(n)/a(n) = 7/8.
a(2^n) = 8^(2^n) + 1, n >= 0.
Note that analogs of Stephan's limit formulas (see Shevelev link) reduce to the relations:
a(2^t*n+2^(t-1)) = 63*(8^(2^(t-1)+1))/(8^(2^(t-1))-1) * a(2^t*n+2^(t-1)-2), t >= 2.
In particular, for t=2,3,4, we have the following formulas:
a(4*n+2) = 65 * a(4*n);
a(8*n+4) = 4097/65 * a(8*n+2);
a(16*n+8) = (16777217/266305) * a(16*n+6), etc. (End)

A100307 Modulo 2 binomial transform of 3^n.

Original entry on oeis.org

1, 4, 10, 40, 82, 328, 820, 3280, 6562, 26248, 65620, 262480, 538084, 2152336, 5380840, 21523360, 43046722, 172186888, 430467220, 1721868880, 3529831204, 14119324816, 35298312040, 141193248160, 282472589764, 1129890359056

Offset: 0

Paul Barry, Dec 06 2004

3^n may be retrieved through 3^n = Sum_{k=0..n} (-1)^A010060(n-k)*(binomial(n,k) mod 2)*a(k).

Gheorghe Coserea, Table of n, a(n) for n = 0..200
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, arXiv:1011.6083 [math.NT], 2010-2012; J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29.

Cf. A001316, A001317, A038183, A100308, A100309, A100310, A100311.

[(&+[3^k*(Binomial(n, k) mod 2): k in [0..n]]): n in [0..40]]; // G. C. Greubel, Feb 03 2023

Table[Sum[Mod[Binomial[n,k],2]3^k,{k,0,n}],{n,0,40}] (* Harvey P. Dale, Aug 28 2013 *)

a(n) = subst(lift((Mod(1,2)+'x)^n), 'x, 3); \\ Gheorghe Coserea, Jun 11 2016

def A100307(n): return sum((bool(~n&n-k)^1)*3**k for k in range(n+1)) # Chai Wah Wu, May 02 2023

[sum((binomial(n,k)%2)*3^k for k in [0..n]) for n in [0..50]] # Tom Edgar, Oct 11 2015

a(n) = Sum_{k=0..n} (binomial(n, k) mod 2)*3^k.
From Vladimir Shevelev, Dec 26-27 2013: (Start)
Sum_{n>=0} 1/a(n)^r = Product_{k>=0} (1 + 1/(3^(2^k)+1)^r),
Sum_{n>=0} (-1)^A000120(n)/a(n)^r = Product_{k>=0} (1 - 1/(3^(2^k)+1)^r), where r > 0 is a real number.
In particular,
Sum_{n>=0} 1/a(n) = Product_{k>=0} (1 + 1/(3^(2^k)+1)) = 1.391980...;
Sum_{n>=0} (-1)^A000120(n)/a(n) = 2/3.
a(2^n) = 3^(2^n)+1, n >= 0.
Note that analogs of Stephan's limit formulas (see Shevelev link) reduce to the relations:
a(2^t*n+2^(t-1)) = 8*(3^(2^(t-1)+1))/(3^(2^(t-1))-1) * a(2^t*n+2^(t-1)-2), t >= 2.
In particular, for t=2,3,4, we have the following formulas:
  a(4*n+2)  =         10 * a(4*n),
  a(8*n+4)  =     (41/5) * a(8*n+2),
  a(16*n+8) = (3281/410) * a(16*n+6), etc. (End)
From Tom Edgar, Oct 11 2015: (Start)
a(n) = Product_{b_j != 0} a(2^j) where n = Sum_{j>=0} b_j*2^j is the binary representation of n.
a(2*k+1) = 4*a(2*k). (End)

Showing 1-10 of 25 results. Next

cp's OEIS Frontend

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A001317 Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

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

A048723 Binary "exponentiation" without carries: {0..y}^{0..x}, where y (column index) is binary encoding of GF(2)-polynomial and x (row index) is the exponent.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A048725 a(n) = Xmult(n,5) or rule90(n,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A048757 Sum_{i=0..2n} (C(2n,i) mod 2)Fibonacci(i+2) = Sum_{i=0..n} (C(n,i) mod 2)Fibonacci(2i+2).