Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than:

  1. Increment current number by N.
  2. Check if current number is divisible any each number in blacklist (M checks if there are M primes in the blacklist).
  3. If so, jump to 1, else return the current number as the next number in the iteration.

My end goal would be an O(1) algorithm that lets me answer queries like, "Give me the 5th number that is a multiple of N but not a multiple of X, Y, or Z." But the above algorithm requires computing the 1-4th numbers first, so it's linear time.

I suspect the answer is no because it seems that if there is a way it would allow speeding up the Sieve of Eratosthenes. Although in some cases the sieve avoids redundant marking by starting at a prime square, it still redundantly marks numbers sometimes. For example the sieve will wastefully mark 60 three times, once for 2, once for 3, and once for 5. You can see this by watching 60 light up three different colors in the linked Wikipedia article's first graphic:

enter image description here

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Up to $kN$ (inclusive) there are $k$ positive integer multiples of $N$, of which $\lfloor k/X \rfloor$ are multiples of $X$, etc. By inclusion-exclusion, the number that escape a "blacklist" of $3$ primes is $$ k - \left\lfloor \frac{k}{X} \right\rfloor - \left\lfloor \frac{k}{Y} \right\rfloor - \left\lfloor \frac{k}{Z} \right\rfloor + \left\lfloor \frac{k}{XY} \right\rfloor + \left\lfloor \frac{k}{XZ} \right\rfloor + \left\lfloor \frac{k}{YZ}\right\rfloor - \left\lfloor \frac{k}{XYZ}\right\rfloor $$ Approximate it without the $\lfloor \cdot \rfloor$'s, and you're off by at most $4$, so then adjust...

EDIT: For example, suppose you want the $35$'th positive integer multiple of $N$ (any prime other than $5$, $7$ or $11$) that is not a multiple of $X=5$, $Y=7$ or $Z=11$. Thus you want $k$ so that $$f(k) = k - \left\lfloor \frac{k}{X} \right\rfloor - \left\lfloor \frac{k}{Y} \right\rfloor - \left\lfloor \frac{k}{Z} \right\rfloor + \left\lfloor \frac{k}{XY} \right\rfloor + \left\lfloor \frac{k}{XZ} \right\rfloor + \left\lfloor \frac{k}{YZ}\right\rfloor - \left\lfloor \frac{k}{XYZ}\right\rfloor = 35$$ Now $$\eqalign{k &- \frac{k}{X} - \frac{k}{Y} - \frac{k}{Z} + \frac{k}{XY} + \frac{k}{XZ} + \frac{k}{YZ} - \frac{k}{XYZ} \cr &= k \left(1-\frac{1}{X}\right)\left(1 -\frac{1}{Y}\right) \left( 1 - \frac{1}{Z}\right) = \frac{48 k}{77}}$$ which would be $35$ for $k = 56.14\ldots$. Now $f(56) = 34$ so we try $f(57)$ and find that this is $35$. Thus $57N$ is the multiple of $N$ we are looking for.

share|improve this answer
    
If I understand right, this computes the size of the set of numbers I want to iterate, but it doesn't help with iterating or computing e.g. the 5th number, or am I not thinking hard enough yet? –  Joseph Garvin Jan 8 '13 at 3:09
    
No, you don't understand. I'll edit my answer to include an example. –  Robert Israel Jan 9 '13 at 5:06
    
Ah, that makes more sense, thanks. –  Joseph Garvin Jan 10 '13 at 20:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.