mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-03-05, 23:47   #1
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default 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.
vector is offline   Reply With Quote
Old 2008-03-06, 02:35   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by vector View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-06, 03:39   #3
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

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.
vector is offline   Reply With Quote
Old 2008-03-06, 04:06   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

17C416 Posts
Default

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.
retina is online now   Reply With Quote
Old 2008-03-06, 09:14   #5
Kees
 
Kees's Avatar
 
Dec 2005

110001002 Posts
Talking

I thought it was 37
Kees is offline   Reply With Quote
Old 2008-03-06, 09:27   #6
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

OK. And what is the smallest uninteresting number?
davieddy is offline   Reply With Quote
Old 2008-03-06, 09:58   #7
Kees
 
Kees's Avatar
 
Dec 2005

22·72 Posts
Default

well, 43 obviously

which makes it very uninteresting indeed
Kees is offline   Reply With Quote
Old 2008-03-06, 10:02   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

Reminds me of a code snipped I've seen somewhere:
Code:
/* Returns a random integer */
int random()
{
  return 4; /* Chosen by fair dice roll */
}
akruppa is offline   Reply With Quote
Old 2008-03-06, 12:01   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by vector View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-06, 18:36   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32·11·107 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2008-03-07, 16:14   #11
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
vector is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Problem E7 of Richard Guy's "Unsolved problems in number theory" Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19
Problem / Error using the "Time..." option petrw1 PrimeNet 1 2011-07-04 17:04
Joe McLean's "Sierpinski Problem to One Million" Spooty Prime Sierpinski Project 1 2008-02-03 05:27
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 03:33.

Sun Mar 7 03:33:20 UTC 2021 up 93 days, 23:44, 0 users, load averages: 1.98, 1.89, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.