A263402 Define Z(1) = {1}, and Z(n+1) = Z(n) (+) { x+y, with x and y in Z(n) } for any n>0 (where (+) stands for the symmetric difference of two sets). Then a(n) gives the number of elements in Z(n).

1, 2, 3, 7, 10, 22, 42, 87, 170, 342, 686, 1365, 2727, 5468, 10919, 21857, 43680, 87389, 174756, 349539, 699039, 1398115, 2796191, 5592422, 11184795, 22369639, 44739229, 89478503, 178956950, 357913967, 715827858, 1431655793, 2863311503, 5726623097, 11453246088

Offset

1,2

Comments

a(n) can also be interpreted as the number of ON cells at the n-th stage of the following automaton:

- At first stage, we have only one ON cell at position 1,

- An ON cell appears at position x+y if the cells at positions x and y are ON,

- An ON cell dies at position x+y if the cells at positions x and y are ON.

a(n) <= 2^(n-1) for any n>0.

Links

Paul Tek, Table of n, a(n) for n = 1..250

Paul Tek, PERL program for this sequence

Paul Tek, Graphic representation of the elements in the range [1..300] of the first 300 sets Z(n)

Formula

a(n) = A000120(z(n)) for any n>0

where z(n) is a binary encoding of Z(n), defined as follows:

- z(1) = 2^1,

- z(n+1) = z(n) XOR A067398(z(n)) for any n>0 (where XOR stands for the binary XOR operator).

Example

Z(1) = {1};
Z(2) = {1} (+) {2} = {1,2};
Z(3) = {1,2} (+) {2,3,4} = {1,3,4};
Z(4) = {1,3,4} (+) {2,4,5,6,7,8} = {1,2,3,5,6,7,8};
Hence: a(1) = 1, a(2) = 2, a(3) = 3 and a(4) = 7.

Prog

(Perl) See Links section.
(PARI) lista(nn) = {zprec = Set([1]); print1(#zprec, ", "); for (n=2, nn, zs = setbinop((x, y)->x+y, zprec); zn = setminus(setunion(zprec, zs), setintersect(zprec, zs)); print1(#zn, ", "); zprec = zn; ); } \\ Michel Marcus, Oct 20 2015

Crossrefs

Cf. A067398.

Sequence in context: A318406 A365967 A079380 * A047082 A062113 A346799

Adjacent sequences: A263399 A263400 A263401 * A263403 A263404 A263405

Keyword

nonn

Author

Paul Tek, Oct 17 2015

Status

approved