Combinatorial analysis using a prime list

Question

I ran across a puzzle and I would like to know if you guys could help me out. Let's suppose I've got a list with 2000000 prime numbers and there is a number (let's call it N) which is a product of two primes (P, Q)

I wanted to know how many possible combinations there could be testing each possibility, I know it is something related to combinatorial analysis but I am afraid I am not confident in this subject

thanks in advance

Answer 1

Notice a few things:

• We can choose any of the two primes with repetition.
• There are $2,000,000$ primes.
• The order of the primes doesn't matter, since multiplicative commutes ($a\cdot b = b \cdot a$).

This is identical to a selection with repetition problem: choosing $2$ primes from $2,000,000$ primes, with repetition.

Thus, we can use binomial coefficients with this. In general, if we have $n$ objects and want to choose from them $k$ objects, the number of such selections is given by

$$\binom{n+k-1}{k} \;\;\; \text{or, equivalently,} \;\;\; \binom{n+k-1}{n-1}$$

Here, $n=2,000,000$ and $k=2$. Thus, using the former formulation for simplicity:

$$\binom{n+k-1}{k} = \binom{2,000,000 + 2 - 1}{2} = \binom{2,000,001}{2} = \frac{2,000,001 \cdot 2,000,000}{2}$$

This is $2,000,000,100,000$ - two trillion, one hundred thousand in American units.

---

Thanks to Thomas Andrews for pointing this out in the comments.

As a follow-up regarding the intuition behind this method, this is generally known as the "stars and bars" method and is discussed, among other places, on Wikipedia.