Monday, August 29, 2011

Project Euler: What is the sum of both diagonals in a 1001 by 1001 spiral?

Problem#28: What is the sum of both diagonals in a 1001 by 1001 spiral?

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Solution:

Number present in the diagonals of first spiral is 1
Numbers present in the diagonals of second spiral is 3,5,7 and 9
Numbers present in the diagonals of third spiral is 13,17,21 and 25
Numbers present in the diagonals of Fourth spiral is 31,37,43 and 49

From above observation it is easy to conculde the following,

1. Every spiral has 4 diagonal numbers (except the first 1)
2. Diagonal numbers same spirals are arithmetic sequences
         3,5,7 and 9 with 2 as common difference
         13,17,21 and 25 as 4 as common difference
3. The value common difference in spiral s is 2(s-1)
     Ex: common diff of spiral 3 is 6 and spiral 4 is 8
4. The difference between last number of spiral s-1 and first number of spiral s is also  2(s-1).
     Ex: diff between last number and first number of spiral 2 and 3 respectively is 4 ( 13 -9)
         diff between last number and first number of spiral 3 and 4 respectively is 6 ( 31 -25)
5. Number of spirals in NxN matrix is N/2 + 1/2.       

The following PL/SQL solution is written based on the above findings,

DECLARE
   lv_final_value   NUMBER (10);
   lv_iter_value    NUMBER;
   lv_factor      NUMBER;
BEGIN
   lv_final_value := 1;
   lv_iter_value := 1;

   FOR i IN 2 .. 501
   LOOP
      lv_factor := 2 * (i - 1);
      lv_final_value := lv_final_value +lv_iter_value * 4 + lv_factor * 10;
      lv_iter_value := lv_iter_value + lv_factor * 4;
   END LOOP;

   DBMS_OUTPUT.PUT_LINE (lv_final_value);
END;



Answer: 669171001

Tuesday, August 2, 2011

How many zeros does 1000! end with?

Is it easy to find the number of zeros 1000! ends with? The answer is YES, it is very straight forward and the answer is 249.
[For the people who does not understand n!(n Factorial).
     1000! is called '1000 factorial' which is equivalent to 1 x 2 x 3 ...x1000.

The answer is [1000/5] + [1000/5^2 ] + [1000/5^3 ] + [1000/5^4 ]...  
             = [1000/5] + [1000/25] +[1000/125] + [1000/625]
             = 200 + 40 + 8 +1 = 249
( [n/p] stands for integer part of n/p. For instance [3/2 ] is 1 and [5/6] is 0. in computer terms FLOOR)

Rest of this post is only for the people who wants to know little more about the mathematical theorem stands behind this solution

Theorem:
if N is an integer, P is a prime number and N! = p^s . m then s = [ n/p]v+ [n/p^3] + [n/p^4]...


in our case N = 1000 and s is the solution we are looking for.What is the value for P? 10? but the theorem says P must be a prime number and 10 is not prime. But you know what 10 = 2 X 5 also 2 and 5 are prime numbers.
So instead of finding exponents of 10 in 1000!, we can find exponent values of 2 and 5 in 1000! and minimum value will be exponent value of 10 in 1000!
 In other words, if we can find the exponent value of 5 in 1000! we can happily say that many number of zeros will be at the end of 1000!.