# 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;
}