ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 07 Sep 2020 01:45:53 +0200Set-Intersection Iterationhttps://ask.sagemath.org/question/53246/set-intersection-iteration/Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.
I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)
I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):
(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).
(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).
(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).
Thanks in advance.Tue, 01 Sep 2020 01:38:15 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/Comment by FrédéricC for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53251#post-id-53251Yes, you could do that using "iterators" that produce elements in increasing order one by one.Tue, 01 Sep 2020 16:14:24 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53251#post-id-53251Comment by u220e for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53257#post-id-53257Great. Could you point me to a site/book that will show me how to write this kind of iterative code? The tutorials I've read only show basic for- or while-loop constructions with one or two nested if-then conditions.Tue, 01 Sep 2020 23:39:18 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53257#post-id-53257Comment by slelievre for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53265#post-id-53265In the question you write:
> I wrote some basic code in Sage to calculate elementary
> set intersection, but for even moderately large cardinalities,
> the halt time was incredibly long.
Please provide the code you wrote so far and we can help build from that.Wed, 02 Sep 2020 23:32:16 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53265#post-id-53265Comment by slelievre for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53266#post-id-53266To display blocks of code or error messages in Ask Sage, skip a line
above and below, and do one of the following (all give the same result):
- indent all code lines with 4 spaces
- select all code lines and click the "code" button (the icon with '101 010')
- select all code lines and hit ctrl-K
For instance, typing
> If we define `f` by
>
> def f(x, y, z):
> return x * y * z
>
> then `f(2, 3, 5)` returns `30` but `f(2*3*5)` gives:
>
> TypeError: f() takes exactly 3 arguments (1 given)
produces:
> If we define `f` by
>
> def f(x, y, z):
> return x * y * z
>
> then `f(2, 3, 5)` returns `30` but `f(2*3*5)` gives:
>
> TypeError: f() takes exactly 3 arguments (1 given)
Please edit your question to add your code formatted in that way.Wed, 02 Sep 2020 23:33:31 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53266#post-id-53266Comment by u220e for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53268#post-id-53268Here's the code. The most basic set intersection based on my research/reading:
sage: n=[some integer]; L=[f_1(x) for x in sxrange(1,(n+1)/2)]; M=[f_2(x) for x \
....: in sxrange(1,(n+1)/2)]; [x for x in L if x in M]
For arbitrarily large $n$, this is too expensive from a time-complexity standpoint.Thu, 03 Sep 2020 00:52:56 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53268#post-id-53268Answer by slelievre for <p>Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.</p>
<p>I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)</p>
<p>I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):</p>
<p>(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).</p>
<p>(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).</p>
<p>(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).</p>
<p>Thanks in advance.</p>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?answer=53261#post-id-53261### Reading about iterators
On the "Thematic tutorials" page of the SageMath documentation:
- [https://doc.sagemath.org/html/en/thematic_tutorials/](https://doc.sagemath.org/html/en/thematic_tutorials/)
check out this tutorial:
- [Tutorial: Comprehensions, Iterators, and Iterables](https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html)
### Answer to the question
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)
9Wed, 02 Sep 2020 14:49:41 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?answer=53261#post-id-53261Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53264#post-id-53264Thanks. I've been through those tutorials, but I'll check them again in case I missed something. I've found "Computational Mathematics with SageMath" to be an excellent resource, but I'm still having trouble with the syntax of indices as they relate to iterative commands.Wed, 02 Sep 2020 22:34:42 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53264#post-id-53264Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53269#post-id-53269Fantastic...and not anything I've seen in the tutorials/literature, which means I would have been looking forever! I can't wait to try it and let you know how it goes. Thanks again.Thu, 03 Sep 2020 02:24:04 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53269#post-id-53269Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53282#post-id-53282Success! Now, I just need to find a way to program the index $i$ to make it less expensive.Thu, 03 Sep 2020 23:02:39 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53282#post-id-53282Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53285#post-id-53285The "upwards" code works for very small $n$, but I keep getting a "StopIteration" error when using numbers even as small as four digits:
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-259-34dce5deec42> in <module>()
----> 1 n=(Integer(5335)+Integer(1))/Integer(2); common_element_upwards(f, g, n, m)
<ipython-input-252-4f212b87ce54> in common_element_upwards(f, g, n, m)
17 a = next(A)
18 else:
---> 19 b = next(B)
20 return a
StopIteration:Fri, 04 Sep 2020 00:20:05 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53285#post-id-53285Comment by slelievre for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53286#post-id-53286The `StopIteration` error happens when one of the sets runs out and no common element was found.
One could use a try/except to catch that and return a more meaningful error message in that case.Fri, 04 Sep 2020 01:24:42 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53286#post-id-53286Comment by slelievre for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53287#post-id-53287> The "upwards" code works for very small $n$, but I keep getting
> a "StopIteration" error when using numbers even as small as four digits:
You are not saying with what `f` and `g` that happens.
Also, beware, `(5335 + 1) / 2` gives a rational, not an integer
(in case that matters for what you do with it).
Use `(5335 + 1) // 2` for the integer version.Fri, 04 Sep 2020 01:27:42 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53287#post-id-53287Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53290#post-id-532905336 * 1/2 = 2668 is an element of $\mathbb{Z}$. Both approaches work
sage: 5336/2
2668
sage: 5336//2
2668
and there hasn't been a problem when using similarly calculated values (e.g., $n=14$, etc). I tried both syntaxes just to make sure, though, and I get the same error. (I thought I'd just get the `sage:` prompt if no results were found; that's been the case so far.)
So, "upwards" seems to work for (roughly) $n<200$ but not with even slightly larger values I've confirmed *do* work with the "downwards" algorithm. Go figure. Thanks for all your help.Fri, 04 Sep 2020 02:29:29 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53290#post-id-53290Comment by slelievre for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53310#post-id-53310Here is what I meant:
sage: a = 62 // 2
sage: a
31
sage: a.parent()
Integer Ring
sage: b = 62 / 2
sage: b
31
sage: b.parent()
Rational Field
So, in a way `a` and `b` are equal,
sage: a == b
True
but in some ways they might behave differently.
sage: a.is_prime()
True
sage: b.is_prime()
False
sage: a.is_unit()
False
sage: b.is_unit()
TrueSat, 05 Sep 2020 11:47:21 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53310#post-id-53310Comment by slelievre for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53311#post-id-53311Debugging the failing example would require basic information:
- What are `f`, `g`, `n`, `m` in that example?
- Are `f` and `g` increasing functions?Sat, 05 Sep 2020 11:51:42 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53311#post-id-53311Comment by u220e for <h3>Reading about iterators</h3>
<p>On the "Thematic tutorials" page of the SageMath documentation:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/">https://doc.sagemath.org/html/en/thematic_tutorials/</a></li>
</ul>
<p>check out this tutorial:</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials/tutorial-comprehensions.html">Tutorial: Comprehensions, Iterators, and Iterables</a></li>
</ul>
<h3>Answer to the question</h3>
<p>To recap, we start from</p>
<ul>
<li>two integers <code>n</code> and <code>m</code></li>
<li>two increasing functions
<ul>
<li>$f : [1, ..., n] \to mathbb{R}$</li>
<li>$g : [1, ..., m] \to mathbb{R}$</li>
</ul></li>
</ul>
<p>and we define</p>
<ul>
<li>$A$ = {$f(i),\ i = 1 .. n$}</li>
<li>$B$ = {$g(i),\ i = 1 .. m$}</li>
</ul>
<p>We know these sets have a single common point and we want to find it.</p>
<p>Our choice is between:</p>
<ul>
<li><p>go upwards</p>
<ul>
<li>start from the lowest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element from the set which had given us the lowest number</li>
</ul></li>
</ul></li>
<li><p>go upwards</p>
<ul>
<li>start from the highest elements of $A$ and $B$</li>
<li>check if they are equal
<ul>
<li>if so we're done</li>
<li>if not take the next element down from the set which had given us the highest number</li>
</ul></li>
</ul></li>
</ul>
<p>Here is the upwards version:</p>
<pre><code>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
</code></pre>
<p>Here is the downwards version:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53342#post-id-53342I understand the integer ring-rational field distinction in Sage, but it's not an issue for other calculations that follow the exact same process (e.g., `(27+1)/2`, etc.)—where we get the correct output and no error message. Unfortunately, I'm not at liberty to define the functions in a public forum, but, yes, they are "monotone (or strictly) increasing" functions given the required parameters.Mon, 07 Sep 2020 01:45:53 +0200https://ask.sagemath.org/question/53246/set-intersection-iteration/?comment=53342#post-id-53342