Project Euler : Smallest Multiple

Problem Statement :

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

This is basically finding the LCM of first 20 natural numbers.

Method 1:

Brute force method would be to go in a loop 

check if the number is divisible by all 20 numbers (using if else statements ) otherwise increase the number and  repeat till you find the answer.

Method 2:

Find the LCM the normal way.

Let x be divisible by any number less than all numbers less than 20.

Any number can be represented as a product of all prime numbers (raised to powers) less than itself. So, any number < 20 can represent as a product of prime numbers less than 20.

x =  2pow(k1)*3pow(k2)*5pow(k3)*7pow(k4)*11pow(k5)*13pow(k6)*17pow(k7)*19pow(k8)

k1, k2, k3... such that they are equal to the highest power used with the corresponding prime while representing any number less than 20.

for 2:
the highest value of k1 would be 4 for 16 = 2^4;

for 3:

the highest value of k2 would be 2 for 9 = 3^2;

for 5 or other primes > 5:

the highest value of k3,k4.... would be 1 as  5^2 =25 > 20;

so x = 2^4*3^2*5*7*11*13*17*19 = 232792560;

.

Project Euler : Even Fibonacci Numbers

Problem Statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Generally Fibonacci Sequence is defined as follows:

F(1) =1;
F(2)=1;
F(n) = F(n-1)+F(n-2); for n > 2;

* here F(1) is omitted;

so instead of 1,1,2,3,5,8,....  it is just 1,2,3,5,8,........

Look up the wiki for Fibonacci Sequence http://en.wikipedia.org/wiki/Fibonacci_number

Brute-force Method :

C#

namespace euler
{
    class Program
    {
        private static void Main(string[] args)

        {
            int i = 0;
            int f1 = 1;
            int f2 = 2;
            int f = 0;
            int sum = f2;
            while (f <= 4000000)
            {
                f = f1 + f2;
                f1 = f2;
                f2 = f;
                if (f%2 == 0)
                    sum = sum + f;
            }
            Console.Write(sum);
            Console.ReadLine();
        }
    }
}
     
Define the first two numbers in the sequence i.e. f1 = 1 and f2 = 2 . Initialize the sum to 0.


Calculate the next number  f in the sequence , if it is even add it to the sum.

Move the index one up so that now f1(new) = f2(old) and f2(new) =f to calculate the next number.

One interesting observation is that even Fibonacci numbers occur 3 places apart.

eg : 2,3,5,8     8, 13, 21,34 and so on

it goes  even, odd, odd, even and so on

(Could be proven by Mathematical Induction)



The following should be faster because of the lesser number of loops required

            while (f <= 4000000)
            {
                f = 2*f1+3*f2;
                f1 = f1+2*f2;
                f2 = f;
                f = 2*f1 + 3*f2;
                sum = sum + f2;
            }

Ans : 4613732

Let me know what you think of the Post in the Comments.

Project Euler : Multiples of 3 and 5

Problem 1:  Multiples of 3 and 5

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.

c# :
     
            int i = 1000;

            int sum = 0;
            for (int j = 3; j < i; j++)
            {
                if (j % 3 == 0 || j % 5 == 0)
                    sum = sum + j;

            }
            Console.Write(sum);
            Console.ReadLine();
     


---
Problem is pretty straight forward,
just loop through the numbers less than 1000 (started from 3 to save two loops :) )
if either 3 or 5 divides the number evenly, add it to the sum.