mersenneforum.org > Math Residue classes
 Register FAQ Search Today's Posts Mark Forums Read

 2009-02-12, 20:17 #1 CRGreathouse     Aug 2006 32×5×7×19 Posts Residue classes Suppose I had a lot of residue classes and I wanted to find the probability that a random integer (mod the product of the moduli) was in at least one of the classes. How could I calculate that? If the moduli were pairwise coprime, it would be easy: start an accumulator at 0 and for each class a mod m, calculate acc <- acc + 1/m - acc/m and return the accumulator. But what if they're not? And what if there are a whole lot of residue classes, and their moduli are both large and fairly smooth (so they are 'far from' being coprime)? I'm picturing some kind of solution involving tracking products of small primes separately and using some version of the above algorithm for the large, and so probably coprime to everything else, prime factors. But is there a better way? Is there already a program/function/library that can do this for me? I'm actually reminded of a recent preprint by Neilsen ('a covering set with minimum modulus 40' or something like that), though this is by no means a covering set.
 2009-03-11, 15:46 #2 maxal     Feb 2005 22×32×7 Posts In other words, you need to find the probability of random integer to belong to the union of given residue classes. As it is easy to find probability that a random integer belongs to the intersection of residue classes (which would be 0 or 1/L where L is l.c.m. of the moduli, depending on whether this intersection is empty), just use the inclusion-exclusion principle to express the probability for the union in terms of the probabilities for the intersections: http://en.wikipedia.org/wiki/Inclusi...in_probability
 2009-03-12, 14:46 #3 CRGreathouse     Aug 2006 32×5×7×19 Posts Bingo. Thanks!
 2009-03-12, 15:28 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 24·3·7·19 Posts Thanks for the Nielsen reference; it's a lovely piece of higher-order abstraction. 0(2) 1(4) 0(5) 0(7) 3(8) 1(10) 1(14) 3(20) 3(28) 2(35) 39(40) 39(56) 27(70) 47(140) seems to be a covering with all moduli coprime to 3 ...
 2009-03-12, 16:00 #5 CRGreathouse     Aug 2006 32×5×7×19 Posts Did you see the video abstract? http://www.youtube.com/watch?v=3ev1YjVl0RY I thought it was neat to see Neilsen actually explaining it himself...

 Similar Threads Thread Thread Starter Forum Replies Last Post king Information & Answers 1 2018-03-05 05:52 Dubslow Lounge 67 2012-12-08 07:46 alpertron Miscellaneous Math 17 2012-04-30 15:28 Unregistered Information & Answers 6 2008-09-11 12:57 schneelocke PrimeNet 6 2003-11-22 01:26

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

Sat May 15 17:05:35 UTC 2021 up 37 days, 11:46, 0 users, load averages: 2.39, 2.07, 1.96