20080305, 23:47  #1 
Nov 2007
home
5^{2} 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. 
20080306, 02:35  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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. 

20080306, 03:39  #3 
Nov 2007
home
5^{2} 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. 
20080306, 04:06  #4 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
17C4_{16} 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. 
20080306, 09:14  #5 
Dec 2005
11000100_{2} Posts 
I thought it was 37

20080306, 09:27  #6 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
OK. And what is the smallest uninteresting number?

20080306, 09:58  #7 
Dec 2005
2^{2}·7^{2} Posts 
well, 43 obviously
which makes it very uninteresting indeed 
20080306, 10:02  #8 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} 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 */ } 
20080306, 12:01  #9  
Nov 2003
1D24_{16} Posts 
Quote:
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 NPComplete. I have a tentative sketch, based on taking logarithms after combining two of your congruences that reduces your problem to a subsetsum problem. 

20080306, 18:36  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{2}·11·107 Posts 
Quote:
My density function is that the probability of drawing x from Z is 1/N if 1<=x<=N and 0 otherwise. Paul 

20080307, 16:14  #11  
Nov 2007
home
5^{2} Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
Problem E7 of Richard Guy's "Unsolved problems in number theory"  Batalov  Computer Science & Computational Number Theory  40  20130316 09:19 
Problem / Error using the "Time..." option  petrw1  PrimeNet  1  20110704 17:04 
Joe McLean's "Sierpinski Problem to One Million"  Spooty  Prime Sierpinski Project  1  20080203 05:27 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 