Brain Teaser - Indivisibility properties of sequence of numbers?

Mmmm homework =)

The easy way is to just list the primes in the range. The answer is not constant (the number gets fewer as the range gets higher)

I failed math.

Tnx DrBill. I agree that listing the primes gives an approximation but it is not very accurate. For example, if we consider the range 63… 93 w.r.t the range 4… 7, then 74, 82 and 86 are non-primes indivisible by 4 or 5 or 6 or 7.

Hold on—do you mean nondivisible by all the numbers in the smaller sequence?

yes, non-divisible by all the numbers in the smaller sequence.

I don’t see any way of doing this other than by trying to divide each number in the first sequnece by each number in the second.

@mowens me too.

After thinking about it, I realize that the problem can be solved without looking at every case, but the method is messy and takes a fair amount of work. It is worth doing only if the first set is fairly large and the second is fairly small. I will give a brief overview of what would have to be done. In the example that you give, first compute the size of the first set as 93 – 62 + 1 = 32. I am going to be looking at determining how many of these numbers are divisible by some number of the second set. To find out how many are not divisible, just subtract from 32.

To find out how many are divisible by 3, find 32/3 = 10. There may be one additional number that is divisible, which could be determined by use of modular arithmetic. You would do the same thing for 4, 5, 6 and 7. Add these values together.

Now you apply what is called the inclusion/ exclusion formula. The current value is too large because there has been double counting. To eliminate the double counting, look at each pair of numbers, say 3 and 4. To find how many numbers are divisible by both 3 and 4, find the least common multiple which is 3*4=12. Find out how many of the numbers of the first set are divisible by 12 and subtract from the previous.value. Do this for every pair of numbers.

Now you have to look at every set of 3 of the numbers, for example 3, 4 and 5. You want to add back how many are divisible by all three, which is just how many are divisible by the least common multiple, which in this case is 3*4*5=60. You would do this for every set of 3 whose product is not greater than 93.

Then you take numbers 4 at a time and subtract and then 5 at a time and add and so on. In the present example, it would not be necessary to go any further.

Tnx LostInParadise. Your solution does solve the problem though as you say it is a bit messy :)

We can use the logic in your second para to get an upper bound as well. For the example sequences 63… 93 and 3… 7: ⅓ of the numbers will be divisible by 3. ¼ of the remaining ⅔ numbers will be divisible by 4 and so on…

Remaining number of indivisibles at the end >= (⅔×¾×4/5×5/6×6/7) * (93–63+1)= 2/7 * 31. So the number of divisible numbers <= (5/7 * 31). The count of divisible numbers in 63… 93 w.r.t 3…7 is 22 <= (5/7×31).

I am still looking for a more elegant solution though to get the accurate count of indivisibles (if one exists) ... some mechanism that doesn’t become intractable for very large sequences.