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 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 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 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 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 Java

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 java.

One Possible Solution: Java

Project Euler – Problem # 16 – Solved with Java

What is the sum of the digits of the number 21000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

**********

Helpful Links:

One Possible Solution: Java

import java.math.BigInteger;


public class Problem_16 {
	public static void main(String args[])
	{
		BigInteger result = BigInteger.ZERO;
		BigInteger two = BigInteger.valueOf(2);
		BigInteger one_thousand = BigInteger.valueOf(1000);
		result = pow(two, one_thousand);
		String string_result = new String(result.toString());
		
		int Answer = 0;
		for (int i = 0; i < string_result.length(); i++)
		{
		    Character c = new Character(string_result.charAt(i));
		    String s = c.toString();
		    int n = Integer.parseInt(s);
		    Answer = Answer + n;
		}

		System.out.println(Answer);

	}
	
	public static BigInteger pow(BigInteger base, BigInteger exponent)
	{
		BigInteger result = BigInteger.ONE;
		while (exponent.signum() > 0)
		{
			if (exponent.testBit(0)) result = result.multiply(base);
		    base = base.multiply(base);
		    exponent = exponent.shiftRight(1);
		}
		  return result;
	}

}

Project Euler – Problem # 15 – Solved with Java

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

**********

After doing a bit of research on this problem, it seems as though a simple Combinations formula will provide the answer. We know that any path will have 40 moves (20 right + 20 down), so for C(n,r) – n will equal 40 and r (the number of right moves) will equal 20 – C(40,20). Then we just plug the numbers into the formula – the ! means ‘factorial’. I posted 2 versions of the solution: 1 without recursion – uses a for loop, and one with recursion – the factorial function calls itself.

                 n!
C(n,r) =   ———-
             r!*(n-r)!

The number of how many good routes we have can be found by finding how
many combinations of 20 R’s we can have in our 40 moves, so we want to
calculate:

                    40!
C(40,20) =   ———-
                20!*(40-20)!

Helpful Links:

One Possible Solution: Java – without recursion – (uses a for loop)

import java.math.BigInteger;

public class Problem_15 {
	public static void main(String args[]){
		int n = 40;		// The total number of moves for any one path (right + down)
		int r = 20;		// The total number of right moves for any one path
		
		System.out.println(factorial(n).divide(factorial(r).multiply(factorial(n - r))));
	}
	public static BigInteger factorial( int n1 )
    {
		BigInteger n = BigInteger.ONE;
		for (int i = 1; i <= n1; i ++) {
			n = n.multiply(BigInteger.valueOf(i));			
		}
		return n;
    }

}

One Possible Solution: Java – uses recursion (the factorial method calls itself)

import java.math.BigInteger;


public class Problem_15a {
	public static void main(String args[]){
		BigInteger n = BigInteger.valueOf(40);		// The total number of moves for any one path (right + down)
		BigInteger r = BigInteger.valueOf(20);		// The total number of right moves for any one path
		
		System.out.println(factorial(n).divide(factorial(r).multiply(factorial(n.subtract(r)))));
	}
	
	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 # 14 – Solved with Java

Problem:

The following iterative sequence is defined for the set of positive integers:

n –> n/2 (n is even)

n –> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.


public class Problem_14 {
	public static void main(String args[]){
		long start = System.currentTimeMillis();
		
		int largest = 0;
		int longest_sequence = 0;
		for(int n = 2; n < 1000001; n++){
			long Number = n;
			int counter = 1;
			while(Number > 1){
				if(Number % 2 == 0){
					Number = Number / 2;
				} else{
					Number = (Number * 3) + 1;
				}
				counter += 1;
			}
			
			if(counter > longest_sequence){
				longest_sequence = counter;
				largest = n;
			}
		}
	
		System.out.format("Answer = %d", largest);
		System.out.println();
		System.out.format("longest_sequence = %d ", longest_sequence);
		System.out.println();
		long stop = System.currentTimeMillis();
		System.out.println("Run time = " + (stop - start) + " milliseconds");
	}

}

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( );
		   }
	}

}