big = 1 000 000
s = 0
S = Set([])
unseen = 1
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++)

find(p,v) = {
	my (pp=factor(p)[,1]~, vv=factor(v)[,1]~, m=1);
	if (#pp==1, m*=pp[1]);
	if (#vv==1, m*=vv[1]);

	forstep (w=ceil(unseen/m)*m, oo, m,
		if (!seen(w) && gcd(p,w)>1 && gcd(v,w)>1,
			return (w);
		);
	);
}

{
	n=0;
	for (v=1, oo,
		if (!seen(v),
			see(v);

			if (v > 2 && gcd(p,v)==1,
				\\ we must sandwich a term
				see(w=find(p,v));
				print (n++ " " w);
			);

			print (n++ " " v);
			p = v;

			if (n>=10 000,
				break;
			);
		);
	);
}

quit