Is there a mathematical notation for "repeat $X$ until $Y$"?

The repeat X until Y methodology is a key component of many algorithms. Yet, I haven't come across a good mathematical notation for it. (Perhaps because it is of little use in manipulating expressions?)

As an example how would you write "Sum the reciprocals of natural numbers until the total is above 42." I would like to write something like:

$$\sum_{N=1}^{this\lt 42} \frac{1}{N}$$

where "this" corresponds to the partial sums.

Likewise one would like to do a similar thing with products or iterations in general e.g. "Start with 2, keep squaring until the result is no bigger than 15":

$$ (x \rightarrow x^2)^{this\lt 15}(2)$$

I mean I suppose one could fake it by using the Heaviside function $H(x)$ which is $0$ if $x\lt 0$ and $1$ if $x\geq 0$

$$ (x \rightarrow x + H(42-x)(x^2-x) )^\infty(2)$$

Which gives the same result but is not a direct translation of the English into mathematical notation. Since this is essentially saying "keep doing the iteration forever even though you're getting the same result."

Solution 1:

The first one:

"Sum of reciprocals of natural numbers (starting with 1) until sum is above 42"

is fairly straightforward. First, the number where it goes above 42 is:

$$X = \min \left\{ x \in \mathbb{N} \,\left\vert\, \sum_{n=1}^x \frac{1}{n} >42 \right.\right\}$$

And so if you want to know what the sum is:

$$\sum_{n=1}^X \frac{1}{n}$$

Or, as one expression:

$$\sum_{n=1}^{\min \left\{x \in \mathbb{N} \,\left\vert\, \sum_{n=1}^x \frac{1}{n} >42 \right.\right\} } \frac{1}{n}$$

For the "Start with $2$ and keep squaring while result is less than 15"

you indeed need to talk about iterations of numbers. For this, we could define a recursive function. So, let $f$ be a funtion from natural numbers to natural numbers defined by:

$f(1)=2$

$f(x+1)=f(x)^2$ (for $x>1$)

And now the result we are looking for is:

$$\max \{ f(x) \mid x \in \mathbb{N}, f(x)<15 \}$$

Solution 2:

I think a lot of times in mathematics, we are less interested in the procedure and more interested in the result. So, why do you need to do $X$ until $Y$? Presumably it is to compute some value. Often in a mathematical context, it is sufficient to just assert (or prove) the existence of such a value without regard to how it's computed.

Consider your example: "Sum the reciprocals of natural numbers until the total is above 42." As someone not interested in futility, I would ask why I should do this. Perhaps you are interested in the first such total that is above 42? If it is obvious that such a quantity exists, in mathematical literature we might instead say "Let $x_n$ denote the sum of the reciprocals of the first $n$ natural numbers, and let $x$ denote the least element of the set $\{x_n \; |\; x_n > 42\}$". Very often I am not interested in how one might go about computing $x$.

Solution 3:

I think there are a few ways to do it, but probably the most natural is to use set-builder notation.

You can take the sequence $x_{n+1}=x_n^2$ which is a recursively defined sequence, and you could take $$\{x_n \mid x_n<15\}$$ to capture the repitition. and if you just want the last one, $$\mathrm{max}\{x_n \mid x_n<15\}.$$

This kind of recursion approach along with set-builder notation, or "cases," is adopted in Haskell.

However, mathematics is usually communicated with common language. Just saying, "repeatedly square $x$ while $x<15$" would probably do the trick for the recursion, or maybe "let $a_n$ be the largest member of the sequence $a_{n+1}=a_n^2$ so that $a_n<15$." I think the computer science notation is out of necessity for a computer to understand you, which is not a requirement for communicating math.

Solution 4:

"Sum the reciprocals of natural numbers until the total is above 42" might be $$\sum_{j=1}^{\arg\min\limits_n \left(\sum_{i=1}^n \frac1{i} \,> \,42\right)} \frac1j$$ or in this special case where the sum is increasing and is both the test value and the result $$\min\limits_n \left\{S_n: S_n=\sum_{i=1}^n \frac1{i}, S_n>42 \right\}$$

Solution 5:

As the basis of this question seems to be algorithms, you could also just write pseudocode (Even if it is for a smaller part of the algorithm). There is a common mathematical style pseudocode, which should provide the idea of what you're trying to convey in an elegant manner.

There is a nice example of this style on Wikipedia for Ford–Fulkerson algorithm, which incorporates the repeat X until Y methodology in your question.