$| = 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"; }