|
|
A086839
|
|
Number of steps needed to reverse a pattern of length 2*n of cellular automaton Rule 90.
|
|
1
|
|
|
1, 3, 7, 7, 31, 63, 15, 15, 511, 63, 2047, 1023, 511, 16383, 31, 31, 4095, 87381, 4095, 1023, 127, 4095, 8388607, 2097151, 255, 67108863, 1048575, 511, 536870911, 1073741823, 63
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Rule 90
|
|
FORMULA
|
It appears that a(n)=2*n-1 for n=2^m.
|
|
EXAMPLE
|
a(3)=7 because all patterns of length 2*n=6 for Rule 90 are mirrored in 7 cellular automaton steps.
|
|
PROG
|
(Java) public class Rule90 { public static void main(String args[]) { for (int len = 2; len < 100; len += 2) { long count = 1; for (int i = 0; i < len; i++) count *= 2; int max = -1; for (int i = 0; i < count; i++) { long value = i;
// reverse value long reverse = 0; for (long b1 = 1, b2 = count / 2; b2 > 0; b1 *= 2, b2 /= 2) { if ((value & b1) != 0) reverse |= b2; }
// count steps for reversing int steps = 0; long current = value; while (current != reverse) { steps++; current = (current >> 1) ^ (current << 1) & (count - 1); }
// check if more than the current maximum if (steps > max) max = steps; } System.out.println(max + ", "); } } }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Frank Buss (fb(AT)frank-buss.de), Aug 08 2003
|
|
STATUS
|
approved
|
|
|
|