mersenneforum.org > Math Modular Subset "Product" Problem
 Register FAQ Search Today's Posts Mark Forums Read

 2008-03-05, 23:47 #1 vector     Nov 2007 home 52 Posts Modular Subset "Product" Problem 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.
2008-03-06, 02:35   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

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

 2008-03-06, 03:39 #3 vector     Nov 2007 home 52 Posts 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.
 2008-03-06, 04:06 #4 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 137548 Posts 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.
 2008-03-06, 09:14 #5 Kees     Dec 2005 3048 Posts I thought it was 37
 2008-03-06, 09:27 #6 davieddy     "Lucan" Dec 2006 England 145128 Posts OK. And what is the smallest uninteresting number?
 2008-03-06, 09:58 #7 Kees     Dec 2005 22·72 Posts well, 43 obviously which makes it very uninteresting indeed
 2008-03-06, 10:02 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Reminds me of a code snipped I've seen somewhere: Code: /* Returns a random integer */ int random() { return 4; /* Chosen by fair dice roll */ }
2008-03-06, 12:01   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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
subset-sum problem.

2008-03-06, 18:36   #10
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

23×113 Posts

Quote:
 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

2008-03-07, 16:14   #11
vector

Nov 2007
home

318 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19 petrw1 PrimeNet 1 2011-07-04 17:04 Spooty Prime Sierpinski Project 1 2008-02-03 05:27 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 17:45.

Tue Apr 20 17:45:17 UTC 2021 up 12 days, 12:26, 1 user, load averages: 3.87, 3.75, 3.65