12
$\begingroup$

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

$\endgroup$
  • 30
    $\begingroup$ Sometimes notation is a very good way for humans to communicate mathematics to each other. Other times, words are better. $\endgroup$ – Lee Mosher Aug 8 '18 at 17:11
  • 2
    $\begingroup$ "Start with 2, keep squaring until the result is no bigger than 15" - Do you mean "keep squaring until the result is bigger than 15"? Because the number 2 is already no bigger than 15. $\endgroup$ – Tanner Swett Aug 8 '18 at 17:14
  • 12
    $\begingroup$ If you're repeating a process until something happens, depending on what it is you're looking at (for example, a list of numbers, as in all of your examples), then you can easily describe the minimum or maximum of the set that satisfies the given properties. In the first case, you can use: $$\min\left\{n\in\Bbb N:\ \sum_{k=1}^n\frac1k\geq42\right\}$$ and get across that you're interested in the minimum value $n$ that makes the sum at least as large as $42$. $\endgroup$ – Clayton Aug 8 '18 at 17:18
  • 6
    $\begingroup$ The answers in this thread are in great support of @LeeMosher's comment. $\endgroup$ – Randall Aug 8 '18 at 18:32
  • 2
    $\begingroup$ @Randall: savage hahahah. I don't disagree. $\endgroup$ – Andres Mejia Aug 8 '18 at 22:53
19
$\begingroup$

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 \{ x \in \mathbb{N} \mid \sum_{n=1}^x \frac{1}{n} >42 \}$$

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 \{x \in \mathbb{N} \mid \sum_{n=1}^x \frac{1}{n} >42 \} } \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 \}$$

$\endgroup$
  • $\begingroup$ Your last point is basically just avoiding the identification $f:\mathbb N \to \mathbb R$ with a sequence $x_n$, no? I can't really see the benefit of that, can you elaborate on your choice? $\endgroup$ – Andres Mejia Aug 8 '18 at 17:40
  • 1
    $\begingroup$ Very good. It's a pity the "as one expression" part involves having to duplicate part of the expression but I suppose you could write $f(min\{x\in\mathbb{N}|f(x)>42\})$ where $f(x) = \sum_{n=1}^x\frac{1}{n}$ $\endgroup$ – zooby Aug 8 '18 at 17:42
  • $\begingroup$ @zooby oh yeay, nice! :) $\endgroup$ – Bram28 Aug 8 '18 at 18:20
  • 1
    $\begingroup$ Or to make it more readable I would choose a better name than $f$ such as: $ \left.S_{ \min \{ n \in \mathbb{N} | S_n>42\}} \mid S_p = \sum\limits_{i=1}^p \frac{1}{i} \right.$ $\endgroup$ – zooby Aug 8 '18 at 19:06
  • 4
    $\begingroup$ Please don't use italics for "min". $\endgroup$ – Andreas Rejbrand Aug 8 '18 at 20:07
19
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You make a good point. I think the set notation is the right notation to use in this case. $\endgroup$ – zooby Aug 8 '18 at 19:20
  • 6
    $\begingroup$ This is an important point to make: Imperative vs. declarative is a major impedence mismatch between "typical" programmers and "typical" mathematicians. Mathematicians are perfectly content to say that $\sum_{n=1}^\infty \frac{1}{2^n} = 1$, but you obviously cannot add infinitely many numbers one at a time. Programmers are fine with saying x=5 and then later x=10, even though that may seem a bit duplicitous to the mathematician. $\endgroup$ – Kevin Aug 9 '18 at 1:14
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, while writing it out in English is fine, it is a bit of a hole that there is no simple notation for the "repeat...until.." paradigm since this is such a key component of lots of algorithms. $\endgroup$ – zooby Aug 8 '18 at 17:16
  • $\begingroup$ @zooby but it's fine to describe an algorithm. $\endgroup$ – Andres Mejia Aug 8 '18 at 17:16
  • 2
    $\begingroup$ "Computer science notation" (aka pseudocode in this context) helps other humans understand you. Not computers, unless the language is interpreted. Algorithms are easier to understand when written in pseudocode than in English, just as equations are easier to understand when written in mathematical notation than in English. $\endgroup$ – Rosie F Aug 9 '18 at 6:03
  • $\begingroup$ @RosieF yeah, it depends. I think math notation is cumbersome sometimes too $\endgroup$ – Andres Mejia Aug 9 '18 at 8:29
2
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ You could write it that way but, egad, it's so much clearer in words. $\endgroup$ – David Richerby Aug 8 '18 at 18:47
  • $\begingroup$ @David well, it is a bit tricky when you have to check the difference between "sum until the result is over 42" and "sum up until the result is over 42 but not over" whereas the min/max makes things very precise. $\endgroup$ – zooby Aug 8 '18 at 19:22
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hmm... I think that's too much like a program. I was looking more for an expression you can manipulate. I like the set theory idea. I wonder how the F-F algorithm would be written in a set theory style! (Probably unreadable!) $\endgroup$ – zooby Aug 8 '18 at 19:36
  • 4
    $\begingroup$ @zooby "That's too much like a program." That's because that's precisely what it is. You aren't really distinguishing between "an mathematical object" and "an algorithm to compute such an object", and you should be. Sigma notation doesn't say anything about how to compute a sum; it just represents the result of any of the countless ways you could arrive at the sum. $\endgroup$ – chepner Aug 8 '18 at 20:22
  • 1
    $\begingroup$ You are right. The mathematical object is kind of like a question to which the algorithm is a way to (possibly) find the answer. Makes me wonder just what exactly is a mathematical object. Perhaps it is just a list of symbols. And an algorithm is a way in which to show that it can be replaced with another list of symbols without loss of consistency. In which case, it would be nice to represent the object as a short and readable list of symbols. $\endgroup$ – zooby Aug 8 '18 at 21:24
  • $\begingroup$ @zooby You can/do actually "manipulate expressions" in CS. Compilers do that, you do that if you do program verification. A programming language is a formal language for algorithms. $\endgroup$ – kutschkem Aug 9 '18 at 11:12
  • $\begingroup$ @zooby: A mathematical object is often an abstraction. Note that if you are interested in time/space complexity of your program, then you certainly do not want the mathematical function that corresponds to its output behaviour. In other words, many programs compute the same function, but may have wildly different time/space/resource usage. $\endgroup$ – user21820 Aug 9 '18 at 14:15
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You could use $\times_{i=1}^{n}a_i$ $\endgroup$ – clathratus Nov 6 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.