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 # 25 – Solved with Python

It doesn’t take long for the Fibonacci sequence to get really large. This program asks for a stopping number, then loops through those numbers until it gets one of length 1000 digits or more. At only 4782 the Fibonacci number problem is solved.

Problem:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

  • F1 = 1
  • F2 = 1
  • F3 = 2
  • F4 = 3
  • F5 = 5
  • F6 = 8
  • F7 = 13
  • F8 = 21
  • F9 = 34
  • F10 = 55
  • F11 = 89
  • F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

One Possible Solution:

def find_fibonacci(n):
    """Find fibonacci"""
    a, b = 0, 1
    for i in range(0, n):
        x = str(a)
        if len(x) == 1000:
            print a
            print "F(n) = ", i
            break
        a, b, = b, a + b

def main():
    """Main program"""
    n = input("\nHow many numbers of the sequence would you like? ")
    find_fibonacci(n)
    
if __name__ == '__main__':
    main()

Project Euler

Project Euler – Problem # 24 – Solved with Python

This problem was made easy with the permutations fucntion.

Problem:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

One Possible Solution:

import itertools
x = itertools.permutations('0123456789', 10)
counter = 0
for i in x:
    counter += 1
    if counter == 1000000:
        print i
    else:
        pass

Project Euler – Problem # 23 – Solved with Python

I first approached this problem with lists…. The test programs were running 15 + minutes , so I tried dictionaries, this gave too much data representation. So I settled with python sets. You can add to a set to build it, they are unique, (don’t have to worry about duplicates), and best of all they can be compared to one another. It worked really smoothly with sets. Note: program still takes about 55 seconds to run.

Problem:

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:

import time

def factor(number):
    """Factor a number"""
    L = []
    for i in range(1, ((number / 2) + 1)):
        if number % i == 0:
            L.append(i)
    return L

def sum_factors(x):
    """Sum factors"""
    return sum(x)

def find_abundant_Set():
    """Find abundant Set"""
    abundant_Set = set()
    for m in range(0, 28123):
        x = factor(m)
        y = sum_factors(x)
        if m < y:
            abundant_Set.add(m)
        else:
            pass
    return set(sorted(abundant_Set))

def find_abundant_sums(xy):
    """Find abundant sums"""
    abundant_Set_a = set()
    for x in xy:
        for y in xy:
            zzz = x + y
            if zzz < 28123:
                abundant_Set_a.add(zzz)
            else:
                pass
    return set(sorted(abundant_Set_a))

def set_of_all_integers():
    """Set if all integers"""
    all_integers = set()
    for x in range(0, 28123):
        all_integers.add(x)
    return set(sorted(all_integers))
        
def find_missing_abundant_sums(yz, zz):
    """Find missing abundant sums"""
    all_positive_int = set()
    all_positive_int = zz - yz
    return set(all_positive_int)

def main():
    """Main program"""
    start_time = time.clock()
    xy = find_abundant_Set()
    yz = find_abundant_sums(xy)
    zz = set_of_all_integers()
    xz = find_missing_abundant_sums(yz, zz)
    tally = sum(xz)
    print "Tally = ", tally
    run_time = time.clock() - start_time
    print "Run time = ", run_time
            
if __name__ == '__main__':
    main()