## Kaveh's question

Expand Messages
• ... 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) ]
• 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
• 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,

Thanks,

Billy Hamathi.

___________________________________________________________

[Non-text portions of this message have been removed]
• ... 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.