1: #!/usr/local/bin/perl -w 2: 3: # The "Kolakoski sequence" 4: # (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000002) 5: # is the sequence beginning 2,2,1,1,2,1,2,2,1,2,2,1,1,2,... 6: # of alternating blocks of 1's and 2's, where the length 7: # of the k'th block is the value of the k'th element. So 8: # the sequence has TWO 2's, then TWO 1's, then ONE 2, then 9: # ONE 1, then TWO 2's, then ONE 1, ... 10: # 11: # It's not a periodic sequence, but it is conjectured 12: # (i.e. it is thought to be true, but nobody has any idea 13: # how to prove it) that approximately half the elements 14: # are 1's. 15: 16: # Generate the Kolakoski sequence 17: 18: use strict; 19: 20: package Kolakoski; 21: 22: # Object format: [ WHAT, HOW_MANY, KOLAKOSKI ] 23: # 24: # WHAT: What we're generating now (1's or 2's) 25: # HOW_MANY: How many to generate (2 -> 1 -> 0) 26: # KOLAKOSKI: Sequence generator, to use when HOW_MANY == 0 27: sub new { 28: my $class = shift; 29: $class = ref($class) || $class; 30: bless [2, 2, undef], $class 31: } 32: 33: sub next { 34: my $self = shift; 35: if ($self->[1] == 0) { 36: if (! defined $self->[2]) { 37: # Generate a new object 38: $self->[2] = $self->new; 39: $self->[2]->next; # advance past first one (already generated) 40: } 41: # Use sequence object to generate next count 42: $self->[0] = 3 - $self->[0]; # flip 1 <-> 2 43: $self->[1] = $self->[2]->next; 44: } 45: -- $self->[1]; 46: return $self->[0]; 47: } 48: 49: 50: package main; 51: 52: my $n = shift || 100_000; 53: my $n2; 54: 55: my $k = new Kolakoski; 56: 57: for (1..$n) { 58: my $v = $k->next; 59: print $v; 60: $n2++ if $v==2; 61: } 62: print "\n"; 63: print "$n2 / $n 2's (@{[$n2/$n*100]}%)\n"; 64: 65: # Notes 66: # 67: # 1. Some people prefer to start the sequence with a "1". 68: # If you're one of them, just print a "1" before starting 69: # the loop. 70: # 2. The number of objects required to print the first N 71: # elements is O(log N), IF the conjecture about the 72: # distribution of 2's in the sequence is true. 73: # 3. Simulations (not much more sophisticated than this 74: # one, although probably better written in C) suggest that 75: # the conjecture is true. The number of 2's in the first 76: # N elements of the sequence appears to be N/2+O(log(N)), 77: # but of course this too is unproven.
|
---|
Replies are listed 'Best First'. | |
---|---|
(MeowChow) Re: Kolakoski sequence generator
by MeowChow (Vicar) on Jun 20, 2002 at 17:11 UTC |
Back to
Craft