Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Kolakoski sequence generator

by ariels (Curate)
on Jun 20, 2002 at 14:08 UTC ( #176016=perlcraft: print w/ replies, xml ) Need Help??

   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.

Comment on Kolakoski sequence generator
Download Code
(MeowChow) Re: Kolakoski sequence generator
by MeowChow (Vicar) on Jun 20, 2002 at 17:11 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlcraft [id://176016]
Approved by SparkeyG
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (10)
As of 2014-07-31 08:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (245 votes), past polls