big = 1 000 000
s = 0
S = Set([])
unseen = 2
seen(v) = if (v < big, bit test(s, v), set search(S, v))
see(v) = if (v < big, s = bit or(s, 2^v), S = set union(S, Set([v]))); while (seen(unseen), unseen = nextprime(unseen+1))

base = 10

other(p) = {
	see(p);

	\\ next prime appears in p?
	my (d = digits(p, base));
	my (sub = setbinop((i,j) -> fromdigits(d[i..j], base), [1..#d]));
	for (k=1, #sub,
		if (!seen(sub[k]) && isprime(sub[k]),
			return (sub[k]);
		);
	);

	\\ find a prime number containing p
	c = [p];		\\ candidates
	w = base^#d;

	while (1,
		\\ add a digit in front or at the end of the candidates

		c = Set(concat(apply(v -> vector(2*base, k,
			if (k<=base,
				(k-1)*w + v,		\\ in front of
				base*v + (k-1-base)	\\ at the end of
			);
		), c)));

		for (k=1, #c,
			if (!seen(c[k]) && isprime(c[k]),
				return (c[k]);
			);
		);

		w *= base;
	);
}

{
	my (p = prime(1));
	for (n=1, 10 000,
		print (n " " p);
		p = other(p);
	);
}

quit