Is it possible to compute how many iterations this algorithm will take?

Question

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always guaranteed to terminate.)

Let $x$, $y$, and $z$ be some positive integers. The values of $x$, $y$, and $z$ are chosen such that neither $y$ nor $z$ will become $\le 0$ before the loop terminates.

$\text{do}$

$\qquad \text{if } (x+y) \text{ mod } z = 0 \text{ then done}$

$\qquad x \leftarrow x + y$

$\qquad y \leftarrow y - 4$

$\qquad z \leftarrow z - 2$

$\text{loop}$

For example, if we let $x =184$, $y = 376$, and $z = 187$, this algorithm terminates in $19$ loops.

Here is a plot of $(x+y) \text{ mod } z$ for some real inputs. Here is another plot for larger inputs.

Answer 1

There might be no clean formula for that.

The values of $x,y,z$ after the $n$th iteration of the loop are $x_0 + (n+1) y_0 - 2n(n+1)$, $y_0 - 4n$, and $z_0 - 2n$, respectively, as can be verified by induction, where $x_0,y_0,z_0$ are their initial values (before the first iteration of the loop). The loop terminates for the smallest positive integer $n$ such that

$$x_0 + (n+1) y_0 - 2n(n+1) + y_0 - 4n \equiv 0 \pmod{z_0 - 2n}.$$

There might not be any nice expression for the smallest $n$ that satisfies that equation, in terms of $x_0,y_0,z_0$. It's also not obvious to me whether such an $n$ always exists, i.e., whether your loop will always terminate.

---

I'm glossing over a serious issue that you haven't addressed in the question: what is the meaning of $(x+y) \bmod z$ when $z=0$ or when $z<0$? It's not clear, and that will affect the answer.