Let's rephrase the problem a litte bit, note that after the $$$i$$$-th iteration of the algorithm we get some $$$9$$$-digit number, $$$a_{i}$$$, that isn't divisible by $$$10$$$. If we prove that every step yields a number whose last digit is the last non-zero digit of $$$P_{i}^{N}$$$, then the algorithm works for all $$$1 \leq i \leq N$$$. This screams induction, but focusing only on the last non-zero digit will take us nowhere because we will be missing a lot of information whenever the current last digit becomes zero and this would make retrieving previous digits impossible. So, instead of proving that the last non-zero digit is correct after each step of the algorithm, we will prove that also the $$$8$$$ digits to the left of the last non-zero digit are correct in the sense that $$$a_{i}$$$ is a substring of $$$P_{i}^{N}$$$.

Let's define $$$f(n)$$$ as the $$$k$$$-digit number (we are interested in $$$k = 9$$$, but let's do it more generally) obtained after removing all trailing zeros from $$$n$$$ and then taking the $$$k$$$ less significant digits, we may have leading zeroes.

We proceed by induction on $$$i$$$, the base case $$$i = 1$$$ is clear since $$$N \lt 10^{9}$$$. Now we only need to prove \begin{align}f(P_{i + 1}^{N}) = f(a_{i}\cdot(N − i))\end{align} But notice that $$$P_{i + 1}^{N}$$$ is equal to $$$P_{i}^{N} \cdot (N - i)$$$ by definition and $$$f(P_{i}^{N}) = a_{i}$$$ by the induction hypothesis. Using the following claim we conclude the proof.

$$$\text{Claim:}$$$ Let $$$n$$$ and $$$m$$$ be positive integers. If the number of digits of $$$m$$$ is less than $$$k$$$, then $$$f(nm) = f(f(n)\cdot m)$$$, i.e. the less $$$k$$$ significant digits, excluding trailing zeros, of $$$nm$$$ and $$$f(n)\cdot m$$$ are the same.

Suppose the last non-zero digit of $$$n$$$ is at position $$$j$$$ from right to left, then we are only interested in the digits at positions $$$j, j + 1, \dots , j + k - 1$$$. How exactly does $$$nm$$$ look like? Well, if $$$n = \sum\limits_{s = 0}^{k}10^{s}b_{s}$$$ and $$$m = \sum\limits_{s = 0}^{r}10^{s}c_{s}$$$, for some $$$r \lt k$$$, then the $$$t$$$ digit of $$$nm$$$ is obtained after taking modulo $$$10$$$ the sum of $$$\sum\limits_{s = 0}^{\min(t, r)}b_{t - s}c_{s}$$$ and the carrying which comes from the right. Suppose $$$nm$$$ has $$$q \geq 0$$$ more trailing zeros than $$$n$$$, then $$$f(nm)$$$ is formed by the digits of $$$nm$$$ at positions $$$j + q, j + q + 1, \dots , j + q + k - 1$$$, using the previous formula we notice two things:

• Trailing zeros of $$$n$$$ doesn't affect the value of any digit of $$$nm$$$.

• (This is false) Digits of $$$n$$$ at positions $$$t \gt (j + k - 1)$$$ are not needed to compute the digits of $$$f(nm)$$$, that's because all the digits of interest are at positions of the form $$$(j + q + p)$$$ with $$$ 0 \leq p \leq k - 1$$$; plugging that into the formula yields \begin{align}\sum\limits_{s = 0}^{\min(j + q + p,\, r)}b_{j + q + p − s}c_{s}\end{align} so we only need to prove that \begin{align} j + q + p − s &\leq j + k − 1 \newline \iff q + p &\leq s + (k − 1) \end{align} which follows from the fact that $$$s = \min(j + q + p,\, r)$$$, note that if $$$\min(j + q + p,\, r) = j + q + p$$$ just substitute and the result is true, else $$$s = r$$$ and see that there is not way $$$nm$$$ has more than $$$r$$$ trailing zeros than $$$n$$$ (This last part is totally wrong).

The above suggests that $$$f(f(n)\cdot m)$$$ should be equal to $$$f(nm)$$$ since we don't involve digits of $$$n$$$ not included in $$$f(n)$$$ to compute the $$$k$$$ less significant digits of $$$nm$$$, excluding trailing zeros.