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

If primality of the elements of A and B helps with the task, let's

assume they're all prime.

David and Phil, cool catch of the pigeonhole. I had overlooked that in

my formulation. As Phil said about FFT, I just need to check the

coverage, without generating the unnecessary intermediates.

So the output size is not really nm, it's a mere 1 digit or, say, if

you want to break the [0,nm-1] range into m sub-intervals of size n,

an output of size m would suffice. (Each digit telling if the

corresponding sub-interval is covered or not).

Ronny, I guess your test will take O(nm) again to guarantee that the

entire range is covered, right?

Thanks all for all the great feedbacks. Looking forward to your

further thoughts and guidelines.

Best wishes,

Kaveh > In the real life of computation, my B set is flexible. I should

To clarify on this: You have a _fixed_ set A and want to construct a set B,

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

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

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

> entire range is covered, right?

Ronny- 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

>