Project Euler – Problem # 13 – Solved with Java

Find the first ten digits of the sum of one-hundred 50-digit numbers.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

One Possible Solution: Java

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigInteger;


public class Problem_13 {
	public static void main(String [] args) {
		try
	    {
	       FileReader fro = new FileReader( "one-hundred_50.txt" );
	       BufferedReader bro = new BufferedReader( fro );
	  
	       BigInteger tally = BigInteger.ZERO;
	     
	       String line;
	       while ((line = bro.readLine()) != null)   {
	           BigInteger bi = new BigInteger(line);
	           tally = tally.add(bi);
	       }
	       System.out.println("tally = " + tally);
	    }
		catch( FileNotFoundException filenotfoundexcption )
		   {
		     System.out.println( "one-hundred_50.txt, does not exist" );
		   }
		 
		catch( IOException ioexception )
		   {
		     ioexception.printStackTrace( );
		   }
	}

}
Advertisements

Project Euler – Problem # 13 – Solved with Go

Find the first ten digits of the sum of one-hundred 50-digit numbers.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

**********

I had to ask two questions on stackoverflow.com to help me solve this problem in Go. Question # 1 was about reading in the external file and getting it into a useable form (string). Question # 2 was about the “math/big” package. For numbers greater than 2147483647, the big package is needed.

One Possible Solution: Go

package main

import "fmt"
import "io/ioutil"
import "strings"
import "math/big"

func main() {
	fData, err := ioutil.ReadFile("one-hundred_50.txt")	// read in the external file
	if err != nil {
		fmt.Println("Err is ", err) 	// print any error
	}
	strbuffer := string(fData)	// convert read in file to a string
	lines := strings.Split(strbuffer, "\n") // split the string into lines
	tally := big.NewInt(0)		// declare and initialise big number tally
	for _, line := range lines {	// loop through each line in lines - 100 of them
		bi := big.NewInt(0)	// declare and  initialise big number bi
		bi.SetString(line, 10) 	// convert line to a big integer (base 10)
		tally.Add(tally, bi)   	// add bi to the tally
	}
	fmt.Println(tally) 	// print tally and use the first 10 digits for the answer
}

Project Euler – Problem # 12 – Solved with Go

What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

  • 1: 1
  • 3: 1,3
  • 6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

One Possible Solution: Go

package main

import "fmt"
import "math"

func main() {
	counter := 0
	TriangleNumber := 0
	Switch := 1
	for Switch >= 1 {
		counter++
		TriangleNumber += counter
		if factors(TriangleNumber) > 500 {
			fmt.Println(TriangleNumber)
			Switch = 0
		}
	}
}

func factors(n int) (facCount int) {
	facCounter := 0
	k := int(math.Sqrt(float64(n)))
	for i := 1; i < k+1; i++ {
		if n%i == 0 {
			facCounter++
		}
	}
	return facCounter * 2

}

Project Euler – Problem # 12 – Solved with Java

What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

  • 1: 1
  • 3: 1,3
  • 6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

One Possible Solution: Java


public class Problem_12 {
	public static void main(String [] args){
		int counter = 0;
		int TriangleNumber = 0;
		boolean Switch = true;
		while(Switch == true){
			counter ++;
			TriangleNumber += counter;
			if(Factors(TriangleNumber) > 500){
				System.out.println(TriangleNumber);
				Switch = false;
			}
		}
		
	}
	public static int Factors(int n){
		// Finds all the factors of a number (n)
		// and returns the number of factors.
		int counter = 0;
		int k = (int) Math.sqrt(n);
		for(int i = 1; i < k + 1; i ++){
			if(n % i == 0){
				counter ++;
			}
		}
		return 2 * counter;
	}

}

Project Euler – Problem # 12 – Solved with Python

What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

  • 1: 1
  • 3: 1,3
  • 6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

**********

Helpful links:

Help with finding all the factors of a number – http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32
# Run time =  16.4755609827 seconds

import math
import time

def factors(n):
    """Returns a set of all the factors of a triangle number (n)."""
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(math.sqrt(n)) + 1) if n % i == 0)))
    
def main():
    """Main program"""
    start_time = time.clock()
    counter = 0         # Initialise counter for natural numbers
    TriangleNumber = 0  # Initialise triangle number variable
    switch = True       # Switch for while loop
    while switch == True:
        counter += 1
        TriangleNumber += counter               # Get the current triangle number.
        if len(factors(TriangleNumber)) > 500:  # Find all the factors of TriangleNumber, 
            switch = False                      # if greater than 500 stop the while loop
    print(TriangleNumber)                       # and print the last triangle number.
    run_time = time.clock() - start_time
    print "Run time = ", run_time
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 11 – Solved with Go

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: Go

package main

import "fmt"

func main() {

	Grid := [20][20]int{
		{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},
	}

	Product := 0
	largest := 0

	// Check horizontally
	for i := 0; i < 20; i++ {
		for 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 i := 0; i < 17; i++ {
		for 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 i := 0; i < 17; i++ {
		for j := 0; j < 17; 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
			}
		}
	}

	// Check diagonally left
	for i := 0; i < 17; i++ {
		for 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
			}
		}
	}

	fmt.Println(largest)
}

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

Project Euler – Problem # 10 – Solved with Go

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.

**********

When running this program on http://play.golang.org/, I get the error message [process took too long]; however, when running it on my local machine I get the correct answer.

One Possible Solution: Go

package main

import "fmt"
import "math"

var Sum int64 = 0

func main() {
	
	counter := 1
	for counter < 2000000 {
		if isPrime(counter) {
			Sum += int64(counter)
		}
		counter += 2
	}
	fmt.Println(Sum + 2)

}

func Sqrt(x float64) float64 {
	x = math.Sqrt(x)
	return x
}

func isPrime(n int) (isP bool) {
	if n == 1 {
		return false
	}
	if n == 2 {
		return true
	}
	k := int(Sqrt(float64(n)))
	for i := 2; i <= k; i++ {
		if n%i == 0 {
			return false
		}

	}
	return true

}