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

Project Euler – Problem1

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000.

Here is a straight forward solution to this problem,

SELECT SUM(DECODE(MOD(ROWNUM,3),0,ROWNUM,

DECODE(MOD(ROWNUM,5,0,ROWNUM,0)))

FROM DUAL

CONNECT BY LEVEL <1000;

The logic is simple. The CONNECT BY clause in the above statement simply acts as row generator to generate natural numbers from 1 to 999.

The DECODEs inside the aggregate function check whether the number is divisible either by 3 or 5 if so the number is added.

This is a simple solution to understand but certainly not the best when it comes to performance. With the help of mathematical formula this problem can be solved little easier.

Multiples of 3 are 3, 6,9,12 … 999. Sum of them is

3+6+9+…999 = 3 ( 1+2 + … + [999/3]) ( [999/3] denotes integer part of 999/3 )

= 3 ([999/3]) ([999/3]+1)/2 ( 1 + 2+ … + n = n(n+1)/2)

Sum of multiples of 5 is

5 + 10 +15 +…[999/5] = 5([999/5]) ([999/5]+1)/2

The tricky part is the numbers 15, 30 …990 are included in both the case. This series should be subtracted once from the solution. So the final solution is

select trunc(999/3)* (trunc(999/3)+1) *3/2

+ trunc(999/5)* (trunc(999/5)+1) *5/2

- trunc(999/15)* (trunc(999/15)+1) *15/2 from dual;

Answer: 233168

Project Euler - An Ideal place to enhance your analytical skills

Think about this, you are in love with analytical problems and you are a software guy and you always feel comfortable when it comes to mathematics. One day you found a website where you have mathematical analytical puzzles and you are expected to solve them using your favorite software tool. Things cannot be better than this. Is in it? I just had the same feeling the moment I came to know the website “Project Euler” through few “siragu muzhaitha paravaigal” (colleagues who put their papers) having quality time with this website

This site completely swept my attention towards it from the moment I saw it. Being a mathematician by nature and software guy by profession, I could not restrict me from solving the puzzles despite a full packed busy schedule.

The objective is simple. Project Euler is a series of challenging mathematical problems. You need to solve them by using any of your favorite programming language in line with the "one-minute rule". This means, your algorithm implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

The “Project Euler” also comes with usual ingredients such as country level ranking, discussion forums, tips to build best algorithm (of course it’s hidden until you post your solution) and many more.

I have chosen interesting software which is not even in the list maintained by Euler Admin itself. Neither have I had any other choice as I know only s/w language since I started my career as IT professional. It is an interesting choice though…It is Oracle SQL and PL/SQL.

People who want to know more before kick-start this just check this link.