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,2

Links

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

Rich Holmes, Rule 90 on a Line Segment

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

Sequence in context: A004794 A336719 A272981 * A359322 A316258 A258405

Adjacent sequences: A086836 A086837 A086838 * A086840 A086841 A086842

Keyword

nonn

Author

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

Status

approved