how many zeros in the end of huge number

Note: Came across this Q at TIFR-Ph.D.entrance test.

Let n > 1 be an odd integer. How many zeros are at the end of number S = 99^n+1 (Read as S = 99 raised to the power n and then 1 added to it)

At first glance, this indicates some trick, for two reasons. First, S is going to be huge very fast, even with comparatively small n and second, this was asked in Ph.D test of TIFR! :D

I thought of splitting 99 as 100-1 and getting a generic result form for S.
i.e.

S = 99 ^ n - 1 = P - 1..................... s.t. P = 99 ^ n (n > 1, odd)
so,
P = 99 ^ n = (100 - 1) ^ n = (-1 + 100) ^ n
Using binomial theorem for expansion,
P = \sum_over_k=0_to_k=n {nCk * (-1)^k * 100 ^ (n-k)}
P = nC0 * (-1)^0 * 100 ^ n
   + nC1 * (-1)^1 * 100 ^ (n-1)
   + .....
   + nC{n-1} * (-1) ^ (n-1) * 100 ^ 1  ..................... note n-1 is even
   + nCn * (-1) ^ n * 100 ^ 0              ..................... note n is odd

Solving we get alternate terms positive and negative s.t. first term is positive (due to (-1)^0) and last term negative (due to (-1) ^ n, n being odd)

P = P1 - P2 + P3 - ....... - Pk + 100n - 1

where P1, P2, ..., Pk are terms which are multiples of powers (>=2) of 100.

Thus,
P = a_term_multiple_of_powers>=2_of_hundred +100n - 1

Thus,
S = P + 1 = a_term_multiple_of_powers>=2_of_hundred + 100n - 1 + 1 a_number_multiple_of_powers>=2_of_hundred + 100n = a_number_ending_with_two_zeros.

Thus, S ends with 2 zeros.

Prime number pairs summing to an odd number

While reading a book (details below), I came across a very nice problem as follows.

Find all pairs of prime numbers that sum up to 999.

As the book says, it involves thinking before actually attacking the problem. Few observations:

• Sum given is odd (999).
• To get sum odd, exactly one of the two numbers have to be even.
• Asked are the pairs of prime numbers.
• Meaning, we want intersection of prime and even which is just the number 2.

So, one of the numbers has to be 2; and thus the other of course is 997. And, that's the only pair of prime numbers which sums up to  999.

Cool indeed! :)

Book details:
Title:  math Charmers - Tantalizing Tidbits for the mind
Author: alfred s. posamentier
Publisher: University Press

Array with a mountain shape

Given an array in which initially elements start increasing till some index k and then they decrease. Find k.

Of course this asks us to find k in sub linear time. Otherwise, the most obvious solution is to check every element till elements increase and then at first drop in value, you get k. Sub linear acts as a hint for logarithmic. Logarithmic gives hint for dividing and throwing away some part, so that we reach a singleton or small enough set quickly. Let's see whether we can discard some part of the array. What if we pick the middle as we do in binary search? This gives us m=(i+j)/2 and m<=k or m>k. If we can somehow establish this relation between m and k (note: k is unknown, we have to find it), we can throw away the remaining part. How can we do this then? We know that k is the index such that on its left, the line plot of the array is ascending and on its right, it is descending. This means, if we are on left of k, we are on upward slope as against when we are on the right part of k. This hint is enough I guess. Once we get m, check a[m-1], a[m] and a[m+1] to get an indication about the region of slope where m belongs to, by comparison. Once we know that we are on upward slope, we know that m<=k, so we discard this part. Similarly for the case when m>k. Once we reduce problem size from n to n/2 at every iteration, we are in logarithmic space. Thus the algorithm performs in O(log n).