u220e's profile - activity

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

5336 * 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.

The "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:

Success! Now, I just need to find a way to program the index $i$ to make it less expensive.

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

Here'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.

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

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

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.