First we need to compute the number of trailing zeroes in 10000!
Based on that we should find out which digit to look for.
As 10 is divisible by 2 and 5 ( 10= 2*5) the trailing zeros shall come from power of
2 and 5.
So we should factor out the 5’s and 2’s from all the numbers from 1 to 10000 as factors and count them.
As there are much more number of 5’s then the 2’s we need to count the number of 5’s. 25 shall contribute to 2 5’s so we need to find out how may numbers are divisible by 5^2 and so on.
Number of numbers divisible by 5 = 2000
Number of numbers divisible by 5^2 = 400
Number of numbers divisible by 5^3 = 80
Number of numbers divisible by 5^4 = 16
Number of numbers divisible by 5^5 = 3
They contribute to 2000+ 400+80+16+3 = 2499 powers of 5.
As there are more number of 2’s than 5 we have 2499 trailing zeroes.
That is we need to find the right most non zero digit.
Before that we need to find out the how many powers of 2 and out of which 2499 shall go into multiplication with 5 to give the trailing zeroes.
Then We need to find the product of all the odd numbers(existing ones),
powers of 2 that are there in excess of power of 5 and all the odd numbers which we get after dividing by power of 2.
For example 6 = 2 * 3 and we have taken care of 2 then we need to multiply by 3 as for multiplication by 6 we need to multiply by 2 * 3.
Secondly we should not count by 5 as they are counted along with 2 for the trailing zeros as they have been accounted for.
Let us find out how many powers 2
5000 numbers are divisible by 2, 2500 out of which are divisible by 2^2 or 4, 1250 out of which divisible by 2^3 or 8, 625 out of which divisible by 2^4 or 16, 312 out of which divisible by 2^5 or 32, 156 out of which divisible by 2^6 or 64, 78 out of which divisible by 2^7 or 128,39 out of which divisible by 2^8 or 256,19 out of which divisible by 2^9 or 512,9 out of which divisible by 2^10 or 1024,4 out of which divisible by 2^11 or 2048,2 out of which divisible by 2^12 or 4096,1 out of which divisible by 2^13 or 8192.
So power of 2 = 5000 + 2500+1250+625+312+156+78+39+19+9+4+2+1 = 9995
So extra power of 2 after 5 = 9995-2499 or 7496
We know 2^4 = 6 mod 10 and 6^any number = 6 mod 10
So 2^7496 mod 10 = (2^4)^1874 = 6^1874 mod 10 = 6
Now computation of multiple of odd number (except 5) as it is considered below.
For counting odd numbers we successively divide all even numbers by 2 and take odd numbers only ignoring the numbers that ar 5 ending. We keep dividing each time by 2 so that a number that is multiple of power of 2 is eventually divided by power of 2 after successive divisions and odd number is left divide by highest power of 2 possible and get the odd digit at the end. So after each division we take care of odd number. This is so because for multiplying by 6 we need to multiply 3 and 2. Further for multiplily by 12 we need to multiply by 3 and 4. As we have to keep track of multiples of 2 separately we need to take care of numbers after multiplying by the odd number 3 that is left by successively by 2.
Additionally each set of 10 numbers from 10n to 10(n+1) we have 4 numbers 1*3*7*9 one time.
We realise that 1*3*7 *9 = -1 mod 10 and now we go multiplying as below, This is mentioned as this shall simplify the steps for calculation.
We give the data in tabular form what to multiply after successive division by 2.
S. no. Upto Product Product with previous result
6
10000 (1*3*7*9) ^1000 = (-1)^1000 = -1 6
10000/2 = 5000 -(1)^500 = 1 6
10000/2^2 = 2500 (-1) ^ 250 = 1 6
10000/2^3 = 1250 (-1)^125 = - 1 -6 or 4
10000/2^4 = 625 (-1)^*62 *1 *3 = 3 2
10000/2^5 = 312 (-1)^*31 *1 = -1 -2
10000/2^6 = 156 (-1)^*15 *1*3 = -3 6
10000/2^7 = 78 (-1)^*15 *1*3*7 = 1 6
10000/2^7 = 39 (-1)^*3 *1*3*7*9 = 1 6
10000/2^9 = 19 (-1)^*1 *1*3*7*9 = 1 6Upto 10000 are (-1) ^ 1000 = 1 (there are 1000) of each
1* 6 = 6
Devide by 2 and we get numbers upto 5000
Now odd numbers upto 5000 (-1) ^ 500 = 1
1* 6 = 6
Devide by 2 and we get numbers upto 2500
Now odd numbers upto 2500 (-1) ^ 250 = 1
1*6 = 6
Devide by 2 and we get numbers upto 1250
Now odd numbers upto 1250 (-1) ^ 125 = -1 or 9
9*6 = 54 = 4 mod 10
Devide by 2 and we get numbers upto 625
Now odd numbers upto 625 (-1) ^ 62*1*3 = 3
4*3 = 12 = 2 mod 10
Devide by 2 and we get numbers upto 312
Now odd numbers upto 312 (-1) ^ 31*1 = -1
2*(-1) = -2 or 8 mod 10
Devide by 2 and we get numbers upto 156
Now odd numbers upto 156 (-1) ^15 *1*3 = -3
8*3= 24 = 4 mod 10
Devide by 2 and we get numbers upto 78
Now odd numbers upto 78 (-1) ^7 *1*3*7 = -1
4*-1 = -4 or 6 mod 10
Devide by 2 and we get numbers upto 37
Now odd numbers upto 37 (-1) ^3 *1*3*7 = -1
6*-1 = -6 or 4 mod 10
Devide by 2 and we get numbers upto 19
Now odd numbers upto 19 (-1) ^1 *1*3*7*9 = 1
4*1 = 4 mod 10
Devide by 2 and we get numbers upto 9
Now odd numbers upto 9 (-1) = -1
4*-1 = -4 = 6 mod 10
Devide by 2 and we get numbers upto 4
Now odd numbers upto 4 (1*3) = 3
6*3 = 8 mod 10
Devide by 2 and we get numbers upto 2
Now odd numbers upto 2 (1) = 1
8*1 = 8 mod 10
Devide by 2 and we get numbers upto 1
Now odd numbers upto 1 (1) = 1
8*1 = 8 mod 10
So the required digit is 8 .
No comments:
Post a Comment