Power of 2016 dividing 2016!

What is the largest integer n n such that 201 6 n 2016^n divides 2016 ! ? 2016!\, ?


The answer is 334.

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.

3 solutions

Mark Hennings
Aug 22, 2017

The index of a prime p p in N ! N! is I p ( N ) = n = 1 N p n I_p(N) \; = \; \sum_{n=1}^\infty \left\lfloor \frac{N}{p^n}\right\rfloor Since I 2 ( 2016 ) = 2010 I_2(2016) = 2010 , I 3 ( 2016 ) = 1004 I_3(2016) = 1004 , I 7 ( 2016 ) = 334 I_7(2016) = 334 we deduce that 2016 ! = 2 2010 × 3 1004 × 7 334 × q 2016! \; = \; 2^{2010} \times 3^{1004} \times 7^{334} \times q where q q and 42 42 are coprime. Now 2016 = 2 5 × 3 2 × 7 2016 = 2^5 \times 3^2 \times 7 , and hence 201 6 n 2016^n divides 2016 ! 2016! precisely when 5 n 2010 5n \le 2010 , 2 n 1004 2n \le 1004 and n 334 n \le 334 . Thus 201 6 n 2016^n divides 2016 ! 2016! when n 334 n \le \boxed{334} .

Can you please guide me to web that explains the formula on line 2 to me, not so familiar with theory of numbers? Thanks.

Niranjan Khanderia - 3 years, 9 months ago

Log in to reply

Have you looked at the other solutions? They (in words) set out the idea.

Mark Hennings - 3 years, 9 months ago

Log in to reply

I understand the other solution well, not how you arrive at it. Thanks.

Niranjan Khanderia - 3 years, 9 months ago

Log in to reply

@Niranjan Khanderia For any positive integers N , n N,n and prime p p there are N p n \big\lfloor \tfrac{N}{p^n} \big\rfloor integers between 1 1 and N N that are divisible by p n p^n . For any positive integer n n , let j p ( n ) j_p(n) be the index of p p in n n . Let A n A_n be the set of integers m m between 1 1 and N N for which j p ( m ) = n j_p(m) = n . Then the index of p p in N ! N! is m = 1 N j p ( m ) = n = 1 n A n = n = 1 n { 1 m N j p ( m ) = n } = n = 1 n ( { 1 m N j p ( m ) n } { 1 m N j p ( m ) n + 1 } ) = n = 1 n { 1 m N j p ( m ) n } n = 2 ( n 1 ) { 1 m N j p ( m ) n } = n = 1 { 1 m N j p ( m ) n } \begin{aligned} \sum_{m=1}^N j_p(m) & = \; \sum_{n=1}^\infty n \big|A_n\big| \; = \; \sum_{n=1}^\infty n\big|\big\{1 \le m \le N \; \big| \; j_p(m) = n\big\}\big| \\ & = \; \sum_{n=1}^\infty n\left(\big|\big\{1 \le m \le N \; \big| \; j_p(m) \ge n\big\}\big| - \big|\big\{1 \le m \le N \;\big|\; j_p(m) \ge n+1\big\}\big|\right) \\ & = \; \sum_{n=1}^\infty n \big|\big\{1 \le m \le N \; \big| \; j_p(m) \ge n\big\}\big| - \sum_{n=2}^\infty (n-1)\big|\big\{1 \le m \le N \; \big| \; j_p(m) \ge n\big\}\big| \\ & = \; \sum_{n=1}^\infty \big|\big\{1 \le m \le N \; \big|\; j_p(m) \ge n \big\}\big| \end{aligned} But j p ( m ) n j_p(m) \ge n precisely when p n p^n divides m m , and so this final expression is equal to I p ( N ) I_p(N) .

Mark Hennings - 3 years, 9 months ago

Log in to reply

@Mark Hennings Thanks a lot for detailed explanation.

Niranjan Khanderia - 3 years, 9 months ago

Same method, finding their prime factorization

Jason Chrysoprase - 3 years, 9 months ago
Linkin Duck
Aug 22, 2017

Notice that from 1 1 to 2016 2016 there are:

2016 7 = 288 \left\lfloor \frac { 2016 }{ 7 } \right\rfloor =288 numbers that have at least one factor of 7 7

2016 49 = 41 \left\lfloor \frac { 2016 }{ 49 } \right\rfloor =41 more numbers that have an additional factor of 7 7

2016 343 = 5 \left\lfloor \frac { 2016 }{ 343 } \right\rfloor =5 more number that adds an additional factor of 7 7

So, n 288 + 41 + 5 = 334 n\le 288+41+5=334 or 2016 n { 2016 }^{ n } will have more factors of 7 7 than 2016 ! { 2016 }! , which means that 2016 n { 2016 }^{ n } cannot divides 2016 ! { 2016 }! .

n m a x = 334 \therefore \quad { n }_{ max }=334

