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

{
	a = vector(10 000);
	u = 1;

	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));
				n++;
				if (w<=#a,
					a[w]=n;
				);
			);

			n++;
			if (v<=#a,
				a[v]=n;
			);
			p = v;

			while (a[u],
				print (u " " a[u]);
				if (u++>#a,
					break (2);
				);
			);
		);
	);
}

quit