Project Euler 2

Problem #2:Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution: A straight forward implementation in C for this problem can be as shown

#include
#define LIMIT 4000000
int main()
{
 long a=1, b=2, c=0, sum=0;
 sum = b;
 while(c < LIMIT ){
  c = a+b;
  if(c < 1000000)
  if(c%2 == 0)
   sum += c;
  a = b;
  b = c;
 }
 printf("\nAnswer to euler #2 : %ld\n",sum);
}

        
                 This code works fine for our required need, but more optimizations can be done.How? Lets look at the fibo seq.

                                                    1 1 2 3 5 8 13 21 34 55 89 144 ...

                 As we can see,every 3rd term is a even number. Therefore we can change the code accordingly to just sum up every third number.
                 Another approach is we can find a recurrence funtion for this new series i.e. we can have :

F`(n)=4*F`(n-1) + F`(n-2)

It is easy to prove that for Fibonacci series we get:

 F(n)=4*F(n-3)+F(n-6) 

Thus we get a more faster running code, which we eventually need :-)

Enjoy coding :-)

My all time favourite Movies

Mughal-e-azam

A Wednesday

Munnabhai M.B.B.S

Swades - we the people

Dil Chahta Hai

Rang De Basanti

Project Euler 1

Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution : This can be done in two ways ....

i. The normal method, i.e. run a for from 1 to 1000 and check for the given condition on each number.

This method does solves our problem but is crude.

upperlimit=999
total_sum=0
for i=1 to upperlimit do
if (i mod 3=0) or (i mod 5)=0 then
total_sum:=total_sum+i;
output total_sum

ii. The short-cut method : In this you need only one formula and just need to compute value of 3 expressions.

Just go through---->

The solution to given problem will be the answer of this expression :

ans = sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15)

Now for n=3 :

3,6,9,12,15,18,21,24,27,.....,999 = 3(1,2,3,4,5,6,7,8,9,....,333)

Now we know that :

1 + 2 + 3 + .... + q = 1/2*q*(q+1)

In our case : q = upperlimit / n

Therefore our solution says :

Function sumDivisibleBy(n):
q = upperlimit div n
return n*(q*(q+1)) div 2
EndFunction

print sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)

Feel free to ask any kind of querry, I'll try my best to solve it.

Enjoy coding :-)

The Month of Purity and Patience

Ramzaan is the month of purity and patience that brings the human soul towards the Creator and makes him think about each and every small and wonderful things He has created. Fasting reschedules all your daily routines that we disturbed otherwise.

---------------------------------------------------------
Take account of yourself before you are called for account.

Bubble vs Quick Sort

A good comparision between Bubble Sort and Quick Sort.

Please Wait while the video loads.......

Impressed by Free Software........

The starting of the CoFSUG ( Coep's Free Software Users Group) club increased my curiosity towards the world of free software. FREEDOM IS OUR BIRTH RIGHT AND WE SHALL HAVE IT was been rightly said by one great freedom fighter which applies in almost every field.
My thinking got changed a lot and now I believe that the code contributed by a group of people is far more robust and secured than developed by an individual.If anyone wants to write any new implementable software from scratch then even if he has done with it, the code would not be that smarter as it would have been if it was a open source code.