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

Kaveh's question

Expand Messages
  • Kermit Rose
    ... Posted by: Phil Carmody thefatphil@yahoo.co.uk thefatphil Date: Sun Nov 12, 2006 12:40 am ((PST)) Note that to fail to cover the range, all you need is
    Message 1 of 4 , Nov 12, 2006
    • 0 Attachment
      --- Kaveh <kaveh_vejdani@...> wrote:

      > > Let A and B be two sets of n and m positive integers, respectively. We
      > > want to know if {(an element of A) - (an element of B)} covers the
      > > entire interval of [0,nm] or not, through an algorithm running faster
      > > than O(nm). (Something like fast fourier transform for fast
      > > multiplication).

      Posted by: "Phil Carmody" thefatphil@... thefatphil
      Date: Sun Nov 12, 2006 12:40 am ((PST))

      Note that to fail to cover the range, all you need is two terms in each set with
      the same difference, i.e. a1-a2=b1-b2. So perhaps looking at possible
      differences within each set individually is easier than looking at terms
      derived from elements of both sets.

      Phil


      Kermit wrote:

      Since we haven't been told the nature of sets A and B, we don't know
      whether or not it will be sufficient to
      look at only consecutive differences of the integers in each of A and B.

      Perhaps, given more information of the sets A and B, a theoretical
      analysis will prove that it's sufficient to look at only
      consecutive differences within each of A and B, thus making an algorithm
      of order ( n + m).
      [ Considering that need to also consider difference of first element and
      last element, thus making it order ( n + m), instead of order (n + m - 2) ]
    • Ronny Edler
      Hi! Maybe Kaveh could use a Monte Carlo-type test - i.e. pick a fixed number of randomly chosen k s to test and look whether the respective difference exists.
      Message 2 of 4 , Nov 12, 2006
      • 0 Attachment
        Hi!

        Maybe Kaveh could use a Monte Carlo-type test - i.e. pick a fixed number of
        randomly chosen k's to test and look
        whether the respective difference exists. This can be done in O( min(m,n) *
        iterationCount)
        [assuming you can check in O(1) whether a given number belongs to a set].

        Furthermore if there are at least two solutions to a given k, return false.

        Another simple tests that may speed up the process is to check first whether
        min_element(A) < max_element(B)
        If this holds return false, since one can construct a negative number thus
        missing at least one number from [0,mn-1].
        Runtime: O(max(m,n))

        I have constructed some covering sets - there aren't that many (if you bound
        the members of the set to be in [0,mn-1]!).
        So unless explicitly constructed it is very unlikely that two sets have the
        desired property
        [exponentially small in the number of iterations - if you choose each set
        member uniformly at random].

        HTH,
        Ronny
      • Billy Hamathi
        Hi, I am new to this group, and I have been doing some work on prime numbers that I feel I should share with others interested in prime numbers. I have
        Message 3 of 4 , Nov 13, 2006
        • 0 Attachment
          Hi,

          I am new to this group, and I have been doing some
          work on prime numbers that I feel I should share with
          others interested in prime numbers.

          I have attached a document that supports my claim,
          please comment on my paper after reading it.

          Thanks,

          Billy Hamathi.



          ___________________________________________________________
          The all-new Yahoo! Mail goes wherever you go - free your email address from your Internet provider. http://uk.docs.yahoo.com/nowyoucan.html

          [Non-text portions of this message have been removed]
        • Ronny Edler
          ... Actually there are _exactly_ 0% prime numbers in the naturals... There are about x/log(x) prime numbers less than x - see:
          Message 4 of 4 , Nov 14, 2006
          • 0 Attachment
            >There are approxiametly 29 % prime numbers in the positive integers range

            Actually there are _exactly_ 0% prime numbers in the naturals...

            There are about x/log(x) prime numbers less than x - see:
            http://primes.utm.edu/howmany.shtml

            Now the ratio primes/naturals = (x/log(x)) / x = 1/log(x) which converges to
            0 as x approaches infinity.


            Ronny
          Your message has been successfully submitted and would be delivered to recipients shortly.