Modular Subset "Product" Problem

[vector]

Is there info on how to solve this type of problem somewhere?

Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are not repeated)
Now merge one congruence A[i] mod B[i] with another congruence and join the resulting congruence with other unjoined congruences as many times as needed until you get a congruence with the lowest ratio of A/B that is possible from the set of congruences.

[R.D. Silverman]

Originally Posted by vector

Is there info on how to solve this type of problem somewhere?

Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are not repeated)
Now merge one congruence A[i] mod B[i] with another congruence and join the resulting congruence with other unjoined congruences as many times as needed until you get a congruence with the lowest ratio of A/B that is possible from the set of congruences.

This is pseudo-babble; It is not a math problem. It is non-rigorous
GIBBERISH.

You have failed to specify the meaning of "merge one congruence with
another". Does "unjoined" mean the same as "not yet merged"? One
presumes so, but the word "join" is also undefined. Just because
"join" and "merge" are synonyms in English does not guaranteee that
they must mean the same thing in a math problem.

And you have not defined A or B. You have defined A[i]
and B[i], but the meanings of A, B, and A/B are vague mysteries.

And finally, there is no such thing as a "random integer" or "random prime".
They don't exist.

[vector]

Joining/merging means using the Chinese remainder theorem on congruences (a1 mod b1) and (a2 mod b2) to get another congruence of the form (a3 mod b1*b2).

For a congruence (A mod B) or (3 mod 11) the ratio A/B is 3/11 or 0.272727272727272727.....

The set of congruences can be: (2 mod 3);(3 mod 5);(4 mod 7);(1 mod 11)

The Chinese remainder theorem can be used on more than two congruences at the same time.
This problem involves using Chinese remainder theorem on a specific subset of these congruences to produce a congruence A mod B such that the ratio A/B is smaller than the ratio produced by using the Chinese remainder theorem on any other subset of congruence set.

I have no comment for your disbelief in random numbers.

[retina]

I remember a report once stating that 17 is the least random number.

Ask people to think of a random number and 17 is given more often than any other number.

[Kees]

I thought it was 37

[davieddy]

OK. And what is the smallest uninteresting number?

[Kees]

well, 43 obviously

which makes it very uninteresting indeed

[akruppa]

Reminds me of a code snipped I've seen somewhere:

/* Returns a random integer */
int random()
{
  return 4; /* Chosen by fair dice roll */
}

[R.D. Silverman]

Originally Posted by vector

Joining/merging means using the Chinese remainder theorem on congruences (a1 mod b1) and (a2 mod b2) to get another congruence of the form (a3 mod b1*b2).

For a congruence (A mod B) or (3 mod 11) the ratio A/B is 3/11 or 0.272727272727272727.....

The set of congruences can be: (2 mod 3);(3 mod 5);(4 mod 7);(1 mod 11)

The Chinese remainder theorem can be used on more than two congruences at the same time.
This problem involves using Chinese remainder theorem on a specific subset of these congruences to produce a congruence A mod B such that the ratio A/B is smaller than the ratio produced by using the Chinese remainder theorem on any other subset of congruence set.

I have no comment for your disbelief in random numbers.

You are clueless. Nothing in my post indicated that I "disbelieve" in random
numbers. I said that random integers and random primes do not exist.
They do not. Random integers DRAWN FROM A SUBSET OF Z with a specified density function exist.

There is no way to draw an integer at random from the set of all integers.
There is no way to draw a prime at random from the set of all primes.
You must specify a density function.

Although I do not have the details, I am sure that your problem is NP-Complete. I have a tentative sketch, based on taking logarithms after
combining two of your congruences that reduces your problem to a
subset-sum problem.

[xilman]

Originally Posted by R.D. Silverman

You are clueless. Nothing in my post indicated that I "disbelieve" in random
numbers. I said that random integers and random primes do not exist.
They do not. Random integers DRAWN FROM A SUBSET OF Z with a specified density function exist.

Warning: nitpicking follows.

My density function is that the probability of drawing x from Z is 1/N if 1<=x<=N and 0 otherwise.


Paul

[vector]

Originally Posted by R.D. Silverman

Although I do not have the details, I am sure that your problem is NP-Complete. I have a tentative sketch, based on taking logarithms after
combining two of your congruences that reduces your problem to a
subset-sum problem.

Why are you taking logarithms of the congruences? This will not accomplish anything. You cant represent and apply the Chinese remainder theorem operation logarithmically, your algorithm would just return utter nonsense.

If this problem involved multiplying a bunch of numbers together then it might work. I called this a product problem because multiplication is the closes analogy I know to operation of Chinese remainder theorem.

The best algorithm I have so far involves finding "common remainders of remainders." For example: (9 mod 33) and (2 mod 7) makes (9 mod 231) because (9 mod 7) = (2 mod 7)
Now if there was a way to use Chinese remainder theorem on a "small congruence" and a "large congruence which has a small remainder" such that the "large congruence's remainder increases but not by too much" this algorithm be usable in practice because the first algorithm would be able to be reused efficiently.