These extra lines on the top, in black, are not mine!! it is not what I have written. 2016 ! = 32 9 7 = 2 5 3 2 7. N u m b e r o f 2 5 i n 2016 ! 2016 2 = 1008 , a t l e a s t 1008 n u m b e r s t h a t h a s 2 a s f a c t o r . . . . . . . 2016 2 2 = 504 n u m b e r s t h a t h a s 2 a s f a c t o r , a d d i t i o n a l n u m b e r s i n c e 4 i s a f a c t o r . . . . . . . 2016 2 3 = 252 n u m b e r s t h a t h a s 2 a s f a c t o r , a d d i t i o n a l n u m b e r s i n c e 8 i s a f a c t o r . . . . . . . 2016 2 4 = 101 n u m b e r s t h a t h a s 2 a s f a c t o r , a d d i t i o n a l n u m b e r s i n c e 16 i s a f a c t o r . . . . . . . 1008 + 504 + 252 = 1764 , t h a t i s 2 1764 > = ( 2 5 ) 352 . I n f a c t t h e r e a r e m o r e 2 s d u e t o h i g h e r p o w e r s o f 2. S o 2016 ! h a s m o r e t h a n 352 " 2 5 = 32 " . N u m b e r o f 3 2 i n 2016 ! 2016 3 = 672 , a t l e a s t 672 n u m b e r s t h a t h a s 3 a s f a c t o r . . . . . . . 3 672 = ( 3 2 ) 336 . I n f a c t t h e r e a r e m o r e 3 s d u e t o h i g h e r p o w e r s o f 3. S o 2016 ! h a s a t l e a s t 352 " 3 2 = 9 " . N u m b e r o f 7 i n 2016 ! 2016 7 = 288. a t l e a s t 288 n u m b e r s n u m b e r s t h a t h a s 7 a s f a c t o r . . . . . . . . 2016 7 2 = 41 n u m b e r s t h a t h a s 7 a s f a c t o r , a d d i t i o n a l n u m b e r s i n c e 7 2 i s a f a c t o r . . . . . . . 2016 7 3 = 5 n u m b e r s t h a t h a s 7 a s f a c t o r , a d d i t i o n a l n u m b e r s i n c e 7 3 i s a f a c t o r . . . . S i n c e 7 4 > 2016 , n o m o r e o f 7 i s a v a i l a b l e . 288 + 41 + 5 = 334. T h u s o n l y 334 o f 7 a r e a v a i l a b l e . S o n = 334. ~~~~~\\ ~~~\\ \Large \text{These extra lines on the top, in black, are not mine!! it is not what I have written.}\\ ~~~\\ \color{#E81990} {2016! =32*9*7=2^5*3^2*7.}\\ ~~\\ \color{#20A900} {Number~ of~2^5~in~2016!\\ \left\lfloor \frac { 2016 }{ 2 } \right\rfloor =1008,~at~least~1008~ numbers~ that~ has~ 2 ~as~ factor.......\\ \left\lfloor \frac { 2016 }{ 2^2 } \right\rfloor =~~ 504~ numbers~ that~ has~ 2 ~as~ factor,~additional~number~since~4~is~a~factor.......\\ \left\lfloor \frac { 2016 }{ 2^3 } \right\rfloor =~~ 252~ numbers~ that~ has~ 2 ~as~ factor,~additional~number~since~8~is~a~factor.......\\ \left\lfloor \frac { 2016 }{ 2^4} \right\rfloor =~~ 101~ numbers~ that~ has~ 2 ~as~ factor,~additional~number~since~16~is~a~factor.......\\ 1008+504+252=1764,~that~is~~2^{1764}>=(2^5)^{352}. ~In ~fact~there~are~more ~2s~due~to~higher~powers~of~2.\\ So~2016!~has~more~than~352~~~"~2^5=32~".}\\ ~~~~\\ \color{#EC7300} {Number~ of~3^2~in~2016!\\ \left\lfloor \frac { 2016 }{ 3 } \right\rfloor =672,~~at~least~672~ numbers~ that~ has~ 3 ~as~ factor.......\\ 3^{672}=(3^2)^{336}.~~~In ~fact~there~are~more ~3s~due~to~higher~powers~of~3.\\ \\ So~2016!~has~at~least~~352~~"~3^2=9~".}\\ ~~~~\\ \color{#3D99F6} {Number~ of~7~in~2016!\\ \left\lfloor \frac { 2016 }{ 7 } \right\rfloor =288.~ ~at~least~288~ numbers~ numbers~ that~ has~ 7 ~as~ factor........\\ \left\lfloor \frac { 2016 }{ 7^2 } \right\rfloor =~41~ numbers~ that~ has~ 7 ~as~ factor,~additional~number~since~7^2~is~a~factor.......\\ \left\lfloor \frac { 2016 }{ 7^3} \right\rfloor =~5~ numbers~ that~ has~ 7 ~as~ factor,~additional~ number~since~ 7^3~is~a~ factor....\\ Since~7^4>2016, ~no~more~of~7~is~available.\\ 288+41+5=334.}\\ ~~~\\ Thus ~only~334~of~7~are~available.\\ So~n=\Large \color{#D61F06}{334}.

Thanks to Mr. Linkin Duck . I adopted his style of presentation. As such I have only added more explanation to his solution.

Any reason why I am getting extra lines on the top?

Niranjan Khanderia - 3 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...