Ask Your Question

Revision history [back]

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

check out this tutorial:

Reading about iterators

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

check out this tutorial:

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

Reading about iterators

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

check out this tutorial:

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

Reading about iterators

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

check out this tutorial:

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

Reading about iterators

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

check out this tutorial:

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)
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.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59