# n -> 0 and 1 in decimal expansion of n sub profile { my $n = shift; $n =~ s/[2-9]+//g; return $n; } # length x prefix -> len-length profiles starting with prefix sub profiles { my $len = shift; my $prefix = shift; if ($len == length($prefix)) { return ($prefix); } else { return (profiles($len, $prefix . "0"), profiles($len, $prefix . "1")); } } my $unclassed = 1; my %next_with_profile = (); # profile -> next unused number with given profile sub next_with_profile { my $profile = shift; while ($#{$next_with_profile{$profile}}<0) { push @{$next_with_profile{ profile($unclassed) }} => $unclassed; $unclassed++; } return $next_with_profile{$profile}[0]; } # n -> consume n sub consume { my $n = shift; my $profile = profile($n); die if $next_with_profile{$profile}[0] ne $n; shift @{$next_with_profile{$profile}}; } my $carry = ""; sub compute_next_term { my $best = next_with_profile(""); foreach my $len (1..length($best)) { foreach my $profile (profiles($len, substr($carry, 0, $len))) { my $other = next_with_profile($profile); if ($best > $other) { $best = $other; } } } consume($best); $carry = substr($carry . sprintf("%b", $best), length(profile($best))); return $best; } my $prev = 0; my $i = 0; foreach my $n (1..32062) { my $a = compute_next_term($n); if ( ($prev <= $n-1) != ($a <= $n) ) { print ++$i, " ", $n-1, "\n"; last if $i==10_000; } $prev = $a; }