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

Author

Paul Tek, Oct 17 2015

Keywords

• nonn

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.

Examples

			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.
		

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)

Crossrefs

Cf. A067398.

Programs

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

Perl

See Links section.

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