Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Real life

Expand Messages
  • Ronny Edler
    ... To clarify on this: You have a _fixed_ set A and want to construct a set B, such that the differences span the interval [0,mn-1], with all members of A and
    Message 1 of 3 , Nov 14, 2006
      > In the real life of computation, my B set is flexible. I should
      > generate k*m numbers is B until the [0,nm] range is covered. So
      > actully the real problem is to find optimal k such that the range of
      > question is covered. But checking the coverage in O(nm) is way too
      > slow. So I need to resolve this before I can worry about k.

      To clarify on this: You have a _fixed_ set A and want to construct a set B,
      such that the differences span the
      interval [0,mn-1], with all members of A and B are in [0,mn-1]?

      Furthermore, as an answer of your algorithm you need something like:
      "Here is a set B that satifies the constraints" or "I have proven that no
      such B exists".

      Well, i think that unless you construct B, testing abitrarily generated sets
      will take you a _long_ time.

      Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6 choose 2) =
      20*15 = 300 possible set combinations.

      The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
      B={0,3}.

      That is 2 out of 300. (m,n are tiny! here)

      > Ronny, I guess your test will take O(nm) again to guarantee that the
      > entire range is covered, right?

      Yes, if you keep track of the numbers you already tested.

      Ronny
    • Kaveh
      No Ronny. A and B are both fixed sets of n and km positive integers, and their elements are not arbitrary. The problem is not to construct A and B, but to
      Message 2 of 3 , Nov 14, 2006
        No Ronny. A and B are both "fixed" sets of n and km positive integers,
        and their elements are not arbitrary. The problem is not to construct
        A and B, but to check if their differences cover the range [0,nm].

        Best wishes.

        Kaveh



        --- In primenumbers@yahoogroups.com, "Ronny Edler" <ronny.e@...> wrote:
        >
        > > In the real life of computation, my B set is flexible. I should
        > > generate k*m numbers is B until the [0,nm] range is covered. So
        > > actully the real problem is to find optimal k such that the range of
        > > question is covered. But checking the coverage in O(nm) is way too
        > > slow. So I need to resolve this before I can worry about k.
        >
        > To clarify on this: You have a _fixed_ set A and want to construct a
        set B,
        > such that the differences span the
        > interval [0,mn-1], with all members of A and B are in [0,mn-1]?
        >
        > Furthermore, as an answer of your algorithm you need something like:
        > "Here is a set B that satifies the constraints" or "I have proven
        that no
        > such B exists".
        >
        > Well, i think that unless you construct B, testing abitrarily
        generated sets
        > will take you a _long_ time.
        >
        > Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6
        choose 2) =
        > 20*15 = 300 possible set combinations.
        >
        > The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
        > B={0,3}.
        >
        > That is 2 out of 300. (m,n are tiny! here)
        >
        > > Ronny, I guess your test will take O(nm) again to guarantee that the
        > > entire range is covered, right?
        >
        > Yes, if you keep track of the numbers you already tested.
        >
        > Ronny
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.