$| = 1;

sub overlaps {
	my $a = shift;
	my $b = shift;

	if (index($a, $b)>=0 || index($b, $a)>=0) {
		return 1;
	}

	my $la = length($a);
	my $lb = length($b);

	my $l = ($la < $lb) ? $la : $lb;

	foreach (1..$l) {
		if (substr($a, 0, $_) eq substr($b, $lb-$_)) {
			return 1;
		}
		if (substr($b, 0, $_) eq substr($a, $la-$_)) {
			return 1;
		}
	}

	return 0;
}

my %seen = (0 => 1);
my $min = 1;

sub other {
	my $prev = shift;

	$seen{$prev} = 1;
	while (exists $seen{$min}) {
		$min++;
	}

	my $candidate = $min;
	while ((exists $seen{$candidate}) or (not overlaps($prev, $candidate))) {
		$candidate++;
	}

	return $candidate;
}

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