Project Euler – Problem # 11 – Solved with Java

What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?

In the 2020 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 * 63 * 78 * 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

One Possible Solution: Java

public class Problem_11 {
	public static void main(String [] args){
		int Grid [][] = {
		{8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,8},
		{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
		{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
		{52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
		{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
		{24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
		{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
		{67,26,20,68,02,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},
		{24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
		{21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
		{78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,9,53,56,92},
		{16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
		{86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
		{19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
		{04,52,8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
		{88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
		{04,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36},
		{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
		{20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
		{01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}
		};
		
		int Product = 0;
		int largest = 0;
		
		// Check horizontally
		for(int i = 0; i < 20; i++){
			for(int j = 0; j < 17; j++){
				Product = Grid[i][j] * Grid[i][j + 1] * Grid[i][j + 2] * Grid[i][j + 3];
				if(Product > largest){
					largest = Product;
				}
			}	
		}
		
		// Check vertically
		for(int i = 0; i < 17; i ++){
			for(int j = 0; j < 20; j++){
				Product = Grid[i][j] * Grid[i + 1][j] * Grid[i + 2][j] * Grid[i + 3][j];
				if(Product > largest){
					largest = Product;
				}
			}
		}
		
		// Check diagonally right
		for(int i = 0; i < 17; i++){
			for(int j = 0; j < 17; j++){
				Product = Grid[i][j] * Grid[i + 1][j + 1] * Grid[i + 2][j + 2] * Grid[i + 3][i + 3];
				if(Product > largest){
					largest = Product;
				}
			}
		}
		
		// Check diagonally left
		for(int i = 0; i < 17; i ++){
			for(int j = 3; j < 20; j ++){
				Product = Grid[i][j] * Grid[i + 1][j - 1] * Grid[i + 2][j  - 2] * Grid[i + 3][j - 3];
				if(Product > largest){
					largest = Product;
				}
			}
		}
		System.out.format("Max Product = %d", + largest);
	}
}

Project Euler – Problem # 10 – Solved with Java & Python

Calculate the sum of all the primes below two million.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

One Possible Solution: Java

public class Problem_10 {
	public static void main(String [] args){
		// create Problem_10 object
		Problem_10 prob_10Obj = new Problem_10();
		
		// answer will be a long
		long Sum = 0;
		
		// start the counter at 1 and increase by 2 (all odd numbers)
		int counter = 1;
		
		// while counter is less than two million
		while (counter < 2000000) {
			
			// checks to see if counter is a prime number - if true - add to Sum
			if (prob_10Obj.isPrime(counter)) {
				Sum += counter;
			}
			// increase counter by 2 -> 1, 3, 5, 7, 9, 11, etc.
			counter += 2;
		}
		// add 2 to the Sum - our counter does not count the first prime number -> 2.
		System.out.println(Sum + 2); 
	}

	public boolean isPrime(int n)
	    {
		if (n == 1){
			return false;
		}
	    int k = (int) Math.sqrt(n);
	        for (int i = 2; i <= k; i++)
	        {
	            if (n % i == 0)
	                return false;
	        }
	        return true;
	    }

}

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

def primes(n):
    """Prime number generator up to n - (generates a list)"""
    ## {{{ http://code.activestate.com/recipes/366178/ (r5)
    if n == 2: return [2]
    elif n < 2: return []
    s = range(3, n + 1, 2)
    mroot = n ** 0.5
    half = (n + 1) / 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3) / 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2]+[x for x in s if x]

   ## end of http://code.activestate.com/recipes/366178/ }}}

def main():
    """Main Program"""
    print "Sum of all the primes below two million = %d" % sum(primes(2000000))

if __name__ == '__main__':
    main()

Project Euler – Problem # 9 – Solved with Java & Python

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

**********

The wikipedia page on Pythagorean triple is helpful in solving this problem. Particularly the part about
Euclid’s formula: a = m² – n², b = 2mn, c = m² + n².

Helpful link:

Pythagorean triple – http://en.wikipedia.org/wiki/Pythagorean_triple

One Possible Solution: Java

public class Problem_09 {
	public static void main(String [] args){
		for (int n = 1; n < 500; n++) {
			for (int m = (n + 1); m < 500; m ++) {
				int a = (m * m) - (n * n);
				int b = 2 * m * n;
				int c = (m * m) + (n * n);
				if (a + b + c == 1000) {
					int product = a * b * c;
					System.out.format("a = %d" + "b = %d" + "c = %d" + newline, a, b, c);
					System.out.format("Product = %d" + newline, product);
				}
				
			}	
		}	
	}
	public static String newline = System.getProperty("line.separator");
}

One Possible Solution: Python

import math
    
def main():
    """Main program"""
    for n in xrange(1, 500):
        for m in xrange(n + 1, 500):
            a = int(math.pow(m, 2) - math.pow(n, 2))
            b = 2 * m * n
            c = int(math.pow(m, 2) + math.pow(n, 2))
            if a + b + c == 1000:
                product = a * b * c
                print "a = %d, b = %d, c = %d" % (a, b, c)
    print "Product = %d" % (product)

if __name__ == '__main__':
    main()

Project Euler – Problem # 7 – Solved with Java & Python

Find the 10001st prime.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

One Possible Solution: Java

public class Problem_07 {
	public static void main(String args[])
	{
		Problem_07 prob_07Obj = new Problem_07();
		int Switch = 1;
		int counter = 1;
		int primes = 0;
		while(Switch == 1){
			if (prob_07Obj.isPrime(counter)){
				primes += 1;
				counter += 2;
			} else
			{
				counter += 2;
			}
			if (primes == 10001){
				System.out.println(counter - 2);
				Switch = 0;
			}
		}
		
	}
	public boolean isPrime(int n)
    {
    int k = (int) Math.sqrt(n);
            for (int i = 2; i <= k; i++)
            {
                    if (n % i == 0)
                            return false;
            }
            return true;
    }
}

One Possible Solution: Python

# Python version 2.7.2
# Platform = win32

def isprime(n):
    """Checks number (n) for primality, and returns
    True of False."""
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2:
        return True
    if not n & 1:
        return False
    for x in range(3, int(n ** 0.5) + 1, 2):
        if n % x == 0:
            return False
    return True 

def main():
    """this example takes the numbers 1, 3, 5, 7, 9, etc., and
    checks for primality."""
    Switch = 1
    number = 1
    primes = 1 # start with 1 since we do not count 2, which is a prime
    while Switch == 1:
        if isprime(number):
            primes += 1 
        if primes == 10001: # Stop at 10001, and print that number
            print number
            Switch = 0
        number += 2

if __name__ == '__main__':
    main()

Project Euler – Problem # 6 – Solved with Java & Python

What is the difference between the sum of the squares and the square of the sums?

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

One Possible Solution: Java

public class Problem_06 {
	public static void main(String args[]){
		int sum_of_squares = 0;
		int square_of_sum = 0;
		int Sum = 0;
		for(int i = 1; i < 101; i++){
			int square = (int)Math.pow(i, 2);
			sum_of_squares += square;
			Sum += i;
		}
		square_of_sum = (int)Math.pow(Sum, 2);
		int Difference = square_of_sum - sum_of_squares;
		System.out.println("sum_of_squares = " + sum_of_squares);
		System.out.println("square_of_sum = " + square_of_sum);
		System.out.println("Difference is = " + Difference);
	}

}

One Possible Solution: Python

# Python version: 2.7.2
# Platform = win32

def main():
    """Finds the difference between the sum of the
    squares of the first one hundred natural numbers
    and the square of the sum."""
    sum_of_squares = 0
    square_of_sum = 0
    Sum = 0
    for i in range(1, 101):
        square = i ** 2
        sum_of_squares += square
        Sum += i
    square_of_sum = Sum ** 2
    print "sum_of_squares = ", sum_of_squares
    print "square_of_sum = ", square_of_sum
    Difference = square_of_sum - sum_of_squares
    print "Difference = ", Difference

if __name__ == '__main__':
    main()

Project Euler – Problem # 5 – Solved with Java & Python

What is the smallest number divisible by each of the numbers 1 to 20?

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?

**********

“”"Main program – since we know that 2520 is evenly divisible by
the first 10 integers, we know that the number in question is a
multiple of 2520. So we start with 2520 and increment by that much
until we find the smallest number that is evenly divisible by the
first 20 integers (1-20)”"”

One Possible Solution: Java

public class Problem_5 {
	public static void main(String args[]){
		Problem_5 prob_5Obj = new Problem_5();
		int n = 2520;
		int Switch = 1;
		while (Switch == 1){
			Integer smallest = prob_5Obj.evenlyDivisible(n);
			if(smallest != 1){
				System.out.println(smallest);
				Switch = 0;
			}else{
				n += 2520;
			}
		}
	}
	
	public Integer evenlyDivisible(int n)
	{
		int counter = 0;
		for (int i = 1; i < 21; i++)
		{
			if(n % i == 0)
			{
				counter = counter + 1;
				if (counter == 20){
					return n;
				}
				else{
					continue;
				}
			}
			else{
				return 1;
			}
		}
		return 1;
	}
}

One Possible Solution: Python

# Python Version = 2.7.2
# Platform = win32
# Run time =  0.442848859867

import time

def evenlyDivisible(n):
    """Checks if number (n) is evenly divisible by the numbers 1 -20."""
    counter = 0
    for i in range(1, 21):
        if n % i == 0:
            counter = counter + 1
            if counter == 20:
                return n
        else:
            return 1

def main():
    """Main program - since we know that 2520 is evenly divisible by
    the first 10 integers, we know that the number in question is a
    multiple of 2520. So we start with 2520 and increment by that much
    until we find the smallest number that is evenly divisible by the
    first 20 integers (1-20)"""
    start_time = time.clock()
    n = 2520
    switch = 1
    while switch == 1:
        smallest = evenlyDivisible(n)
        if smallest != 1:
            print smallest
            switch = 0
        else:
            n += 2520
    run_time = time.clock() - start_time
    print "Run time = ", run_time
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 4 – Solved with Java & Python

Find the largest palindrome made from the product of two 3-digit numbers.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

**********

The way to reverse a sting in Python is a lot shorter than the way to do it in Java. y = x[::-1] as opposed to the reverse method in the Java program.

One Possible Solution: Java

public class Problem_4 {
	public static void main(String args[]){
		Problem_4 prob_4Obj = new Problem_4();
		int largest = 0;
		for (int i = 100; i < 1000; i++){
			for (int r = 100; r < 1000; r++){
				String x = Integer.toString(i * r);
				String y = prob_4Obj.reverse(x);
				int xx = Integer.parseInt((x));
				if (x.equals(y)) {
					if (xx > largest){
						largest = (xx);
					}
				}
					
				}
			}
	System.out.println(largest);	
	}
		
// http://www.vbforums.com/showthread.php?t=320907
	 public String reverse(String arg)
	 {
		String tmp = null;
		if (arg.length() == 1)
		{
			return arg;
		}
		
		else
		{
			String lastChar = arg.substring(arg.length() -1, arg.length());
			
			String remainingString = arg.substring(0, arg.length() -1);
	
			tmp = lastChar + reverse(remainingString);
			return tmp;
			
			
		}
	  }
// http://www.vbforums.com/showthread.php?t=320907
}

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

def findLargest():
    largest = 0
    for i in range (100, 999):
        for r in range(100, 999):
            x = str(i * r)
            y = x[::-1]
            if x == y:
                x = int(x)
                if x > largest:
                    largest = (x)
    return largest

def main():
    print findLargest()
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 3 – Solved with Java & Python

Find the largest prime factor of a composite number.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

**********

The question is: “How many prime numbers do we need to try?” I used the square root of n 600851475143. That would be 775146.099225. The algorithm to find the prime number list came from a third party for both the python solution and the java solution. Once we have the list of primes, we can apply the algorithm for finding the prime factors. The largest number in the Factors list is the answer to problem 3.

I have been learning Java from internet tutorials. If you see some code that can be improved on, feel free to leave a comment.

Helpful Links:

• Prime Factor – http://en.wikipedia.org/wiki/Prime_factor
• Prime factorization algorithm – http://www.indopedia.org/index.php?title=Prime_factorization_algorithm
• A fast prime number list generator for python – http://code.activestate.com/recipes/366178/
• A java prime number list generator – http://techdive.in/java/java-prime-number

One Possible Soultion: Java

import java.util.ArrayList;
import java.util.List;

public class Problem_3 {
	public static void main(String args[])
	{
		Problem_3 prob_3Obj = new Problem_3(); // Create Problem_3 object
		long number = 600851475143L; // Large composite number
		double sqrtNumber = Math.sqrt(number) + 1; // Find the sqrt of number
		int sN = (int)sqrtNumber; // Make the sqrt an integer
		List<Integer> primes = prob_3Obj.getListOfPrimes(sN); // Generates a list of primes up to sqrt
		List<Integer> Factors = new ArrayList<Integer>(); // Create a list for the prime factors
		for(int i = 0; i < primes.size(); i++) // For loop up to the size of primes list
		{
			int prime = primes.get(i); // Gets the (i)th element in the primes list
			if(prime == 1) // 1 is not a prime
			{
				continue;
			}
			int s = 1; // Counter for while loop
			while(s == 1)
			{
				if(number % prime == 0) // If number modulus prime is equal 0
				{
					Factors.add(prime); // Add that prime to the prime factors list
					number = number / prime; // Find the next number according to the algorithm
				} else 
				{
					s = 0; // if we are done with that prime, breaks the while loop
				}
				
			}
		}
		System.out.println(Factors); // Prints out the prime factors of number
	}
	
// Start: http://techdive.in/java/java-prime-number
// Returns 1 as a prime - accounted for that in the main method
	
		public boolean isPrime(int n)
        {
        int k = (int) Math.sqrt(n);
                for (int i = 2; i <= k; i++)
                {
                        if (n % i == 0)
                                return false;
                }
                return true;
        }

        public List<Integer> getListOfPrimes(int end)
        {
                List<Integer> lstInt = new ArrayList<Integer>();

                lstInt.add(1);
                lstInt.add(2);
                boolean flag = true;

                for (int i = 3; i < end; i++)
                {
                        flag = true;
                        int sqI = (int)Math.sqrt(i);
                        for (int j = 1; j < lstInt.size(); j++)
                        {
                                if (i % lstInt.get(j) == 0)
                                {
                                        flag = false;
                                        break;
                                }

                                if (sqI < lstInt.get(j))
                                {
                                        break;
                                }
                        }
                        if (flag == true)
                        {
                                lstInt.add(i);
                        }
                }
                return lstInt;
        }
// End: http://techdive.in/java/java-prime-number
	
	}

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

def primes(n):
    """Prime number generator up to n - (generates a list)"""
    ## {{{ http://code.activestate.com/recipes/366178/ (r5)
    if n == 2: return [2]
    elif n < 2: return []
    s = range(3, n + 1, 2)
    mroot = n ** 0.5
    half = (n + 1) / 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3) / 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2]+[x for x in s if x]

   ## end of http://code.activestate.com/recipes/366178/ }}}

def main():
    """Main Program - Integer factorization"""
    number = 600851475143
    primeList = primes(int(math.sqrt(number)))
    Factors = []
    for prime in primeList:
        s = 1
        while s == 1:
            if number % prime == 0:
                Factors.append(prime)
                number = number / prime
            else:
                s = 0
    print Factors
           
if __name__ == '__main__':
    import math
    main()

Project Euler – Problem # 2 – Solved with Java & Python

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.

One Possible Solution: Java

public class Problem2 {
	public static void main(String args[]){
		int sum = 0;
		int a = 0;
		int b = 1;
		int c = a + b;
		while (c < 4000000){
			if (c % 2 == 0){
				sum = sum + c;
			}
			a = b;
			b = c;
			c = a + b;
		}
		System.out.println(sum);
	}

}

One Possible Soulution: Python

# Python version = 2.7.2
# Platform = win32

def fib(n):
    """Determines the sum of the even numbers in the fibonacci sequence
    up to value n"""
    thesum = 0
    a, b = 0, 1
    while a < n:
        if a % 2 == 0:
            thesum = (thesum + (a))
        a, b = b, a + b
    return thesum

def main():
    """The main program - calls the fib function and prints the value
    returned from the function --> x"""
    x = fib(4000000)
    print x
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 1 – Solved with Java & Python

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.

**********

I have been learning Java from internet tutorials. If you see some code that can be improved on, feel free to leave a comment.

One Possible Solution: Java

public class Problem1 {
	public static void main(String[] args){
		int sum = 0;
		for(int counter = 1; counter < 1000; counter++){
			if(counter % 3 == 0 || counter % 5 == 0){
				sum = sum + counter;
			}else{
				continue;
			}
		}
		System.out.println(sum);
	}

}

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

sum = 0
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        sum = sum + i
print "Answer = ", sum