A181533 - OEIS

%I #22 Dec 29 2024 05:56:32

%S 2,4,8,8,12,34,58,96,188,334,574,1046,1874,3308,5928,10608,18872,

%T 33694,60194,107338,191542,341950,610146,1088790,1943262,3467858,

%U 6188534,11044356,19709736,35173564

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

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

%C 2) For each string apply the following rules:

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

%C 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

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

%C 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

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

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

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

%o (PARI) padbin(i, n) = {b = binary(i); off = n - #b; vector(n, i, if (i> off, b[i - off], 0));}

%o kprec(k, n) = if (kp = k-1, kp, n);

%o knext(k, n) = if ((kn = k+1) > n, 1, kn);

%o binv(v) = subst(Pol(v), x, 2);

%o 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;}

%o 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

%K nonn,base,more

%O 1,1

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

%E a(12)-a(20) from _Michel Marcus_, Apr 21 2014

%E a(21)-a(30) from _Giovanni Resta_, Apr 22 2014