Calculating the minimum element of an intersection of countable sets.

Discussion in 'Recreational Math' started by Guest, Jan 30, 2006.

  1. Guest

    Guest Guest

    Hi - I have solved this (I think), using brute-force. However, I can't
    help but think there must be a better way!

    Let's call my sets A(n) = {t(n) + k.w(n) | k is 0,1,2,3...}
    I wish to calculate min(intersect(A(n), for all n))

    Fortunately, in my application, n is only 5: t(n)=2,3,4,7,9 and
    w(n)=7,13,17,19,23. My minimum common element comes out as 477,857 - a
    prime. (Calculated by software.)
    Originally I thought the answer would be related to the least common
    multiple of the t(n)s and/or w(n)s, but this doesn't seem the case.

    Any number theorists about? ;)

    Thanks :)
    Christopher Harrison
     
    Guest, Jan 30, 2006
    #1
    1. Advertisements

  2. Guest

    Chip Eastham Guest

    Hi, Christopher:

    The cases you describe, at least with finitely many values of n,
    are solved by what is commonly called the Chinese Remainder
    Theorem if the values w(n) are pairwise coprime. That is:

    X = t(n) mod w(n) for all n

    has a unique solution X modulo the least common multiple of
    the w(n)'s. But since we assume their pairwise coprimality,
    the least common multiple is the product of all w(n)'s.

    If the w(n)'s are not coprime, then there may be no solution.
    For example {0,6,12,18,...} and {2,11,20,29,...} have no
    intersection, due to the common factor between "strides"
    6 and 9. If there is a solution, then it is unique modulo the
    least common multiple of the w(n)'s, even if these are not
    coprime.

    The theory above one says that the least _positive_
    solution X lies between 1 and 7*13*17*19*23 = 676,039.
    Obviously this accords with the solution you gave being
    smaller than this. The fact that the solution turned out
    to be prime is a bit of coincidence, helped in particular
    by the requirement that none of the five w(n)'s will be
    divisors (since the corresponding t(n)'s are nonzero).

    Without some requirement on the solution other than
    being an integer, there is no minimum value because
    the modulus 7*13*17*19*23 = 676,039 could be
    subtracted from any solution to give a "lesser" one.

    Did you have a more specific question than whether
    the solution is "related" to the least common multiple
    of the w(n)'s ?


    regards, (IANANT) chip
     
    Chip Eastham, Feb 4, 2006
    #2
    1. Advertisements

  3. Thanks very much Chip :) IANANTE ;) I really should remember the
    Chinese Remainder Theorem, though: I'm a mathematics graduate, and it
    was mentioned several times - never had a use for it until now...
    Thanks for reminding me!

    I didn't have any specific questions as to how my solution was related
    - I just needed a solution (which I've got) and thought there might
    have been a neater way to find it than brute force. Mind you, I guess
    putting a restriction on my sets makes things a little easier.

    Thanks :)
    Christopher Harrison
     
    Christopher Harrison, Feb 6, 2006
    #3
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.