Project Euler 268 - Counting numbers with at least four distinct prime factors less than 100

Official link: https://projecteuler.net/problem=268

Thought Process

If we have a product of k primes, N, then there will be 10^16//N numbers which are divisible by N, however this doesn't solve the problem, because lets say A = 2*3*5*7, and B = 2*3*5*11, then 2*3*5*7*11 is divisible by both A and B, and therefore will be double counted.

So some subtractions need to made, this is quite similar to the classic Inclusion-Exclusion principle.

  1. Take every possible subset of length 4 of the available primes, for each subset form N as stated above and then there will be 10^16//N numbers which are divisible by N, and now sum these all up for all different subsets, call this sum A1

    1. In short we have already counted all the numbers we want from the question, but we need to remove a bunch of them, and the question becomes how much exactly?

    2. Every product of 5 primes will be divisible by 5C4 = 5 products of 4 primes (2*3*5*7*11 is divisible by 2*3*5*7, 2*3*5*11, 2*5*7*11, 3*5*7*11)

    3. Every product of 6 primes will be divisible by 6C4 = 15 products of 4 primes

    4. etc, etc

  2. Now we take every possible subset of length 5 of the available primes, do the same as the first step, and now sum these all up for all different subsets, call this sum A2

    1. We remove 4 times A2 because of step 2.2 and now we will be left with the correct amount of numbers divisible by 4 primes and 5 primes

    2. However, now we note that every product of 6 primes will be divisible by 6C5 = 6 products of 5 primes and we have remove 4 times this amount, therefore we have removed 4*6 = 24 times the amount of numbers that are divisible by a product of 6 primes

    3. Our solution is now sitting at A1 - 4A2

  3. Now we take every possible subset of length 6 of the available primes, do the same as the first step, and now sum these all up for all different subsets, call this sum A3

    1. We added 15 times the amount of numbers divisible by a product of 6 primes in step 1.3 and we subtracted 24 times the amount of numbers divisible by a product of 6 primes in step 1.3, therefore we must add 10A3

    2. Therefore out, solution is now A1 - 4A2 + 10A3

You can see where this is going, and after a quick search on OEIS: I found the coefficients sequence, The tetrahedral numbers: https://oeis.org/A000292

To find A1, A2, ... we can use itertools.combinations and now the problem is done!

Interactive Code

Enter a number (yourinput)

Code will output the number of positive integers less than yourinput are divisible by at least four distinct primes less than 100.