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

Question

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."

Answer 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 \}$$

Answer 2

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.

Answer 3

"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\}$$

Answer 4

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$.

Answer 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.

Answer 6

Sum the reciprocals of natural numbers until the total is above 42.

$$\min\left\{x ~:~ \exists y ~.~ x=\sum_{k=1}^y \frac 1k > 42\right\}$$

Start with 2, keep squaring until the result is no bigger than 15"

$$\max\left\{x ~:~ \exists y~.~ x=(((2\text{^}\overbrace{2)\text{^}2) \cdots)\text{^}2}^y \le 15\right\}$$

Still prose is probably preferred.

Answer 7

I think you are effectively asking if there's a way to represent a while loop using standard mathematical notation. I can think of two ways to do this.

The first uses a nice law from computer science, which states that any while loop can be reformulated as a tail recursion problem:

First, let us see the anatomy of a standard while loop as pseudocode.

state = initialstate; 
while(not EndCondition) { newstate = f(state); state = newstate; };
return FinalStep(state);

This is semantically equivalent to the following pseudocode

F(state) = if !Endcondition then { return F(newstate) } else { return FinalStep(state) }

You can see from the above then, that the mathematical notation for this is fairly straightforward. Assuming an initial condition $ x_0 $, a "final step" function $ h $, an "inner step" function $ g $, and an "endcondition" expression / predicate $ E $, then the loop can be expressed in recursive form as follows:

$$ F(x_0), ~~\text{where:}~~ F(x) = \left \{ \begin{array}{ll} h(x) & , E(x) \\ F(g(x)) & , otherwise \end{array} \right .$$

The second method is similar to the above idea of others of using a generator expression, but also making use of function composition, and in particular the notation $ g^2(x) $ to mean $ g(g(x)) $.

Therefore, a different notation could make use of predicate $Q$ which is only satisfied at the endcondition, and then perform function composition exactly $ n $ times, such that $n$ satisfies $Q$, i.e.

$$ \min \{ n \in \mathbb{N} : g^{n-1}(x_0), ~~Q(n)\} ,~~~ \text{where:} Q(m) = \left \{ \begin{array}{ll} \top & , E(g^{m-1}(x_0)) \\ \bot & , otherwise \end{array} \right . $$

or if you're willing to have recursion in your predicate, you can get rid of the 'min' expression and have more simply:

$$ g^{n-1} (x_0) : Q(n), ~~ \text{where:} Q(m) = \left \{ \begin{array}{ll} \top & , E(g^{m-1}(x_0)) \\ \bot &, Q(m-1) \\ \bot & , otherwise \end{array} \right . $$

---

Demo using the sum example:

"sum until the total is > 42"

Using tail recursion:

$$ F(1,1), \text{where:}~~ F(n,\Sigma) = \left \{ \begin{array}{ll} \Sigma & , \Sigma > 42 \\ F(n+1, \Sigma + n+1) & , otherwise \end{array} \right . $$

Using function composition:

$$ g^{n-1}(1) : Q(n), ~~\text{where:} ~~Q(m) = \left \{ \begin{array}{ll} \top & , g^{m-1}(1) > 42 \\ \bot & , Q(m-1) \\ \bot & , otherwise \end{array} \right . ~~~, \text{and} ~~g(x) = g(x-1) + x $$

Answer 8

I do not know whether other people also use but for any commutative binary operation, I use this notation:

Let $\times$ be our commutative binary operation we want to find a notation for the expression $$a_1\times a_2 \times a_3 \times... \times a_n,$$ then I show it as

$$ = [\sum_{i=1}^n]_x a_i$$