1 0 0 7 0 2 1 0 3 5 0 3 5 0 2 1 0 0 7 0 0 1
How many positive divisors (including 1 and itself) does the large number above have?
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.
Good observation of the Pascal Triangle coefficients.
How you thinked about that?
Alex, Good day.. Where did you get this problem? May I know the source.. thank you sooo much it will be a tremendous help :)
I used CS.
same method!
Yay! Same method! Here's an upvote :P
Log in to reply
Hey, @Nihar Mahajan , how did u come up with the solution.. How did u think on it? I still cannot believe my eyes, seeing the solution...
Log in to reply
I observed the numbers 1 , 7 , 2 1 , 3 5 , 3 5 , 2 1 , 7 , 1 that reminded me of a row of pascal's triangle. Hence , I was able to solve it :)
Log in to reply
@Nihar Mahajan – Even i made the same observation
same here :D
I did the exact same . Each and every step
1 7 21 35 35 21 7 1 is the 7th row of Pascal's triangle. Any number 10^n+1 raised to a power m, will result in the nth row of Pascal's triangle represented as a number, each number in the triangle getting m digits. (Of course, if the nth row has a number > m digits, this pattern messes up). This can be verified by using a calculator with numbers 11, 101, 1001 etc. Simple multiplication shows us intuitively why that happens. Expanding using the binomial theorem gives formal justification.
Since this is the 7th row of the triangle, represented with 3 digits per number, this is (10^3+1)^7 = 1001^7. 1001 = 11 * 91 = 11 * 13 * 7
This number has exactly 3 prime factors, 7,11 and 13. To calculate the total number of positive divisors, we note that 7^7 11^7 13^7 can result in 8 8 8 = 512 different factors (including 1 and the number itself)
I used PAscal,but this is also quick solution:
z=1007021035035021007001=35x1001x10^9+21x(10^9+1)x10^6+7x(10^15+1)x10^3+10^21+1
Notist that 10^(3n)+1=(1000)^n+1=(-1)^n+1 (mod 1001)
so for odde n number 10^(3n)+1 is divided by 1001
Notis now that 999x1001x1000+1001=999999000+1001=10^9+1
so (10^9+1)/1001=999x1000+1=999001
10^15+1=(10^9+1)x10^6-10^6+1=1001x(999001x10^6-999)=999000999001
also 10^21+1=(10^15+1)x10^6-10^6+1=1001x(999000999001x10^6-999)=999000999000999001
so a=z/1001=1006015020015006001 = 15x(10^6+1)x10^6+6x(10^12+1)x1000+10^18+1+20x(10^9+1)-20
10^(6n)+1=(1000^2)^n+1=(-1x-1)^n+1=2 (mod 1001)
so a=15x2x1+6x2x(-1)+2-20=0 (mod 1001)
so b=a/1001=1005010010005001=5x(10^9+1)x1000+10^15+1+ 1001x10^7 is divided bu 1001 by previous
so c=b/1001=1004006004001=10^12+1+4x(10^6+1)x1000 is divided by 1001 by previous (2+2x1000 mod (1001))
so d=c/1001=1003003001=3x1001x1000+10^9+1 i sdivided by 1001 by previous
so e=d/1001=1002001=1001x1000+1001=1001x1001
now we see that z=1001^7=(7x11x13)^7= 7^7x11^7x13^7
so number of divisors is (7+1)^3=512
This was actually a problem from the HMMT guts round :)
Thanks Jonathan, appreciated
Try test of divisibility try for 7, 11, 13 combined test make groups of 3 digits each from the end
1 007 021 035 035 021 007 001
add groups odd places 001 + 021 + 035 + 007 = 64
add groups even places 007 + 035 + 021 + 1 = 64
find difference if difference is zero then the given number is divisible by 7, 11 and 13
or multiple of either 7, 11, 13 the number is divisible by either of 7, 11, or 13
here difference is zero so it is divisible by 7, 11, and 13 i.e. by 1001
find factors by dividing by 1001 you will get it is 1001^7
so factors are 7^7 × 11^7 × 13^7
so number of divisors = (7 + 1)^7 - 512
1 7 21 35 35 21 7 1 is the 7th row of Pascal's triangle. Any number 10^n+1 raised to a power m, will result in the nth row of Pascal's triangle represented as a number, each number in the triangle getting m digits. (Of course, if the nth row has a number > m digits, this pattern messes up). This can be verified by using a calculator with numbers 11, 101, 1001 etc. Simple multiplication shows us intuitively why that happens. Expanding using the binomial theorem gives formal justification. Since this is the 7th row of the triangle, represented with 3 digits per number, this is (10^3+1)^7 = 1001^7. 1001 = 11 * 91 = 11 * 13 * 7 This number has exactly 3 prime factors, 7,11 and 13. To calculate the total number of positive divisors, we note that 7^711^713^7 can result in 888 = 512 different factors (including 1 and the number itself)
Problem Loading...
Note Loading...
Set Loading...
Note that the number is equal to ( 0 7 ) 1 0 0 0 0 + ( 1 7 ) 1 0 0 0 1 + . . . + ( 7 7 ) 1 0 0 0 7 = ( 1 0 0 0 + 1 ) 7 = 7 7 × 1 1 7 × 1 3 7 , which has ( 7 + 1 ) ( 7 + 1 ) ( 7 + 1 ) = 5 1 2 factors.