|
%I #18 Apr 22 2014 04:18:22
%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
%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
|
