A086839 Number of steps needed to reverse a pattern of length 2*n of cellular automaton Rule 90.

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

Offset: 1

Author

Frank Buss (fb(AT)frank-buss.de), Aug 08 2003

Keywords

• nonn

Examples

			a(3)=7 because all patterns of length 2*n=6 for Rule 90 are mirrored in 7 cellular automaton steps.
		

Links

• Rich Holmes, Rule 90 on a Line Segment
• Eric Weisstein's World of Mathematics, Rule 90

Programs

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 + ", "); } } }

Formula

It appears that a(n)=2*n-1 for n=2^m.