q-: Magic Fractions | Practice Problems
anyone please explain me, how to solve this problem.
for every i from 1 to n, find the possible magic fractions for i.
To find possible magic fractions for a particular i :
You just need the no of primes upto i.
why:
If prime factorization for i! is (2^x * 3^y *…11^z) then:
possibilities for a and b can be (2^x-1 * 3^y-1… , 2 * 3 …) or (2^x * 3^y… , 11^z…).
it is clear that 1st possibility is not correct (as gcd wont be 1).
so we doesn’t care about prime powers, we care about no of primes.
so possibilities for a and b can be 2^(no of distinct primes in i!)/2 (selecting a and b from i!) and no of distinct primes in i! is nothing but no of primes upto i.