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

}
Advertisements

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

}

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,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

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 = m2 – n2, b = 2mn, c = m2 + n2.

Helpful link:

Pythagorean triplehttp://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 # 9 – Solved with Go

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,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

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 = m2 – n2, b = 2mn, c = m2 + n2.

Helpful link:

Pythagorean triplehttp://en.wikipedia.org/wiki/Pythagorean_triple

One Possible Solution: Go

package main

import "fmt"
import "math"

func main() {
	for n := 1; n < 500; n++ {
		for m := (n + 1); m < 500; m++ {
			a := int(math.Pow(float64(m), 2) - math.Pow(float64(n), 2))
			b := 2 * m * n
			c := int(math.Pow(float64(m), 2) + math.Pow(float64(n), 2))
			if a+b+c == 1000 {
				product := a * b * c
				fmt.Println(a, b, c)
				fmt.Println(product)
			}
		}

	}
}

Project Euler – Problem # 8 – Solved with Go

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

One Possible Solution: Go

package main

import "fmt"
import "strconv"

const fileIn = "73167176531330624919225119674426574742355349194934" +
	"96983520312774506326239578318016984801869478851843" +
	"85861560789112949495459501737958331952853208805511" +
	"12540698747158523863050715693290963295227443043557" +
	"66896648950445244523161731856403098711121722383113" +
	"62229893423380308135336276614282806444486645238749" +
	"30358907296290491560440772390713810515859307960866" +
	"70172427121883998797908792274921901699720888093776" +
	"65727333001053367881220235421809751254540594752243" +
	"52584907711670556013604839586446706324415722155397" +
	"53697817977846174064955149290862569321978468622482" +
	"83972241375657056057490261407972968652414535100474" +
	"82166370484403199890008895243450658541227588666881" +
	"16427171479924442928230863465674813919123162824586" +
	"17866458359124566529476545682848912883142607690042" +
	"24219022671055626321111109370544217506941658960408" +
	"07198403850962455444362981230987879927244284909188" +
	"84580156166097919133875499200524063689912560717606" +
	"05886116467109405077541002256983155200055935729725" +
	"71636269561882670428252483600823257530420752963450"

func main() {
	largest := 0
	for i := 0; i < (len(fileIn) - 4); i++ {
		fiveDigits := fileIn[i:(i + 5)]

		s1 := fiveDigits[0:1]
		s2 := fiveDigits[1:2]
		s3 := fiveDigits[2:3]
		s4 := fiveDigits[3:4]
		s5 := fiveDigits[4:5]

		x1, _ := strconv.Atoi(s1)
		x2, _ := strconv.Atoi(s2)
		x3, _ := strconv.Atoi(s3)
		x4, _ := strconv.Atoi(s4)
		x5, _ := strconv.Atoi(s5)

		product := x1 * x2 * x3 * x4 * x5

		if product > largest {
			largest = product
		}

	}
	fmt.Println("Greatest product is: ", largest)
}