Project Euler – Problem # 23 – Solved with Java

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

One Possible Solution: Java

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Collection;

public class Problem_23 {
	public static void main(String args[]){
		
		long start = System.currentTimeMillis();
		
		List<Integer> aN = new ArrayList<Integer>(Abundant_numbers());
		Collections.sort(aN);
		
		Collection<Integer> abundant_sums = new ArrayList<Integer>(Abundant_sums(aN));
		Collection<Integer> all_integers = new ArrayList<Integer>(All_integers());
		
		all_integers.removeAll(abundant_sums);
		
		System.out.println(sum_Answer(all_integers));
		
		long stop = System.currentTimeMillis();
		System.out.println("Run time = " + (stop - start) + " milliseconds");
	}
	
	public static Integer sum_Answer(Collection<Integer> list) {
	     Integer sum= 0;
	     if(list == null){
	    	 return 0;
	     }
	     for (Integer i:list)
	         sum = sum + i;
	     return sum;
	}
	
	public static Set<Integer> All_integers(){
		Set<Integer> All_integers = new HashSet<Integer>();
		for(int i = 1; i < 28123; i ++){
			All_integers.add(i);
		}
		return All_integers;
	}
	
	
	public static Set<Integer> Abundant_numbers(){
		Set<Integer> Abundant_numbers = new HashSet<Integer>();
		for(int i = 1; i <= 28123; i ++){
			List<Integer> x = proper_divisors(i);
			if(sum(x) > i){
				Abundant_numbers.add(i);
			}
		}
		return Abundant_numbers;
	}
	
	public static Set<Integer> Abundant_sums(List<Integer> aN){
		Set<Integer> Abundant_sums = new HashSet<Integer>();
		for (int i = 0; i < aN.size(); i++) {
			Integer x = aN.get(i);
			for(int j = 0; j < aN.size(); j++){
				int y = aN.get(j);
				int zzz = x + y;
				if(zzz < 28123){
					Abundant_sums.add(zzz);
				}
			}
		}
		return Abundant_sums;
	}

	public static List<Integer> proper_divisors(int number){
		List<Integer> L = new ArrayList<Integer>();
		if(number == 1){
			L = null;
			return L;
		}
		if(number == 2){
			L.add(1);
			return L;
		}
		for(int i = 1; i <= ((number / 2) + 1); i ++){
			if(number % i == 0){
				L.add(i);
			}
		}
		return L;
	}
	
	public static Integer sum(List<Integer> list) {
	     Integer sum= 0;
	     if(list == null){
	    	 return 0;
	     }
	     for (Integer i:list)
	         sum = sum + i;
	     return sum;
	}
}
Advertisements

Project Euler – Problem # 22 – Solved with Go

What is the total of all the name scores in the file of first names?

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 * 53 = 49714.

What is the total of all the name scores in the file?

**********

To solve this problem, I had help with reading the file and making it ready for the program from a stackoverflow question I asked – http://stackoverflow.com/questions/11462879/strings-split-in-golang

One Possible Solution: Go

package main

import "fmt"
import "io/ioutil"
import "strings"
import "sort"

