|
| |
|
|
A086839
|
|
Number of steps needed to reverse a pattern of length 2*n of cellular automaton Rule 90.
|
|
0
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
LINKS
| 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: A077629 A184467 A004794 * A064208 A078004 A197728
Adjacent sequences: A086836 A086837 A086838 * A086840 A086841 A086842
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frank Buss (fb(AT)frank-buss.de), Aug 08 2003
|
| |
|
|
