$| = 1;

my %known = ();		# current known digits
my %future = ();	# possible future digits
my $nextAn = 1;		# position of next a(n)

sub match {
	my $pos = shift;
	my $n   = shift;

	foreach my $i (0..length($n)-1) {
		my $d = substr($n, $i, 1);

		if (exists $known{$pos+$i} and $known{$pos+$i}!=$d) {
			return 0;
		}
		if (exists $future{$pos+$i} and $future{$pos+$i}!=$d) {
			return 0;
		}

		$future{$pos+$i} = $d;
	}

	return 1;
}

sub candidates {
	my $len = shift;

	my @newdigits;
	if (exists $known{$nextAn+$len-1}) {
		@newdigits = ( $known{$nextAn+$len-1} );
	} else {
		if ($len==1) {
			# leading digit -> not 0 !
			@newdigits = (1..9);
		} else {
			@newdigits = (0..9);
		}
	}

	my @newcandidates = ();

	foreach my $oldcandidate (@_) {
		push @newcandidates => map { $oldcandidate*10 + $_ } @newdigits;
	}

	return @newcandidates;
}

sub a {
	my $n = shift;

	my $len = 1;
	my @candidates = (0);
	while (1) {
		@candidates = candidates($len, @candidates);
		foreach my $can (@candidates) {
			%future = ();

			if (match($can, $n) && match($nextAn, $can)) {
				if (exists $known{$nextAn+$len} and $known{$nextAn+$len}==0) {
					# leading zero !
				} elsif (exists $future{$nextAn+$len} and $future{$nextAn+$len}==0) {
					# leading zero !
				} else {
					foreach (keys %future) {
						$known{$_} = $future{$_};
					}
					$nextAn += $len;
					return $can;
				}
			}

		}

		$len++;
	}
}

foreach my $n (1..10_000) {
	my $a = a($n);
	print "$n $a\n";
}