A181533 Number of values generated by the algorithm given as first comment.

2, 4, 8, 8, 12, 34, 58, 96, 188, 334, 574, 1046, 1874, 3308, 5928, 10608, 18872, 33694, 60194, 107338, 191542, 341950, 610146, 1088790, 1943262, 3467858, 6188534, 11044356, 19709736, 35173564

Offset

1,1

Comments

1) Generate all 2^n different binary string of n bits.

2) For each string apply the following rules:

2.A) if the i-th bit of the string is 1:

the i-th bit of the result is 1 if and only if the (i-1)-th (mod n) AND the (i+1)-th (mod n) bit of the string is 1

2.B) if the i-th bit of the string is 0:

the i-th bit of the result is 1 if and only if the (i-1)-th (mod n) OR the (i+1)-th (mod n) bit of the string is 1

For example: If the original string is 10010, then the result of the algorithm is 01101.

The sequence counts the different possible values generated by the algorithm for all binary strings of length n.

Links

Table of n, a(n) for n=1..30.

Example

For n=4 the 8 possible results generated by the algorithm are: [1001, 0000, 0011, 1111, 0110, 0101, 1010, 1100].

Prog

(PARI) padbin(i, n) = {b = binary(i); off = n - #b; vector(n, i, if (i> off, b[i - off], 0)); }
kprec(k, n) = if (kp = k-1, kp, n);
knext(k, n) = if ((kn = k+1) > n, 1, kn);
binv(v) = subst(Pol(v), x, 2);
transf(v, n) = {tv = vector(n); for (k=1, n, kp = kprec(k, n); kn = knext(k, n); if (v[k], if ((v[kp] == 1) && (v[kn] == 1), tv[k] = 1), if ((v[kp] == 1) || (v[kn] == 1), tv[k] = 1); ); ); tv; }
a(n) = {alls = []; for (i=0, 2^n-1, alls = Set(concat(alls, binv(transf(padbin(i, n), n)))); ); #alls; } \\ Michel Marcus, Apr 21 2014

Crossrefs

Sequence in context: A008218 A073043 A083542 * A263981 A362936 A088244

Adjacent sequences: A181530 A181531 A181532 * A181534 A181535 A181536

Keyword

nonn,base

Author

Arthur Oviedo (aa.oviedo332(AT)uniandes.edu.co), Oct 28 2010

Extensions

a(12)-a(20) from Michel Marcus, Apr 21 2014

a(21)-a(30) from Giovanni Resta, Apr 22 2014

Status

approved