A006943 Rows of Sierpiński's triangle (Pascal's triangle mod 2).
1, 11, 101, 1111, 10001, 110011, 1010101, 11111111, 100000001, 1100000011, 10100000101, 111100001111, 1000100010001, 11001100110011, 101010101010101, 1111111111111111, 10000000000000001, 110000000000000011
Offset: 0
Examples
From _Daniel Forgues_, Jun 20 2011: (Start) Terms as products of distinct Fermat numbers in binary representation (Cf. A080176 comment) (Cf. Sierpiński's triangle on OEIS Wiki): a(0) = 1 = (empty product); a(1) = 11 = F_0; a(2) = 101 = F_1; a(3) = 1111 = 11*101 = F_0*F_1; a(4) = 10001 = F_2; a(5) = 110011 = 11*10001 = F_0*F_2; a(6) = 1010101 = 101*10001 = F_1*F_2; a(7) = 11111111 = 11*101*10001 = F_0*F_1*F_2. (End)
References
- C. Pickover, Mazes for the Mind, St. Martin's Press, NY, 1992, p. 353.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
Links
- N. J. A. Sloane, Table of n, a(n) for n = 0..200
- Antti Karttunen, On Pascal's Triangle Modulo 2 in Fibonacci Representation, Fibonacci Quarterly, 42 (2004), 38-46. (For Denton Hewgill's identity)
- OEIS Wiki, Sierpinski's triangle
- 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.
- Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
- Stephen Wolfram, A New Kind of Science
- Index to Elementary Cellular Automata
- Index entries for sequences related to cellular automata
Crossrefs
Programs
-
Maple
A006943 := proc(n) local k; add((binomial(n,k) mod 2)*10^k, k=0..n); end;
-
Mathematica
f[n_] := FromDigits@ Mod[Binomial[n, Range[0, n]], 2]; Array[f, 17, 0] (* Robert G. Wilson v, Jun 26 2011 *)
-
Python
def A006943(n): return sum((bool(~n&n-k)^1)*10**k for k in range(n+1)) # Chai Wah Wu, May 03 2023
Formula
From Daniel Forgues, Jun 20-21 2011: (Start)
In the following formulas, [...]_2 means converted to base 2.
a(n) = [Sum_{i=0..n} (binomial(n,i) mod 2) 2^i]_2, n >= 0.
From row n, 0 <= n <= 2^k - 1, k >= 0, being
a(n) = [Product_{i=0..k-1} (F_i)^(alpha_i)]_2, alpha_i in {0, 1},
where for k = 0, we get the empty product, i.e., 1, giving a(0) = 1,
we induce from the triangle that row 2^k + n, 0 <= n <= 2^k - 1, is
a(2^k + n) = a(n)*[F_k]_2, k >= 0.
Denton Hewgill's identity (cf. links):
a(n) = [Product_{i>=0} (F_i)^(floor(n/2^i) mod 2)]_2, F_i = 2^(2^i)+1.
a(0) = 1; a(n) = [Product_{i=0..floor(log_2(n))} (F_i)^(floor(n/2^i) mod 2)]_2, F_i = 2^(2^i)+1, n >= 1. (End)
From Vladimir Shevelev, Dec 26-27 2013: (Start)
Sum_{n>=0} 1/a(n)^r = Product_{k>=0} (1 + 1/(10^(2^k)+1)^r),
Sum_{n>=0} (-1)^A000120(n)/a(n)^r = Product_{k>=0} (1 - 1/(10^(2^k)+1)^r), where r > 0 is a real number.
In particular,
Sum_{n>=0} 1/a(n) = Product_{k>=0} (1 + 1/(10^(2^k)+1)) = 1.10182034...;
Sum_{n>=0} (-1)^A000120(n)/a(n) = 0.9;
a(2^n) = 10^(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)) = 99*(10^(2^(t-1)+1))/(10^(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) = 101*a(4*n);
a(8*n+4) = (10001/101)*a(8*n+2);
a(16*n+8) = (100000001/1010101)*(16*n+6), etc. (End)
From Tom Edgar, Oct 11 2015: (Start)
a(2*n+1) = 11*a(2*n).
a(n) = Product_{b_j != 0} a(2^j) where n = Sum_{j>=0} b_j*2^j is the binary representation of n.
(End)
Extensions
More terms from James Sellers, Aug 21 2000
Edited by Daniel Forgues, Jun 20 2011
Comments