Audioactive Sequence

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
etc.

The way this sequence works is described in 1, 11, 21, 1211.

Things that are interesting to prove about this sequence, in order of difficulty:

• There will never be a 4, or anything higher, in this sequence.
• If the sequence started with 2 instead of 1, every number after the 2nd would end with '112'.
• The sequence will never get shorter.
• If you consider a new sequence, comprised of digits m through n of each step, this sequence will eventually cycle. (For example, this sequence where m=1 and n=2 is 11, 21, 12, 11, 31, 13, 11, 31, 13 ...)

A simple iterative sequence, beginning with 1:

1
11
21
1211
111221
...

It's easy to generate. Simply write down what numbers you saw in the previous line: the first line has one 1, so the second line is 11. That's two 1's, so we write 21. Then one 2 and one 1, so we write 1211. Repeat to fade.

As you might expect, the number of digits in the sequence increases at a very fast rate. Jongleur points out that the sequence is in fact doubly exponential; the number of digits in the nth term is approximately

(1.3035772690342963912570991121525518907307025046594...)ⁿ,

so the actual value of the number is double exponential.

This enormous irrational but nonetheless algebraic number in parantheses is the solution to a horendous polynomial of degree 71! The polynomial, should you wish to solve it yourself, is:

x⁷¹ - x⁶⁹ - 2x⁶⁸ - x⁶⁷ + 2x⁶⁶ + 2x⁶⁵ + x⁶⁴ - x⁶³ - x⁶² - x⁶¹ - x⁶⁰ - x⁵⁹
+ 2x⁵⁸ + 5x⁵⁷ + 3x⁵⁶ - 2x⁵⁵ - 10x⁵⁴ - 3x⁵³ - 2x⁵² + 6x⁵¹
+ 6x⁵⁰ + x⁴⁹ + 9x⁴⁸ - 3x⁴⁷ - 7x⁴⁶ - 8x⁴⁵ - 8x⁴⁴ + 10x⁴³
+ 6x⁴² + 8x⁴¹ - 5x⁴⁰ - 12x³⁹ + 7x³⁸ - 7x³⁷ + 7x³⁶ + x³⁵
- 3x³⁴ + 10x³³ + x³² - 6x³¹ - 2x³⁰ - 10x²⁹ - 3x²⁸ + 2x²⁷
+ 9x²⁶ - 3x²⁵ + 14x²⁴ - 8x²³ - 7x²¹ + 9x²⁰ + 3x¹⁹ - 4x¹⁸
- 10x¹⁷ - 7x¹⁶ + 12x¹⁵ + 7x¹⁴ + 2x¹³ - 12x¹² - 4x¹¹ - 2x¹⁰
+ 5x⁹ + x⁷ - 7x⁶ + 7x⁵ - 4x⁴ + 12x³ - 6x² + 3x - 6 = 0

The series is base dependent, since it's based on the digits as they appear, but I've only dealt with it in base 10. It's fairly simple to write a script to generate as many terms of this as you fancy, but the first few (and yes, I did this by hand as usual, so corrections are welcome) are:

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213222133112132113311211131222121321131211132221123113112221131112311332111213211322211 31113211

You can actually see the simple exponential pattern appearing in those columns of digits. Interesting.

The only digits present are always 1, 2 and 3. That's because in order to get a 4, you'd need to have 4 consecutive identical digits in the row above. That can't happen because, for example, 2222 never appears since it's just written as 42.

How does this sequence look in other bases? Anyone who fancies writing the script can let me know.

If you would like to generate this sequence yourself, you can either Learn to program, or you can use the following bit of Python code. I wrote this to investigate a new feature of Python called generators, (a.k.a. co-routines), so it will look a little weird.

The code generates as many terms as you might want of the sequence detailed above - have fun playing with it! All computer science dorks (like myself) should note that the running time of this program is O(2ⁿ), but that's unavoidable because the sequence is doubly exponential, so the number of digits in the answer we have to write down grows exponentially every time. It does allow you to generate the sequence in any base you want, though - which is kind of cool.

#!/usr/bin/env python2.2

# Compute the audioactive sequence using coroutines.  We can calculate it in
# any base, but since no number higher than 3 ever appears, it is all the same
# for bases 4 and higher

from __future__ import generators

def convertToBase(num, base):
    rv = ""
    while num > 0:
        rv = ("%d" % (num % base)) + rv
        num = num / base
    return rv

def audioactive(base):
    s = '1'
    while 1:
        yield s
        snew = ""
        count = 0
        curr = ''
        for i in s:
            if i != curr:
                if curr:
                    snew = snew + "%s%s" % (convertToBase(count,base),curr)
                count = 1
                curr = i
            else:
                count = count+1
        s = snew + "%s%s" % (convertToBase(count,base),curr)
            

if __name__ == '__main__':
    from sys import argv, exit
    if len(argv) < 3:
        print "Usage:", argv[0], " number base"
        exit(1)
    
    sequence = audioactive(int(argv[2]))
    for i in xrange(int(argv[1])):
        print sequence.next()

The first 10 terms of the sequence in base 2 look like:

1
11
101
111011
11110101
100110111011
111001011011110101
111100111010110100110111011
100110011110111010110111001011011110101
1110010110010011011110111010110111100111010110100110111011

This handy, little Perl script will display the audioactive sequence in the user-specified non-zero base. It should be noted that this sequence grows exponentially for all bases greater than 1. In base 1, however, the sequence grows linearly. Try AUDIOACTIVE.PL 1 10 and see for yourself (or just look at the short example runs below).

#!/usr/bin/perl
use strict;

# AUDIOACTIVE.PL
# This script takes 2 command line arguments: base and iterations
# If the base is not 1, 2, or 3 it is assumed to be 4
# because after 3, the sequence is the same regardless of base.

# Example: perl AUDIOACTIVE.PL 2 10

if($#ARGV != 1) {
  print STDERR "Usage: perl AUDIOACTIVE.PL <base> <iterations>\n";
  exit;
}

my ($str, $base, $max) = ('1', shift, shift);
my %hDecToBin  = qw(1 1 2 10 3 11 4 100);
my %hDecToTri  = qw(1 1 2  2 3 10 4  11);
my %hDecToQua  = qw(1 1 2  2 3  3 4  10);
my $hDecToBase = undef;

if($base < 1) {
  print STDERR "Base must be greater than 0, exiting program...\n";
  exit;
} elsif($base == 1) {
  print '1' x $_, "1\n" for (0..$max-1);
  exit;
} elsif($base == 2) {
  $hDecToBase = \%hDecToBin;
} elsif($base == 3) {
  $hDecToBase = \%hDecToTri;
} else {
  $hDecToBase = \%hDecToQua;
}

print "$str\n";
for(my $i=0; $i < $max-1; $i++) {
  my @str = split('', $str);
  $str = '';
  my ($num, $count) = ($str[0], 0);
  foreach (@str) {
    if($_ == $num) {
      $count++;
    } else {
      $str  .= $hDecToBase->{$count};
      $str  .= $num;
      $num   = $_;
      $count = 1;
    }
  }
  $str .= $hDecToBase->{$count};
  $str .= $num;
  print "$str\n";
}

Examples:
perl AUDIOACTIVE.PL 1 6
1
11
111
1111
11111
111111

perl AUDIOACTIVE.PL 2 6
1
11
101
111011
11110101
100110111011

perl AUDIOACTIVE.PL 3 6
1
11
21
1211
111221
1012211

perl AUDIOACTIVE.PL 4 6
1
11
21
1211
111221
312211

perl AUDIOACTIVE.PL 5 6
1
11
21
1211
111221
312211