This is the problem that inspired me to think seriously about the advantage of an “algorithmic” construction over an explicit / naive inductive one.

Problem. Suppose that $\{a_i\}$ is a sequence of positive integers satisfying $a_{(m,n)}=(a_m,a_n)$. Prove that there exists a sequence of positive integers $\{b_n\}$ such that $$\prod_{d|n} b_d = a_n$$

Solution. We will construct the sequence $b_n$ iteratively by making small decremental changes to $a_i$. That is, for each $t\in\mathbb{N}$ (thought of as a time variable), we will construct sequences $\{a_n(t)\},\{b_n(t)\}$ as follows:

$$\{a_i(1)\} = \{a_i\}, \quad \{b_i(1)\} = \{1,1,...\}$$

At each step, we will attempt to preserve the following facts:

• $a_{(m,n)}(t)=(a_m(t),a_n(t))$
• $a_n(t) \prod_{d|n} b_d(t) = a_n$

which are both initially true. Eventually, we hope that the sequence $\{a_i\}$ “converges” to $\{1,1,...\}$ and $\{b_i\}$ “converges” to anything at all. By converge, we mean that for each $i$, $a_i(t)$ (and similarly for $b_i(t)$) stays the same for sufficiently large $t$. Subsequently, taking sufficiently large $t$ we get our construction for $\{b_i\}$.

The time evolution rule is as follows: at a given time $t$, let $i$ be the smallest index for which $k=a_i(t)> 1$. Then, we let: $$a_j(t+1) = \begin{cases}a_j(t) \text{ if }i\nmid j\\ a_j(t) / k \text{ if } i\mid j\end{cases}$$ $$b_j(t+1) = \begin{cases} k b_j(t) \text{ if } i = j \\ b_j(t) \text{ otherwise}\end{cases}$$

Now we verify that both rules are preserved. Given $m,n$, the first rule is affected as follows:

• $i\nmid m,n$. Then there is no change.
• $i\mid m,n$. Then each of $a_m(t),a_n(t),a_{(m,n)}(t)$ will shrink by a factor of $k$.
• $i\mid m, i\nmid n$. Then by assumption, $(k,a_n(t)) = a_{(n,i)}(t) = 1$. So $a_m(t)$ shrinks by a factor of $k$ while there is no change for $a_n(t),a_{(m,n)}(t)$

Also, for each $n$, the second rule is affected as follows:

• $i\nmid n$: there is no change to the product condition.
• $i\mid n$: $a_n(t)$ shrinks by a factor of $k$ while $b_i(t)$ grows by a factor of $k$.

Finally, it is obvious that $a_n(t) = 1$ while $b_n(t)$ stays constant for all $t\ge n$ (because then at least the first $n$ terms of $\{a_i(t)\}$ are 1, so $i\ge n+1$ and will not affect both $a_n(t),b_n(t)$). So define $b_n = b_n(n)$ and the conclusion follows.