mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-02-12, 20:17   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2009-03-11, 15:46   #2
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

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
maxal is offline   Reply With Quote
Old 2009-03-12, 14:46   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134528 Posts
Default

Bingo. Thanks!
CRGreathouse is offline   Reply With Quote
Old 2009-03-12, 15:28   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

632210 Posts
Default

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 ...
fivemack is offline   Reply With Quote
Old 2009-03-12, 16:00   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134528 Posts
Default

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...
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Residue and Shift, what do these mean? king Information & Answers 1 2018-03-05 05:52
Classes Dubslow Lounge 67 2012-12-08 07:46
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
Primes in residual classes Unregistered Information & Answers 6 2008-09-11 12:57
Masked residue schneelocke PrimeNet 6 2003-11-22 01:26

All times are UTC. The time now is 20:29.

Sun Oct 25 20:29:41 UTC 2020 up 45 days, 17:40, 0 users, load averages: 1.07, 1.44, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.