Here's how I did it. Have no idea how this does on time.

#!perl
$total=10; ## Set to 1000 and watch your memory drain away! :)

@a=qw(1);
for (1..$total) {
  print "@a\n";
  my @all;
  $count=1; $x=0;
  {
    if ($a[$x] != $a[$x+1]) {
      push(@all, $count); push(@all, $a[$x]);
      $count=0;
    }
    last unless ++$count and $a[$x++];
    redo;
  }
  *a=\@all;
}
[download]