func main() {
	fData, err := ioutil.ReadFile("names.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

	names := strings.Split(strbuffer, ",")

	for i, val := range names {
		names[i] = strings.Trim(val, "\"")
	}

	sort.Strings(names)

	total := 0

	for i := range names {
		name := names[i]
		letters := strings.Split(name, "")

		x2 := 0
		y := 0

		for m := range letters {
			letter := letters[m]
			x1 := letter_counter(letter)
			x2 += x1
		}
		y = x2 * (i + 1)
		total += y

	}
	fmt.Println(total)

}

func letter_counter(letter string) (lc int) {
	letv := make(map[string]int)

	letv["A"] = 1
	letv["B"] = 2
	letv["C"] = 3
	letv["D"] = 4
	letv["E"] = 5
	letv["F"] = 6
	letv["G"] = 7
	letv["H"] = 8
	letv["I"] = 9
	letv["J"] = 10
	letv["K"] = 11
	letv["L"] = 12
	letv["M"] = 13
	letv["N"] = 14
	letv["O"] = 15
	letv["P"] = 16
	letv["Q"] = 17
	letv["R"] = 18
	letv["S"] = 19
	letv["T"] = 20
	letv["U"] = 21
	letv["V"] = 22
	letv["W"] = 23
	letv["X"] = 24
	letv["Y"] = 25
	letv["Z"] = 26

	lc = letv[letter]

	return lc
}

Project Euler – Problem # 22 – Solved with Java

What is the total of all the name scores in the file of first names?

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 * 53 = 49714.

What is the total of all the name scores in the file?

**********

To solve this problem, I had help with reading the file and making it ready for the program from a stackoverflow question/answerhttp://stackoverflow.com/questions/8672712/optimizing-project-euler-22

One Possible Solution: Java

import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.*;
import java.io.File;

public class Problem_22 {
	public static void main(String args[]){
		try
	    {
	       Scanner in = new Scanner(new File("names.txt")).useDelimiter("[\",]+");
	       ArrayList<String> names = new ArrayList<String>();
	       while (in.hasNext())
	       {
	    	   names.add(in.next());
	       }
	       Collections.sort(names);
	       
	       int z = 0;
	       for(int i = 0; i <= names.size() - 1; i ++){
	    	   int x2 = 0;
	    	   int y = 0;
	    	   String name = names.get(i);
	    	   for(int m = 0; m <= name.length() - 1; m ++){
	    		   int x1 = letter_counter(name.charAt(m));
	    		   x2 += x1;
	    	   }
	    	   y = x2 * (i + 1);
	    	   z += y;
			}
	       System.out.format("Total = %d%n", z);
	    }
		catch( FileNotFoundException filenotfoundexcption )
		{
		   System.out.println( "names.txt, does not exist" );
		}
		 
		catch( IOException ioexception )
		{
		   ioexception.printStackTrace( );
		}
	}
	
	public static Integer letter_counter(char letter_u)
	{
		String letter = Character.toString(letter_u);
		Map<String, Integer> letv = new HashMap<String, Integer>();
		letv.put("A", 1);
		letv.put("B", 2);
		letv.put("C", 3);
		letv.put("D", 4);
		letv.put("E", 5);
		letv.put("F", 6);
		letv.put("G", 7);
		letv.put("H", 8);
		letv.put("I", 9);
		letv.put("J", 10);
		letv.put("K", 11);
		letv.put("L", 12);
		letv.put("M", 13);
		letv.put("N", 14);
		letv.put("O", 15);
		letv.put("P", 16);
		letv.put("Q", 17);
		letv.put("R", 18);
		letv.put("S", 19);
		letv.put("T", 20);
		letv.put("U", 21);
		letv.put("V", 22);
		letv.put("W", 23);
		letv.put("X", 24);
		letv.put("Y", 25);
		letv.put("Z", 26);
		
		int lc = letv.get(letter);
		return lc;
	}
}

Project Euler – Problem # 21 – Solved with Go

Problem:

Evaluate the sum of all amicable pairs under 10000.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

One Possible Solution: Go

package main

import "fmt"

func main() {
	fmt.Println("Hello, playground")
	tally := 0
	for y := 1; y <= 10000; y++ {
		x := factors(y)
		x1 := get_total(x)
		x3 := factors(x1)
		x4 := get_total(x3)
		if y == x4 && y != x1 {
			tally += y
		}
	}
	fmt.Println(tally)
}

func get_total(factors []int) (number int) {
	total := 0
	for i := 0; i < len(factors); i++ {
		total += factors[i]
	}
	return total
}

func factors(number int) (factors []int) {
	L := make([]int, number)
	counter := 0
	for i := 1; i < ((number / 2) + 1); i++ {
		if number%i == 0 {
			L[counter] = i
			counter += 1
		}
	}
	return L[:counter]

}

Project Euler – Problem # 21 – Solved with Java

Problem:

Evaluate the sum of all amicable pairs under 10000.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

One Possible Solution: Java

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

public class Problem_21 {
	public static void main(String args[]){
		int tally = 0;
		for(int y = 1; y <= 10000; y ++){
			List<Integer> x = factors(y);
			int x1 = get_total(x);
			List<Integer> x3 = factors(x1);
			int x4 = get_total(x3);
			if((y == x4) && (y != x1)){
				tally += y;
			}
		}
		System.out.format("Tally = %d%n", tally);
	}
	
	public static List<Integer> factors(int number){
		List<Integer> L = new ArrayList<Integer>();
		for(int i = 1; i <= ((number / 2) + 1); i ++){
			if(number % i == 0){
				L.add(i);
			}
		}
		return L;
	}
	
	public static Integer get_total(List<Integer> list) {
		     Integer sum= 0; 
		     for (Integer i:list)
		         sum = sum + i;
		     return sum;
	}
}

Project Euler – Problem # 20 – Solved with Go

Find the sum of digits in 100!

n! means n * (n – 1) * … * 3 * 2 * 1

For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

['9332621544394415268169923885626670049071596826438162146859296389521759999
32299156089414639761565182862536979208272237582511852109168640000000000000
00000000000']

So 100! gives you a long number, what the question is asking is to sum each digit in that long number.

package main

import "fmt"
import "math/big"
import "strings"
import "strconv"

func main() {

	n := big.NewInt(100)

	result := factorial(n)
	string_result := result.String()		// convert result to a string
	numbers := strings.Split(string_result, "")	// split the string

	Answer := 0
	for _, number := range numbers {	// enumerate thru the string of numbers
		x, _ := strconv.Atoi(number)	// convert string to an integer
		Answer += x			// add the individual integer to the Answer
	}

	fmt.Println(Answer)
}

func factorial(n *big.Int) (result *big.Int) {
	// This function finds the factorial of a number. For example: 5! = 5 * 4 * 3 * 2 * 1 = 120

	b := big.NewInt(0)
	c := big.NewInt(1)

	if n.Cmp(b) == -1 {
		result = big.NewInt(1)
	}
	if n.Cmp(b) == 0 {
		result = big.NewInt(1)
	} else {
		result = new(big.Int)
		result.Set(n)
		result.Mul(result, factorial(n.Sub(n, c)))
	}
	return
}

Project Euler – Problem # 20 – Solved with Java

Find the sum of digits in 100!

n! means n * (n – 1) * … * 3 * 2 * 1

For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

['9332621544394415268169923885626670049071596826438162146859296389521759999
32299156089414639761565182862536979208272237582511852109168640000000000000
00000000000']

So 100! gives you a long number, what the question is asking is to sum each digit in that long number.

import java.math.BigInteger;

public class Problem_20 {
	public static void main(String args[]){
		BigInteger n = BigInteger.valueOf(100);
		int Sum = 0;
		BigInteger result = (factorial(n));
		String string_result = String.valueOf(result);
		
		for(int i = 0; i <= string_result.length() - 1; i ++){
			Character c = new Character(string_result.charAt(i));
		    String s = c.toString();
		    int n1 = Integer.parseInt(s);
			Sum += n1;
		}
		System.out.format("Sum = %d%n", Sum);
	}
	public static BigInteger factorial( BigInteger n )
	{
			if ( n.compareTo(BigInteger.ZERO) <= 0 ) { // base case
				return BigInteger.ONE;
			}
			else  {  // general case
				return ( n.multiply(factorial ( n.subtract(BigInteger.ONE)) ) );
			}
	}
}

Project Euler – Problem # 19 – Solved with Go

How many Sundays fell on the first of the month during the twentieth century?

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

Problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

**********

To solve this problem, I just ported my python solution to Go.

One Possible Solution: Go

package main

import "fmt"

func main() {
	fmt.Println("Hello, playground")

	L := make(map[int]string)

	L[1] = "Sun"
	L[2] = "Mon"
	L[3] = "Tue"
	L[4] = "Wed"
	L[5] = "Thurs"
	L[6] = "Fri"
	L[7] = "Sat"

	// Start at Monday, 1st, 1900
	counter := 1
	tally := 0

	for yr := 1900; yr < 2001; yr++ {	// Year
		fmt.Printf("Year = %d\n", yr)

		for month := 1; month < 13; month++ {	//  Month
			y := find_days(month, yr)
			for month_days := 1; month_days <= y; month_days++ {	// Number of month days
				// Start at Monday, 1st, 1900
				counter += 1
				if month_days == 1 && L[counter] == "Sun" {
					fmt.Printf("month_days = %d L[counter] = %s\n", month_days, L[counter])
					tally += 1
				}
				if counter >= 7 {	// Days of the week
					counter = 0
				}
			}
		}
		fmt.Printf("\n")
	}
	// subtract 2 for the year 1900
	fmt.Println("Tally = ", tally-2)
}

func find_days(month int, yr int) int {
	d := 0
	if (month == 1) || (month == 3) || (month == 5) || (month == 7) || (month == 8) || (month == 10) || (month == 12) {
		d = 31
	} else if (month == 4) || (month == 6) || (month == 9) || (month == 11) {
		d = 30
	} else if month == 2 {
		if yr%4 == 0 {
			if yr%100 == 0 {
				if yr%400 == 0 {
					d = 29
				} else {
					d = 28
				}
			} else {
				d = 29
			}
		} else {
			d = 28
		}
	} else {
		fmt.Println("There has been an error")
	}
	return d
}

Project Euler – Problem # 19 – Solved with Java

How many Sundays fell on the first of the month during the twentieth century?

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

Problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

**********

To solve this problem, I just ported my python solution to java.

One Possible Solution: Java

import java.util.HashMap;
import java.util.Map;


public class Problem_19 {
	public static void main(String args[]){
		Map<Integer, String> L = new HashMap<Integer, String>();
		L.put(1, "Sun");
		L.put(2, "Mon");
		L.put(3, "Tue");
		L.put(4, "Wed");
		L.put(5, "Thurs");
		L.put(6, "Fri");
		L.put(7, "Sat");
		
		// Start at Monday, 1st, 1900
		int counter = 1;
		int tally = 0;
		
		// Year
		for (int yr = 1900; yr < 2001; yr ++)
		{
			System.out.println("Year = " + yr);
			// Month
			for (int month = 1; month < 13; month ++)
			{
				int y = find_days(month, yr);
				for (int month_days = 1; month_days <= y; month_days ++) // Number of month days
				{
					// Start at Monday, 1st, 1900
					counter += 1;
					if ((month_days == 1) && (L.get(counter) == "Sun"))
					{
						System.out.println("month_days = " + month_days);
						tally += 1;
					}
					// Days of the week
					if (counter >= 7)
					{
						counter = 0;
					}
				}
			}
			System.out.println();
		}
		// subtract 2 for the year 1900 - start counting at 1901
		System.out.println("tally = " + (tally - 2));
	}
	public static int find_days(int month, int yr){
		int d = 0;
		if ((month == 1) || (month == 3) || (month == 5) || (month == 7) ||
		(month == 8) || (month == 10) || (month == 12))
		{
			d = 31;
		}
		else if ((month == 4) || (month == 6) || (month == 9) || (month == 11))
		{
			d = 30;
		}
		else if ((month == 2))
		{
			if (yr % 4 == 0)
			{
				if (yr % 100 == 0)
				{
					if (yr % 400 == 0)
					{
						d = 29;
					}
					else
					{
						d = 28;
					}
				} 
				else
				{
					d = 29;
				}
			}
			else
			{
				d = 28;
			}
		}
		else
		{
			System.out.println("There has been an error");
		}
		return d;
	}
}

Project Euler – Problem # 17 – Solved with Go

How many letters would be needed to write all the numbers in words from 1 to 1000?

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

**********

I basically just ported my python solution to Go.

One Possible Solution: Go

package main

import "fmt"
import "strconv"

func main() {
	fmt.Println("Hello, playground")

	number := make(map[int]string)

	number[1] = "one"
	number[2] = "two"
	number[3] = "three"
	number[4] = "four"
	number[5] = "five"
	number[6] = "six"
	number[7] = "seven"
	number[8] = "eight"
	number[9] = "nine"
	number[10] = "ten"
	number[11] = "eleven"
	number[12] = "twelve"
	number[13] = "thirteen"
	number[14] = "fourteen"
	number[15] = "fifteen"
	number[16] = "sixteen"
	number[17] = "seventeen"
	number[18] = "eighteen"
	number[19] = "nineteen"
	number[20] = "twenty"
	number[30] = "thirty"
	number[40] = "forty"
	number[50] = "fifty"
	number[60] = "sixty"
	number[70] = "seventy"
	number[80] = "eighty"
	number[90] = "ninety"
	number[100] = "hundred"
	number[1000] = "thousand"

	tally := 0
	k := 0

	for n := 1; n <= 1000; n++ {
		x := strconv.FormatInt(int64(n), 10)
		if len(x) == 1 {
			// The first 9 numbers are 1 digit -- in the dictionary
			k = len(number[n])
			fmt.Printf("n = %d k = %d\n", n, k)
		} else if len(x) == 2 {
			x1 := x[0:1]
			x2 := x[1:2]
			x2_i, _ := strconv.Atoi(x2)
			if n < 20 {
				k = len(number[n])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else {
				if x2 == "0" {
					// The numbers under 100 and greater than 19 -- in the 
					// dictionary ending in '0', (20, 30, 40 ....)
					k = len(number[n])
					fmt.Printf("n = %d k = %d\n", n, k)
				} else {
					// The other numbers under 100 greater than 19
					x1a := x1 + "0"
					x1a_i, _ := strconv.Atoi(x1a)
					k = len(number[x1a_i]) + len(number[x2_i])
					fmt.Printf("n = %d k = %d\n", n, k)
				}
			}
		} else if len(x) == 3 {
			// add 3 for 'and' i.e. -- two-hundred and ten
			x1 := x[0:1]
			x2 := x[1:2]
			x3 := x[2:3]
			x1a := x2 + "0"
			x1aa := x2 + x3

			x1_i, _ := strconv.Atoi(x1)
			x3_i, _ := strconv.Atoi(x3)
			x1a_i, _ := strconv.Atoi(x1a)
			x1aa_i, _ := strconv.Atoi(x1aa)

			if x1 == "1" && x2 == "0" && x3 == "0" {
				// 100 -- in the dictionary
				k = len(number[1]) + len(number[100])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "0" && x3 == "0" {
				// Consider 200, 300, 400, 500, 600, 700, 800, and 900
				k = len(number[x1_i]) + len(number[100])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "0" && x3 != "0" {
				// Consider 101, 102 ... 109, 201, 202, ... 209 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x3_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 != "0" && x3 == "0" {
				// Consider 110, 120, ... 190, 210, 220, ... 290 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1a_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "1" && x3 != "0" {
				// Consider the teens 111, 112, ... 119, 211, 212, ... 219 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1aa_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else {
				// Consider all the other numbers
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1a_i]) + len(number[x3_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			}

		} else {
			// 1000 -- two parts (one and thousand) -- in the dictionary
			k = len(number[1]) + len(number[1000])
			fmt.Printf("n = %d k = %d\n", n, k)
		}
		tally += k

	}
	fmt.Println(tally)
}