a(n) = {
	my (x);
	for (k=1, oo,
		x = if (k==1, n, x - sumdigits(x, k));
		if (x==0,
			return (k);
		);
	);
}

\\ cache
val = vector(10 000)

conquer(t,v) = {
	if (!val[t], val[t] = a(t));
	if (!val[v], val[v] = a(v));

	if (val[t] == val[v],
			\\ sequence is weakly increasing,
			\\ so all values are the same over t..v
			for (k=t+1, v-1,
				val[k] = val[t];
			),

		t+1!=v,
			\\ divide and conquer!
			my (u=(t+v)\2);
			conquer(t, u);
			conquer(u, v);
	);
}

{
	conquer(1, #val);

	print (0 " " a(0));
	for (n=1, #val,
		print (n " " val[n]);
	);
}

quit