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.

• gnasher729: 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.

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.

• EntangledLoops: $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.
• D.W.: @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.
• EntangledLoops: 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: 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.
• D.W.: @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?).