Count The Divisors

There is a certain number N = n 1 n 2 n 3 n k N = n_1\cdot n_2\cdot n_3\cdots n_k , where 1 n i 100 1 \leq n_i \leq 100 ( 1 i k ) (1\le i \le k) are all distinct positive integers.

We are told the following:

  • N N has d d (positive) divisors and d d is odd.
  • 128 N 128\cdot N has 18 11 d \frac{18}{11}d divisors.
  • 175 N 175\cdot N has 8 5 d \frac 8 5 d divisors.
  • 213 N 213\cdot N has 8 3 d \frac 8 3 d divisors.

If 2016 N 2016\cdot N has A B d \frac A B d divisors, with A A and B B coprime positive integers, submit A + B A + B .


The answer is 871.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Arjen Vreugdenhil
Oct 22, 2016

Relevant wiki: Number of Factors

Key fact: if the prime factorization of N N is N = 2 e 2 3 e 3 5 e 5 p e p , N = 2^{e_2} \cdot 3^{e_3} \cdot 5^{e_5} \cdots p^{e_p} \cdots, then the number of divisors of N N is δ ( N ) = ( 1 + e 2 ) ( 1 + e 3 ) ( 1 + e 5 ) ( 1 + e p ) . \delta(N) = (1+e_2)(1+e_3)(1+e_5)\cdots (1+e_p)\cdots.

From the fact that δ ( N ) \delta(N) is odd, we know that all exponents e i e_i must be even, so that N N is a perfect square. In particular, this means that N N contains no prime factors greater than 50.

Using 128 = 2 7 128 = 2^7 , we have δ ( 128 N ) δ ( N ) = ( 1 + e 2 + 7 ) ( 1 + e 3 ) ( 1 + e 2 ) ( 1 + e 3 ) = 8 + e 2 1 + e 2 = 18 11 , \frac{\delta(128N)}{\delta(N)} = \frac{(1+e_2+7)(1+e_3)\cdots}{(1+e_2)(1+e_3)\cdots} = \frac{8+e_2}{1+e_2} = \frac{18}{11}, which tells us immediately that e 2 = 10 e_2 = 10 .

Now 213 = 3 71 213 = 3\cdot 71 , so δ ( 213 N ) δ ( N ) = ( 2 + e 3 ) ( 2 + e 71 ) ( 1 + e 3 ) ( 1 + e 71 ) = 8 3 . \frac{\delta(213N)}{\delta(N)} = \frac{(2+e_3)(2+e_{71})}{(1+e_3)(1+e_{71})} = \frac{8}{3}. We already know that e 71 = 0 e_{71} = 0 , so that we find 2 + e 3 1 + e 3 = 4 3 , \frac{2+e_3}{1+e_3} = \frac{4}{3}, making e 3 = 2 e_3 = 2 .

Next, 175 = 7 5 2 175 = 7\cdot 5^2 , giving δ ( 175 N ) δ ( N ) = ( 3 + e 5 ) ( 2 + e 7 ) ( 1 + e 5 ) ( 1 + e 7 ) = 8 5 . \frac{\delta(175N)}{\delta(N)} = \frac{(3+e_5)(2+e_7)}{(1+e_5)(1+e_7)} = \frac 8 5. To solve this, we cross-multiply, work out brackets, and subtract, and refactor (I find it convenient to multiply everything by 3): 5 ( 3 + e 5 ) ( 2 + e 7 ) = 8 ( 1 + e 5 ) ( 1 + e 7 ) ; 5(3+e_5)(2+e_7) = 8(1+e_5)(1+e_7); 30 + 10 e 5 + 15 e 7 + 5 e 5 e 7 = 8 + 8 e 5 + 8 e 7 + 8 e 5 e 7 ; 30 + 10 e_5 + 15 e_7 + 5 e_5 e_7 = 8 + 8 e_5 + 8 e_7 + 8 e_5 e_7; ( 3 e 5 7 ) ( 3 e 7 2 ) = 80 ; (3 e_5 - 7)(3 e_7 - 2) = 80; there are ten positive integer factorizations of 80, and only four of them result in integer values for e 5 e_5 and e 7 e_7 . Of these four, only one has even values: e 5 = 4 e_5 = 4 and e 7 = 6 e_7 = 6 .

Thus we know that N = 2 10 3 2 5 4 7 6 N = 2^{10}\cdot 3^2\cdot 5^4\cdot 7^6\cdots Using 2016 = 2 5 3 2 7 2016 = 2^5\cdot 3^2\cdot 7 , we get 2016 N = 2 15 3 4 5 4 7 7 2016N = 2^{15}\cdot 3^4\cdot 5^4\cdot 7^7\cdots and A B = δ ( 2016 N ) δ ( N ) = 16 5 5 8 11 3 5 7 = 640 231 , \frac A B = \frac{\delta(2016N)}{\delta(N)} = \frac{16\cdot 5\cdot 5\cdot 8}{11\cdot 3\cdot 5\cdot 7} = \frac{640}{231}, making the answer 871 \boxed{871} .

Great detailed solution!

  1. I think you should explain why "this means that contains no prime factors greater than 50." in more detail.
  2. Playing devil's advocate, is there an N , n i N, n_i that satisfies the conditions of the problem?

Thanks for contributing and helping other members aspire to be like you!

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

Take n 1 = 28 , n 2 = 35 , n 3 = 40 , n 4 = 49 , n 5 = 50 , n 7 = 72 , n 8 = 98 n_1 = 28, n_2 = 35, n_3 = 40, n_4 = 49, n_5 = 50, n_7 = 72, n_8 = 98 .

I don't think you can do it with fewer factors!

Arjen Vreugdenhil - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...