Square Subsets

For a set of positive integers $\{a, a+1, a+2, \dots , b\}$, let $C(a,b)$ be the number of non-empty subsets in which the product of all elements is a perfect square.
For example $C(5,10)=3$, since the products of all elements of $\{5, 8, 10\}$, $\{5, 8, 9, 10\}$ and $\{9\}$ are perfect squares, and no other subsets of $\{5, 6, 7, 8, 9, 10\}$ have this property.
You are given that $C(40,55) =15$, and $C(1000,1234) \bmod 1000000007=975523611$.
Find $C(1000000,1234567) \bmod 1000000007$.

There is a quite deep combinatorial approach to this problem. We need to recall a bit of number theory and combinatorics, and then tie it all together.

Let’s denote p as a prime number. We know from number theory, any positive integer can be expressed uniquely as a product of powers of prime numbers.

So, for a number to be a perfect square, the exponent of each prime in its prime factorization must be even.

If we look at a single prime number p, the powers of p from a to b, are $\{p^0, p^1, \dots, p^b\}$ if p divides b,
or $\{p^0, p^1, …, p^{b-1}\}$ if p does not divide b. When multiplied, they give $p^{0+1+2+…+b} = p^{\frac{b*(b+1)}{2}}$ if ‘p’ divides ‘b’ and similar for the case of ‘b-1’ if ‘p’ does not divide ‘b’.

The power of p in the product of any subset of these numbers is some number from 0 to $\frac{b*(b+1)}{2}$ or $\frac{(b-1)*b}{2}$. Also, since this power must be even in order for the total product to be a perfect square, we have at most $\frac{b}{2} + 1$ options for the power of p.

But this calculation is for each individual prime number p. For multiple primes, we need to use combinatorics to count how many subsets can have an even power for each prime.

An integer from a to b can be factored into various primes. Each prime may or may not be included in a subset, so we have 2 choices per prime. Since the power of each prime must be even, we basically ‘double’ the subsets where we include the prime. So we end up with the possibilities for each number being represented as 2 raised to the power of the number of different primes that factorize the number.

So for each number from a to b, we determine the number of distinct primes that factorize that number. We add those up, take the product over all integers from a to b, and that gives us $C(a, b) \bmod 1000000007$.

To further elaborate:

If we denote $d(n)=$ the number of distinct prime divisors of n, then:

$C(a, b) = 2^{(d(a) + d(a+1) + \dots + d(b))} \bmod 1000000007$.

Note: Calculation for large numbers can be complicated and you may need a strong programming language or calculators. To do this manually can be quite strenuous, especially for the large numbers asked in the end of the question. But hope you can understand the concept and the approach!

Let me explain further how we got here. ‘double’ the subset is actually a combinatorial term which we use when we have two choices for a situation. Here for each prime number, we have two choices whether to include it in our subset or not. That’s why we have ‘doubled’ the number of subsets. Then we raise 2 to the power of number of different prime factors each number from a to b has, because we have two choices for each of those primes. It’s crucial to note that, each selection of primes corresponds to a unique subset.

Then we are taking the product because we are making separate prime choices for each number from a to b. In other words, we make the prime choices for number ‘a’, then separately for number ‘a+1’, then ‘a+2’ and so on up to ‘b’. The total number of ways we can make prime choices for each number from a to b, is the product of the individual number of prime choices.

Please let me know, if you have any questions!

More Answers: