What is the best algorithm to solve this puzzle?

Question

So I came across this question:

How many numbers are there from 1 to 1000 which are not divisible by the digits 2, 3 and 5?

It seems pretty easy at first, so I wrote a quick python program to solve it:

count = 0
for number in range(1,1000):
    if number % 2 != 0 and number % 3 != 0 and number % 5 != 0:
        count += 1
print(count)

I got the correct answer (266), but I thought that doing it that way was a lot of typing if I ever wanted to check more than just 3 values. I also wanted to do a mathematical solution so I came across this:

1000 - ((1000/2 +1000/3 +1000/5) -(1000/2x3 +1000/2x5 + 1000/3x5)+ (1000/2x3x5)) = 1000-((500+333+200) - (166 +100 + 66) + 33) = 1000- 734 = 266

I thought it was a good approach so I implemented it in code:

def foo(ln = 1000), numbers = [2,3,5]:
    div = 0
    muldiv = 0
    totdiv = 1


    for n in numbers:
        div += ln/n
    for i in numbers:
        for n in range(numbers.index(i)+1, len(numbers)):
            muldiv += ln/(i * numbers[n])

    for n in numbers:
        totdiv *= n

    answer = ln - (div - muldiv + ln/totdiv)
    print("answer is ", math.floor(answer))

Now I am pretty sure I messed up somewhere in my second function because it doesn't seem to work for more numbers. For example, if I were to try to find

How many numbers are there from 1 to 1000 which are not divisible by the digits 2, 3, 5 and 7?

the first method returns 228 and foo(numbers = [2,3,5,7]) returns 300... I'm pretty sure 228 is the correct answer since one more number would mean that there are LESS factors instead of more, but where did I go wrong? and is there a better way to solve this problem?

Answer 1

You do not need an algorithm for that, simple mathematics is enough:

Say you want to count the amount of numbers from 1 to N (inclusive) dividable by k, that is simply equivalent to:

floor(N/k).

So the amount of numbers dividable by 3 in this case is 333.

Now you can't however simply use calculate the amount of numbers dividable by 2, 3 and 5; and sum them up, because there are common ones. Indeed: for instance 15 is dividable by both 3 and 5.

You can solve this however using the inclusion-exclusion principle:

the amount of numbers dividable by 2, 3 and 5 is the same as

• the amount numbers dividable by 2
• plus the amount of numbers dividable by 3
• plus the amount of numbers dividable by 5
• minus the amount of numbers dividable by 2 and 3
• minus the amount of numbers dividable by 2 and 5
• minus the amount of numbers dividable by 3 and 5
• plus the amount of numbers dividable by 2, 3 and 5.

So in order to solve your first problem, you can simply state:

def n_div(N,k):
    return N//k

def n_div235(N):
    return n_div(N,2)+n_div(N,3)+n_div(N,5)-n_div(N,2*3)-n_div(N,2*5)-n_div(N,3*5)+n_div(N,2*3*5)

def not_div235(N):
    return N-n_div235(N)

As you can see it generates the correct result:

>>> not_div235(1000)
266

As long as N is very large compared to the number of divisors, you better use the inclusion-exclusion approach:

you can do this like:

import itertools
from functools import reduce
import operator

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(ks):
    res = 1
    for k in ks:
        res = lcm(res,k)
    return res

def n_div_gen(N,ks):
    nk = len(ks)
    sum = 0
    factor = 1
    for i in range(1,nk+1):
        subsum = 0
        for comb in itertools.combinations(ks,i):
            subsum += n_div(N,lcm_list(comb))
        sum += factor * subsum
        factor = -factor
    return sum

def not_div_gen(N,ks):
    return N-n_div_gen(N,ks)

For small N, this will not pay off, but say to want to calculate the amount of numbers dividable by 3, 5 and 7 from 1 to 1 000 000 000 is:

>>> not_div_gen(1000000000,[3,5,7])
457142857

You can do this with:

>>> sum(i%3!=0 and i%5!=0 and i%7!=0 for i in range(1,1000000001))
457142857

But it takes minutes to calculate that whereas our own approach uses milliseconds. Note that this only works for a huge N.

Answer 2

Use the built-in functions sum and all with a nested generator:

def f(r=1000, nums=(2,3,5)):
    return sum(all(x%n for n in nums) for x in range(1, r+1))

This goes through the range of numbers, check whether each of those numbers has a nonzero modulus with each of the specified numbers, and sums those boolean values (False is 0 and True is 1). A nums of (2,3,5,7) produces a result of 228, which is in agreement with your shorter, simpler code (which, reassuringly, doesn't use any floating-point arithmetic, as your second code block does).

Answer 3

The number of integers up to N not divisible by n₁,n₂,...,n_t (assumed to be pairwise-coprime) is

    the number of integers up to N minus
  ( SUM_{i in 1..t} ( the number of integers up to N divisible by n_i)) plus
  ( SUM_{i,j in 1..t, i<j} ( the number of integers up to N divisible by n_in_j)) minus
  ( SUM_{i,j,k in 1..t, i<j<k} ( the number of integers up to N divisible by n_in_jn_k)) plus
  ( SUM_{i,j,k,l in 1..t, i<j<k<l} ( the number of integers up to N divisible by n_in_jn_kn_l)) minus
... ... ... ...
  ( SUM_{i,j,k,l,...q in 1..t, i<j<k<l<...<q} ( the number of integers up to N divisible by n_in_jn_kn_l...n_q))

The series continues until the subscript contains all t integers from the original list.

For numbers that are not known to be pairwise-coprime, replace their product by the least common multiple.

This is why your method works only for 3 numbers. You only compute the first four members of the series.