- --- Kaveh <kaveh_vejdani@...> wrote:

> > Let A and B be two sets of n and m positive integers, respectively. We

Posted by: "Phil Carmody" thefatphil@... thefatphil

> > 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).

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. 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 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] >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