1 | initial version |

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

2 | No.2 Revision |

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

To recap, we start from

- two integers
`n`

and`m`

- two increasing functions
- $f : [1, ..., n] \to mathbb{R}$
- $g : [1, ..., m] \to mathbb{R}$

and we define

- $A$ = {$f(i),\ i = 1 .. n$}
- $B$ = {$g(i),\ i = 1 .. m$}

We know these sets have a single common point and we want to find it.

Our choice is between:

go upwards

- start from the lowest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element from the set which had given us the lowest number

go upwards

- start from the highest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element down from the set which had given us the highest number

Here is the upwards version:

```
def common_element_upwards(f, g, n, m):
r"""
Return the common element between `A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (1 .. n))
B = (g(i) for i in (1 .. m))
a = next(A)
b = next(B)
while a != b:
if a < b:
a = next(A)
else:
b = next(B)
return a
```

Here is the downwards version:

```
def common_element_downwards(f, g, n, m):
r"""
Return a common element between the sets
`A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (n, n - 1 .. 1))
B = (g(i) for i in (m, m - 1 .. 1))
a = next(A)
b = next(B)
while a != b:
if a > b:
a = next(A)
else:
b = next(B)
return a
```

3 | No.3 Revision |

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

To recap, we start from

- two integers
`n`

and`m`

- two increasing functions
- $f : [1, ..., n] \to mathbb{R}$
- $g : [1, ..., m] \to mathbb{R}$

and we define

- $A$ = {$f(i),\ i = 1 .. n$}
- $B$ = {$g(i),\ i = 1 .. m$}

We know these sets have a single common point and we want to find it.

Our choice is between:

go upwards

- start from the lowest elements of $A$ and $B$
- check if they are
~~equal~~equal
- if so we're done
- if not take the next element from the set which had given us the lowest number

go upwards

- start from the highest elements of $A$ and $B$
- check if they are
~~equal~~equal
- if so we're done
- if not take the next element down from the set which had given us the highest number

Here is the upwards version:

```
def common_element_upwards(f, g, n, m):
r"""
Return the common element between `A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (1 .. n))
B = (g(i) for i in (1 .. m))
a = next(A)
b = next(B)
while a != b:
if a < b:
a = next(A)
else:
b = next(B)
return a
```

Here is the downwards version:

```
def common_element_downwards(f, g, n, m):
r"""
Return a common element between the sets
`A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (n, n - 1 .. 1))
B = (g(i) for i in (m, m - 1 .. 1))
a = next(A)
b = next(B)
while a != b:
if a > b:
a = next(A)
else:
b = next(B)
return a
```

4 | No.4 Revision |

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

To recap, we start from

- two integers
`n`

and`m`

- two increasing functions
- $f : [1, ..., n] \to mathbb{R}$
- $g : [1, ..., m] \to mathbb{R}$

and we define

- $A$ = {$f(i),\ i = 1 .. n$}
- $B$ = {$g(i),\ i = 1 .. m$}

We know these sets have a single common point and we want to find it.

Our choice is between:

go upwards

- start from the lowest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element from the set which had given us the lowest number

go upwards

- start from the highest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element down from the set which had given us the highest number

Here is the upwards version:

```
def common_element_upwards(f, g, n, m):
r"""
Return the common element between `A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (1 .. n))
B = (g(i) for i in (1 .. m))
a = next(A)
b = next(B)
while a != b:
if a < b:
a = next(A)
else:
b = next(B)
return a
```

Here is the downwards version:

```
def common_element_downwards(f, g, n, m):
r"""
Return a common element between the sets
`A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (n, n - 1 .. 1))
B = (g(i) for i in (m, m - 1 .. 1))
a = next(A)
b = next(B)
while a != b:
if a > b:
a = next(A)
else:
b = next(B)
return a
```

Example:

```
sage: f = lambda x: x^3 + 1
sage: g = lambda x: x^2
sage: n = 20
sage: m = 30
sage: common_element_upwards(f, g, n, m)
9
```

5 | No.5 Revision |

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

To recap, we start from

- two integers
`n`

and`m`

- two increasing functions
- $f : [1, ..., n] \to mathbb{R}$
- $g : [1, ..., m] \to mathbb{R}$

and we define

- $A$ = {$f(i),\ i = 1 .. n$}
- $B$ = {$g(i),\ i = 1 .. m$}

We know these sets have a single common point and we want to find it.

Our choice is between:

go upwards

- start from the lowest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element from the set which had given us the lowest number

go upwards

- start from the highest elements of $A$ and $B$
- check if they are equal
- if so we're done
- if not take the next element down from the set which had given us the highest number

Here is the upwards version:

```
def common_element_upwards(f, g, n, m):
r"""
Return the common element between `A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (1 .. n))
B = (g(i) for i in (1 .. m))
a = next(A)
b = next(B)
while a != b:
if a < b:
a = next(A)
else:
b = next(B)
return a
```

Here is the downwards version:

```
def common_element_downwards(f, g, n, m):
r"""
Return a common element between the sets
`A = \{ f(i): i = 1 .. n \}`
and `B = \{ g(i): i = 1 .. m \}`.
Assumptions:
- `f` and `g` are increasing functions
- `A` and `B` have a common element
"""
A = (f(i) for i in (n, n - 1 .. 1))
B = (g(i) for i in (m, m - 1 .. 1))
a = next(A)
b = next(B)
while a != b:
if a > b:
a = next(A)
else:
b = next(B)
return a
```

Example:

```
sage: f = lambda x: x^3 + 1
sage: g = lambda x: x^2
sage: n = 20
sage: m = 30
sage: common_element_upwards(f, g, n, m)
9
sage: common_element_downwards(f, g, n, m)
9
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.