What is the largest integer n such that 2 0 1 6 n divides 2 0 1 6 ! ?
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.
Can you please guide me to web that explains the formula on line 2 to me, not so familiar with theory of numbers? Thanks.
Log in to reply
Have you looked at the other solutions? They (in words) set out the idea.
Log in to reply
I understand the other solution well, not how you arrive at it. Thanks.
Log in to reply
@Niranjan Khanderia – For any positive integers N , n and prime p there are ⌊ p n N ⌋ integers between 1 and N that are divisible by p n . For any positive integer n , let j p ( n ) be the index of p in n . Let A n be the set of integers m between 1 and N for which j p ( m ) = n . Then the index of p in 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 } ∣ ∣ But j p ( m ) ≥ n precisely when p n divides m , and so this final expression is equal to I p ( N ) .
Log in to reply
@Mark Hennings – Thanks a lot for detailed explanation.
Same method, finding their prime factorization
Notice that from 1 to 2 0 1 6 there are:
⌊ 7 2 0 1 6 ⌋ = 2 8 8 numbers that have at least one factor of 7
⌊ 4 9 2 0 1 6 ⌋ = 4 1 more numbers that have an additional factor of 7
⌊ 3 4 3 2 0 1 6 ⌋ = 5 more number that adds an additional factor of 7
So, n ≤ 2 8 8 + 4 1 + 5 = 3 3 4 or 2 0 1 6 n will have more factors of 7 than 2 0 1 6 ! , which means that 2 0 1 6 n cannot divides 2 0 1 6 ! .
∴ n m a x = 3 3 4
These extra lines on the top, in black, are not mine!! it is not what I have written. 2 0 1 6 ! = 3 2 ∗ 9 ∗ 7 = 2 5 ∗ 3 2 ∗ 7 . N u m b e r o f 2 5 i n 2 0 1 6 ! ⌊ 2 2 0 1 6 ⌋ = 1 0 0 8 , a t l e a s t 1 0 0 8 n u m b e r s t h a t h a s 2 a s f a c t o r . . . . . . . ⌊ 2 2 2 0 1 6 ⌋ = 5 0 4 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 . . . . . . . ⌊ 2 3 2 0 1 6 ⌋ = 2 5 2 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 . . . . . . . ⌊ 2 4 2 0 1 6 ⌋ = 1 0 1 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 1 6 i s a f a c t o r . . . . . . . 1 0 0 8 + 5 0 4 + 2 5 2 = 1 7 6 4 , t h a t i s 2 1 7 6 4 > = ( 2 5 ) 3 5 2 . 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 2 0 1 6 ! h a s m o r e t h a n 3 5 2 " 2 5 = 3 2 " . N u m b e r o f 3 2 i n 2 0 1 6 ! ⌊ 3 2 0 1 6 ⌋ = 6 7 2 , a t l e a s t 6 7 2 n u m b e r s t h a t h a s 3 a s f a c t o r . . . . . . . 3 6 7 2 = ( 3 2 ) 3 3 6 . 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 2 0 1 6 ! h a s a t l e a s t 3 5 2 " 3 2 = 9 " . N u m b e r o f 7 i n 2 0 1 6 ! ⌊ 7 2 0 1 6 ⌋ = 2 8 8 . a t l e a s t 2 8 8 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 . . . . . . . . ⌊ 7 2 2 0 1 6 ⌋ = 4 1 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 . . . . . . . ⌊ 7 3 2 0 1 6 ⌋ = 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 > 2 0 1 6 , n o m o r e o f 7 i s a v a i l a b l e . 2 8 8 + 4 1 + 5 = 3 3 4 . T h u s o n l y 3 3 4 o f 7 a r e a v a i l a b l e . S o n = 3 3 4 .
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?
Problem Loading...
Note Loading...
Set Loading...
The index of a prime p in N ! is I p ( N ) = n = 1 ∑ ∞ ⌊ p n N ⌋ Since I 2 ( 2 0 1 6 ) = 2 0 1 0 , I 3 ( 2 0 1 6 ) = 1 0 0 4 , I 7 ( 2 0 1 6 ) = 3 3 4 we deduce that 2 0 1 6 ! = 2 2 0 1 0 × 3 1 0 0 4 × 7 3 3 4 × q where q and 4 2 are coprime. Now 2 0 1 6 = 2 5 × 3 2 × 7 , and hence 2 0 1 6 n divides 2 0 1 6 ! precisely when 5 n ≤ 2 0 1 0 , 2 n ≤ 1 0 0 4 and n ≤ 3 3 4 . Thus 2 0 1 6 n divides 2 0 1 6 ! when n ≤ 3 3 4 .