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

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.

• Of course you could say "whatever (x + y) modulo 0 is, it is not zero". In that case the loop runs forever if x is odd, y and z are even. – gnasher729 May 5 at 23:27

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.

• $z$ will never be $\le 0$. The numbers are guaranteed to work by the way I've generated them, but I don't have time to explain the full problem. I'm just interested to know if there is a way to solve this kind of formula in general, or simply trying repeatedly is the only way. – EntangledLoops May 5 at 23:32
• @EntangledLoops, From the text of the algorithm as you've described it, $z \le 0$ certainly can happen. For instance, suppose $x_0=1,y_0=100,z_0=2$. If there's something that prevents $z \le 0$, it's missing from the question -- and omitting relevant context makes it harder to provide a useful answer. We can only answer the question that was asked. – D.W. May 6 at 0:06
• Yes you are correct, but what I'm saying is that $x$, $y$, and $z$ have been chosen by another algorithm that guarantees this won't happen. That's an invariant here. I'm hoping that knowing that up front will help, somehow. – EntangledLoops May 6 at 0:08
• I added a plot to the original question to show the behavior under real inputs. The plots vary depending upon the input, but have some aesthetic similarity that I can't quantify. – EntangledLoops May 6 at 0:19
• @EntangledLoops, that's fine, but please edit the question to state all relevant guarantees (such as that the initial values of $x,y,z$ are chosen so that the loop terminates before $z \le 0$; are there other guarantees?). – D.W. May 6 at 0:41