Category Archives: Project Euler

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.

public class Problem23 {

	static List<Integer> abundant = new ArrayList<Integer>();
	static Set<Integer> sumList = new HashSet<Integer>();


	static long sum = 0;

	public static void main(String[] args) {
		for (int i = 1; i <= 28123; i++) {
			if (getSumOfDivisors(i) > i) {
				abundant.add(i);
			}
		}
		System.out.println("Total abundant numbers: " + abundant.size());
		for (int j = 0; j < abundant.size(); j++) {
			for (int k = 0; k < abundant.size(); k++) {
				int tempNum;
				if ((tempNum = abundant.get(j) + abundant.get(k)) < 28123) {
					sumList.add(tempNum);
				}
			}
		}
		System.out.println("Sum list generated: " + sumList.size());
		for (int i = 0; i < 28123; i++) {
			if (!sumList.contains(i)) {
				sum += i;
			}
		}
		System.out.println(sum);

	}

	public static int getSumOfDivisors(int number) {
		int sum = 0;
		for (int j = number / 2; j > 0; j--) {
			if (number % j == 0) {
				sum += j;
			}
		}
		return sum;
	}

}

Lösung: 4179871

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.

public class Problem21 {
	
	public static void main(String[] args) {
		int sum = 0;
		for (int i = 1; i < 10000; i++) {
			int d = d(i);
			if((d(d) == i && i != d)){
				sum += i;
				System.out.println(i);
			}
		}
		System.out.println(sum);
	}

	public static int d (int number){
		int sum = 0;
		for (int i = 1; i < number; i++) {
			if (number%i==0) {
				sum += i;
			}
		}
		return sum;
	}
	
}

Lösung: 31626

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.

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

public class Problem19 {

    public static void main(String[] args) {

	int[] months = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
	int days = 0;
	int sundays = 0;

	for (int i = 1901; i <= 2000; i++) {
	    for (int j = 0; j < months.length; j++) {
		if (days % 7 == 0) {
		    sundays++;
		}
		if (j == 1 && isLeapYear(i)) {
		    days += 29;
		} else {
		    days += months[j];
		}
		
	    }
	}
	System.out.println(sundays);

    }
    public static boolean isLeapYear(int year) {
	return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0);
    }
}

Lösung: 171

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Das Ganze wird diesmal ohne ein Java-Programm gelöst, da es den ganzen Aufwand nicht wert wäre.

Entscheidend ist hier folgende Formel

wobei n der Kantenlänge des Quadrats entspricht.

Also ergibt ein Quadrat der Kantenlänge n=20

Lösung: 137846528820

In the 20×20 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 the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

int[][] numbers = {		
		{ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
		{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
		{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
		{52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
		{21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
		{78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
		{16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
		{86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
		{19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
		{ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
		{88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
		{ 4, 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,  4, 36, 16},
		{20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
		{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48}		
	};
	
	int max = 0;
	
	//horizontal
	for (int i = 0; i < numbers.length; i++) {
	    for (int j = 0; j < numbers[0].length-3; j++) {
		int temp = numbers[i][j] * numbers[i][j+1] * numbers[i][j+2] * numbers[i][j+3];
		if (temp>max) {
		    max = temp;
		    System.out.println("i: " + i + " j: " + j);
		}
	    }
	}
	
	//vertikal
	for (int i = 0; i < numbers[0].length; i++) {
	    for (int j = 0; j < numbers.length-3; j++) {
		int temp = numbers[j][i] * numbers[j+1][i] * numbers[j+2][i] * numbers[j+3][i];
		if (temp>max) {
		    max = temp;
		    System.out.println("i: " + i + " j: " + j);
		}
	    }
	}
	
	//diagonal left up to down right
	for (int i = 0; i < numbers[0].length-3; i++) {
	    for (int j = 0; j < numbers.length-3; j++) {
		int temp = numbers[j][i] * numbers[j+1][i+1] * numbers[j+2][i+2] * numbers[j+3][i+3];
		if (temp>max) {
		    max = temp;
		    System.out.println("i: " + i + " j: " + j);
		}
	    }
	}
	
	//diagonal right up to left down
	for (int i = numbers[0].length-1; i > 2; i--) {
	    for (int j = 0; j < numbers.length-3; j++) {
		int temp = numbers[j][i] * numbers[j+1][i-1] * numbers[j+2][i-2] * numbers[j+3][i-3];
		if (temp>max) {
		    max = temp;
		    System.out.println("i: " + i + " j: " + j);
		}
	    }
	}
	
	System.out.println(max);

Lösung: 70600674

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.
Find the last ten digits of this prime number.

BigInteger number1 = BigInteger.valueOf(28433);
BigInteger number2 = BigInteger.valueOf(2);
number2 = number2.modPow(new BigInteger("7830457"), new BigInteger("10000000000"));
number1 = number1.multiply(number2);
number1 = number1.mod(new BigInteger("10000000000"));
number1 = number1.add(BigInteger.ONE);
System.out.println(number1);

Lösung: 8739992577

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b

int largest = 0;
for (long a = 1; a < 100; a++) {
	for (int b = 1; b < 100; b++) {
		BigInteger number = BigInteger.valueOf(a);
		number = number.pow(b);
		String tempnumber = number.toString();
		int temp = 0;
		for (int i = 0; i < tempnumber.length(); i++) {
			temp += tempnumber.charAt(i)-48;
		}
		if (temp > largest) {
			largest = temp;
		}
	} 
}
System.out.println(largest);

Lösung: 972

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?

int counter = 0;
for (int i = 0; i <= 200; i++) {//1 pence
	for (int j = 0; j <= 100; j++) {//2 pence
		for (int k = 0; k <= 40; k++) {//5 pence
			for (int l = 0; l <= 20; l++) {//10 pence
				for (int m = 0; m <= 10; m++) {//20 pence
					for (int n = 0; n <= 4; n++) {//50 pence
						for (int o = 0; o <= 2; o++) {//1 pound
							for (int p = 0; p <= 1; p++) {//2 pound
								if ((i*1+j*2+k*5+l*10+m*20+n*50+o*100+p*200)==200) {
									counter++;
								}
							}
						}
					}
				}
			}
		}
	}
}
System.out.println(counter);

Lösung: 73682