A118175 Binary representation of n-th iteration of the Rule 220 elementary cellular automaton starting with a single black cell.

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

Offset: 0

Author

Eric W. Weisstein, Apr 13 2006

Keywords

• nonn
• tabf

Comments

From Franklin T. Adams-Watters, Jul 05 2009: (Start)

Divided into rows of length 2n, row n consists of n 1's followed by n 0's.

Characteristic function of A061885, 1-based characteristic function of A004201. (End)

From Wolfdieter Lang, Dec 05 2012: (Start)

The row lengths sequence is A005408 (the odd numbers). The sum of row No. n is given by A000027(n+1).

This table is the first difference table of the q-binomial (Gauss polynomial) coefficient table G(2;n,k) = [q^k]( [n+2,2]_q) (see table A008967): a(n,k) = G(2;n,k) - G(2;n-1,k). The o.g.f. for the row polynomials is therefore G2(q,z) = (1-z)/Product((1-q^j*z),j=0..2) = 1/((1-q*z)*(1-q^2*z)). Therefore, a(n,k) determines the number of partitions of k into precisely n parts, each <= 2. It determines also the number of partitions of k into at most 2 parts, each <= n but not <= (n-1), i.e., with part n present. See comments on A008967 regarding partitions.

From the o.g.f. G2(q,z) it should be clear that there are 0's for n > k and only 1's for k = n,...,2*n.

(End)

This sequence is also generated by Rule 252. - Robert Price, Jan 31 2016

a(n) is 1 if the nearest square to n is >= n, otherwise 0. - Branko Curgus, Apr 25 2017

Examples

			The table a(n,k) begins:
  n\k 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 ...
  0:  1
  1:  0  1  1
  2:  0  0  1  1  1
  3:  0  0  0  1  1  1  1
  4:  0  0  0  0  1  1  1  1  1
  5:  0  0  0  0  0  1  1  1  1  1  1
  6:  0  0  0  0  0  0  1  1  1  1  1  1  1
  7:  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
  8:  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1
  9:  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1
... Reformatted and extended by _Wolfdieter Lang_, Dec 05 2012
Partition examples: a(n,k) = 0 if n>k because the maximal number of parts of a partition of k is k. a(n,n) = 1, n >= 1, because only the partition 1^n has n parts, and 1 <= 2.
  a(2,3) = 1 because the only partition of 3 with 2 parts, each <= 2, is 1,2. Also, the only partition of 3 with at most 2 parts, each <= 2, and a part 2 present is also 1,2.
  a(5,7) =1 because the only 5-part partition of 7 with maximal part 2 is 1^3,2^3. Also, the only partition of 7 with at most 2 parts, each <= 5, which a part 5 present is 2,5.
		

Links

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

Crossrefs

Cf. A083420, A219238.

Programs

Mathematica

Table[1 - Ceiling[Sqrt[n]] + Round[Sqrt[n]], {n, 1, 257}] (* Branko Curgus, Apr 26 2017 *)
Table[{Array[1&,n],Array[0&,n]},{n,1,5}]//Flatten (* Wolfgang Hintze, Jul 28 2017 *)

Python

from math import isqrt
def A118175(n): return 1+int(n-(m:=isqrt(n+1))*(m+1)>=0)-int(m**2!=n+1) # Chai Wah Wu, Jul 30 2022

Formula

a(n) = 1 - A079813(n+1). - Philippe Deléham, Jan 02 2012

a(n) = 1 - ceiling(sqrt(n+1)) + round(sqrt(n+1)). - Branko Curgus, Apr 27 2017 [Corrected by Ridouane Oudra, Dec 01 2019]

G.f.: x/(1 - x)*( Sum_{n >= 1} x^(n^2-n)*(1-x^n)) = 1/(2-2*x)* ( x + x^(3/4)*EllipticTheta(2,0,x) - x*EllipticTheta(3,0,x) ). - Wolfgang Hintze, Jul 28 2017

a(n) = floor(sqrt(n+1)+1/2) - floor(sqrt(n)) = round(sqrt(n+1)) - floor(sqrt(n)). - Ridouane Oudra, Dec 01 2019