|
Search: id:A086839
|
|
|
| A086839 |
|
Number of steps needed to reverse a pattern of length 2*n of cellular automaton Rule 90. |
|
+0
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; listen)
|
|
|
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.
|
|
PROGRAM
|
(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: A121172 A077629 A004794 this_sequence A064208 A078004 A006834
Adjacent sequences: A086836 A086837 A086838 this_sequence A086840 A086841 A086842
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Frank Buss (fb(AT)frank-buss.de), Aug 08 2003
|
|
|
Search completed in 0.002 seconds
|
