Athanasius, thanks for your interesting write-up. Here is a little version using vec for storing which numbers have been seen already. It runs quite happily until it hits integer overflow... It only prints a line when the maximum observed or the minimum unobserved increases.

use strict;
use warnings;

my $min = 2; # smallest unused number
my $max = 3; # largest number already visited
my $n   = 2;
my $r   = 3;
my $s;
vec($s,$_,1)=1 for (0,1,3);
my $flag = 1;
while(++$n){
    $r += ($r-$n>0) && not( vec($s,$r-$n,1) ) ? -$n : $n;
    vec($s,$r,1)=1;
    $min++, $flag=1 while vec($s,$min,1);
    $max = $r, $flag=1 if $r > $max;
    print "$n\t$max\t$min\t$r\t".length($s)."\n" if $flag;
    $flag = 0;
}
[download]