Versuchen Sie, Project Euler in Java zu lösen

Einführung

Beeilen Sie sich Link zu Project Euler Klicken Sie hier für den japanischen Link

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Problem1.java

public class Problem1{
    public static void main(String[] args){
      int sum = 0;
      for(int i=3; i<=1000; i++){
          if(i%3 == 0 || i%5 == 0){
              sum += i;
          }
      }
      System.out.printf("The answer is %d.\n", sum);
    }
}

Ausführungsergebnis

The answer is 233168.

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Problem2.java

public class Problem2 {
    public static void main(String[] args){
        final int MAX_VALUE = 4000000;

        int value1 = 1;
        int value2 = 1;
        int currentValue = value1 + value2;
        int sumOfValues = 0; // initialized by zero

        while(currentValue < MAX_VALUE){
            if(currentValue % 2 == 0) {
                sumOfValues += currentValue;
            }
            value1 = value2;
            value2 = currentValue;
            currentValue = value1 + value2;
        }

        System.out.printf("The answer is %d.\n", sumOfValues);
    }
}

Ausführungsergebnis

The answer is 4613732.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Problem3.java

public class Problem3 {

	public static void main(String[] args) {
		Long num = 600851475143L;

		for(int divisor=2; divisor<=Math.sqrt(num); divisor++) {
			while(true) {
				if(num%divisor == 0) {
					num /= divisor;
				}else{
					break;
				}
			}
		}
		System.out.printf("The answer is %d.\n", num);
	}
}

Ausführungsergebnis

The answer is 6857.

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Problem4.java

public class Problem4 {

	public static void main(String[] args) {
		final int MAX_NUM = 999;
		int numberOfLargestPalindrome = 0;

		for(int i=MAX_NUM; i>0; i--) {
			for(int j=MAX_NUM; j>i; j--) {
				if(checkPalindrome(String.valueOf(i*j))){
					numberOfLargestPalindrome = Math.max(i*j, numberOfLargestPalindrome);
					break;
				}
			}
		}
		System.out.printf("The answer is %d.\n", numberOfLargestPalindrome);
	}

	public static boolean checkPalindrome(String str) {
		for(int i=0; i<str.length()/2; i++) {
			if(str.charAt(i) != str.charAt(str.length() - 1 - i)) {
				return false;
			}
		}
		return true;
	}
}

Ausführungsergebnis

The answer is 906609.

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Problem5.java

public class Problem5 {
	public static void main(String[] args) {

		int minNum = 2;
		int maxNum = 20;
		int commonMul = 1;	

		for(int i=minNum; i<=maxNum; i++) {
			commonMul = getLCM(commonMul, i);
		}
		System.out.printf("The answer is %d.\n", commonMul);
	}

	/*
	 *Eine Methode, die das minimale gemeinsame Vielfache von zwei Werten ausgibt
	 *Minimales gemeinsames Vielfaches(LCM: Latest common multiple)
	 */
	public static int getLCM(int x, int y) {
		return x*(y/getGCD(x, y));	// overflow taisaku...
	}

	/*
	 *Eine Methode, die die maximale Verpflichtung von zwei Werten ausgibt
	 *Erhalten mit der euklidischen Methode der gegenseitigen Teilung
	 *Maximales Engagement (GCD): Greatest common divisor)
	 */
	public static int getGCD(int x, int y) {
		while(y != 0) {
			int temp = x;
			x = y;
			y = temp%y;
		}
		return x;
	}
}

Ausführungsergebnis

The answer is 232792560.

Problem 6

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Problem6.java

public class Problem6 {

	public static void main(String[] args) {
		final int MAX_NUM = 100;

		int sumOfSquares = 0;
		int squareOfSum = 0;

		for(int i=1; i<=MAX_NUM; i++) {
			sumOfSquares += i*i;
			squareOfSum += i;
		}
		squareOfSum *= squareOfSum;

		System.out.printf("The answer is %d.\n", squareOfSum-sumOfSquares);
	}
}

Ausführungsergebnis

The answer is 25164150.

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Problem7.java

import java.util.ArrayList;

public class Problem7 {

	public static void main(String[] args) {

		final int NUM = 10001;

		ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
		primeNumbers.add(2);
		int number = 3;

		while(primeNumbers.size() < NUM) {
			if(checkPrimeNumber(number, primeNumbers)) {
				primeNumbers.add(number);
			}
			number += 2;
		}
		System.out.printf("The answer is %d.\n", primeNumbers.get(NUM-1));
	}


	public static boolean checkPrimeNumber(int target, ArrayList<Integer> divisors) {

		for(int divisor: divisors) {
			if(target%divisor == 0) {
				return false;
			}
		}
		return true;
	}
}

Ausführungsergebnis

The answer is 104743.

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

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

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Problem8.java

public class Problem8 {

	public static void main(String[] args) {
		String src = "73167176531330624919225119674426574742355349194934\r\n" +
				" 96983520312774506326239578318016984801869478851843\r\n" +
				" 85861560789112949495459501737958331952853208805511\r\n" +
				" 12540698747158523863050715693290963295227443043557\r\n" +
				" 66896648950445244523161731856403098711121722383113\r\n" +
				" 62229893423380308135336276614282806444486645238749\r\n" +
				" 30358907296290491560440772390713810515859307960866\r\n" +
				" 70172427121883998797908792274921901699720888093776\r\n" +
				" 65727333001053367881220235421809751254540594752243\r\n" +
				" 52584907711670556013604839586446706324415722155397\r\n" +
				" 53697817977846174064955149290862569321978468622482\r\n" +
				" 83972241375657056057490261407972968652414535100474\r\n" +
				" 82166370484403199890008895243450658541227588666881\r\n" +
				" 16427171479924442928230863465674813919123162824586\r\n" +
				" 17866458359124566529476545682848912883142607690042\r\n" +
				" 24219022671055626321111109370544217506941658960408\r\n" +
				" 07198403850962455444362981230987879927244284909188\r\n" +
				" 84580156166097919133875499200524063689912560717606\r\n" +
				" 05886116467109405077541002256983155200055935729725\r\n" +
				" 71636269561882670428252483600823257530420752963450";

		final int NUM = 13;
		final int DIGIT = 1000;
		long greatestProduct = 0; // initialize by zero

		src = src.replace("\r\n ", "");
		String[] strAry = src.split("");

		int[] intAry = new int[DIGIT];
		for(int i=0; i<DIGIT; i++) {
			intAry[i] = Integer.valueOf(strAry[i]).intValue();
		}


		for(int startIndex=0; startIndex<DIGIT-NUM; startIndex++) {
			long prod = 1L;
			for(int offset=0; offset<NUM; offset++) {
				prod *= intAry[startIndex + offset];
			}
			greatestProduct = Math.max(prod, greatestProduct);
		}
		System.out.printf("The answer is %d.\n", greatestProduct);
	}

}

Ausführungsergebnis

The answer is 23514624000.

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 .

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Problem9.java

public class Problem9 {

	public static void main(String[] args) {
		for(int a = 1; a < 333; a++) {
			for(int b = a+1; b < 1000-a; b++) {
				int c = 1000 - a - b;
				if (Math.pow(c, 2) == Math.pow(a, 2) + Math.pow(b, 2)) {
					System.out.printf("The answer is %d.\n", (a*b*c));
					break;
				}
			}
		}
	}
}

Ausführungsergebnis

The answer is 31875000.

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Problem10.java

import java.util.Arrays;

public class Problem10 {

	public static void main(String[] args) {
		int MAX_NUM = 2000000;
		printPrimeNumber(maxNum);
	}

	public static void printPrimeNumber(int maxNum) {
		boolean[] numAry = new boolean[maxNum+1];

		Arrays.fill(numAry, true);
		numAry[0] = false;
		numAry[1] = false;

		double sqrt = Math.sqrt(maxNum);

		for(int i=2; i<=sqrt; i++){
			if(numAry[i]){
				for(int j=i*2; j<=maxNum; j+=i) {
					numAry[j] = false;
				}
			}
		}

		long sum = 0L;
		for(int i=2; i<=maxNum; i++) {
			if(numAry[i]) {
				//System.out.println(i);
				sum += i;
			}
		}
		System.out.printf("The answer is %d.\n", sum);
	}
}

Ausführungsergebnis

The answer is 142913828922.

Problem 11

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?

Problem11.java

public class Problem11 {

	public static void main(String[] args) {

		String src = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\r\n" +
				" 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\r\n" +
				" 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\r\n" +
				" 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\r\n" +
				" 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\r\n" +
				" 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\r\n" +
				" 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\r\n" +
				" 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\r\n" +
				" 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\r\n" +
				" 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\r\n" +
				" 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\r\n" +
				" 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\r\n" +
				" 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\r\n" +
				" 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\r\n" +
				" 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\r\n" +
				" 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\r\n" +
				" 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\r\n" +
				" 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\r\n" +
				" 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\r\n" +
				" 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";

		final int ROW = 20;
		final int COLUMN = 20;
		final int NUM = 4;
		int greatestProduct = 0; // initialize by zero

		src = src.replace("\r\n", "");

		// convert String type to String[] array (one-dimensional array of String type)
		String[] strAry = src.split(" ");

		// convert String[] array to int[][] array (two-dimensional array of integer type)
		int[][] intAry = new int[ROW][COLUMN];
		for(int i=0; i<strAry.length; i++) {
			intAry[i/ROW][i%COLUMN] = Integer.valueOf(strAry[i]).intValue();
		}

		/*
		 * calculate greatest product
		 *** rightProd: product of NUM numbers from intAry[currentRow][currenCol] to right.
		 *** downProd: ~ to downward.
		 *** ldProd: ~ to left downward.
		 *** rdProd: ~ to right downward.
		 */
		for(int currentRow=0; currentRow<ROW; currentRow++) {
			for(int currentCol=0; currentCol<COLUMN; currentCol++) {

				int rightProd = 1, downProd = 1, rdProd = 1, ldProd = 1;

				for(int offset=0; offset<NUM; offset++) {
					if(currentRow + NUM < ROW) {
						rightProd *= intAry[currentRow + offset][currentCol];
					}
					if(currentCol + NUM < COLUMN) {
						downProd *= intAry[currentRow][currentCol + offset];
					}
					if(currentRow + NUM < ROW && currentCol + NUM < COLUMN) {
						rdProd *= intAry[currentRow + offset][currentCol + offset];
					}
					if(currentRow - NUM >= 0 && currentCol + NUM < COLUMN) {
						ldProd *= intAry[currentRow - offset][currentCol + offset];
					}
				}
				greatestProduct = calcMaxValueInFiveInteger(rightProd, downProd, rdProd, ldProd, greatestProduct);
			}
		}

		// display the answer
		System.out.printf("The answer is %d.\n", greatestProduct);
	}

	// Method for returning the greatest value in five values
	public static int calcMaxValueInFiveInteger(int a, int b, int c, int d, int e) {

		int[] ary = {a, b, c, d, e};
		int maxValue = 0;
		for(int n: ary) {
			maxValue = Math.max(maxValue, n);
		}
		return maxValue;
	}
}

Ausführungsergebnis

The answer is 70600674.

Problem 12

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?

Problem12.java

public class Problem12 {

	public static void main(String[] args) {
		final int NUM = 500;
		int triangularNum = 1;
		int term = 2;

		while(countDivisor(triangularNum) <= NUM) {
			triangularNum += term;
			term++;
		}

		System.out.printf("The answer is %d.\n", triangularNum);
	}

	public static int countDivisor(int target) {
		double sqrt = Math.sqrt(target);
		int count = 0;

		for(int div=1; div<sqrt; div++) {
			if(target%div == 0) count++;
		}
		return count*2;
	}
}

Ausführungsergebnis

The answer is 76576500.

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 ... 53503534226472524250874054075591789781264330331690

Problem13.java

import java.math.BigInteger;

public class Problem13 {

	public static void main(String[] args) {

		String src = getSrc();

		src = src.replace("\r\n", "");
		String[] strAry = src.split(" ");

		BigInteger sum = new BigInteger("0");

		for(String str: strAry) {
			sum = sum.add(new BigInteger(str));
		}
		
		String answer = String.valueOf(sum).substring(0, 10);
		System.out.printf("The answer is %s.\n", answer);
	}


	// Too long!!
	public static String getSrc() {
		return "37107287533902102798797998220837590246510135740250\r\n" +
				" 46376937677490009712648124896970078050417018260538\r\n" +
				" 74324986199524741059474233309513058123726617309629\r\n" +
                                ..............
				" 53503534226472524250874054075591789781264330331690";
	}
}

Ausführungsergebnis

The answer is 5537376230.

Problem 14

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.

Problem14.java

import java.util.HashMap;

public class Problem14 {

	public static void main(String[] args) {
		final int MAX_NUM = 1000000;
		Long numWithLongestChain = 1L;	//initialized by one
		HashMap<Long, Long> step = new HashMap<Long, Long>();
		step.put(1L, 1L);

		for(Long startNum=2L; startNum<MAX_NUM; startNum++) {
			if(step.get(startNum) == null){
				calcCollatzSeq(startNum, step);
			}
			if (step.get(numWithLongestChain) < step.get(startNum)) {
				numWithLongestChain = startNum;
			}
		}
		System.out.printf("The answer is %d.\n", numWithLongestChain);
	}

	public static void calcCollatzSeq(Long currentNum, HashMap<Long, Long> step){
		Long nextNum = calcNextNum(currentNum);
		if(step.get(nextNum) == null) {
			calcCollatzSeq(nextNum, step);
		}
		step.put(currentNum, step.get(nextNum)+1L);
	}

	public static Long calcNextNum(Long num) {
		if(num%2 == 0) {
			return num/2;
		}else{
			return num*3+1;
		}
	}
}

Ausführungsergebnis

The answer is 837799.

Problem 15

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?

Problem15.java

import java.math.BigInteger;

public class Problem15 {

	public static void main(String[] args) {

		int hGrid = 20;
		int vGrid = 20;
		BigInteger numRoutes = new BigInteger("1");

		for(int i=hGrid+vGrid; i>1; i--) {
			String sInt = String.valueOf(i);
			numRoutes = numRoutes.multiply(new BigInteger(sInt));
			if (i <= hGrid) {
				numRoutes = numRoutes.divide(new BigInteger(sInt));
			}
			if (i <= vGrid) {
				numRoutes = numRoutes.divide(new BigInteger(sInt));
			}
		}
		System.out.printf("The answer is %d.\n", numRoutes);
	}
}

Ausführungsergebnis

The answer is 137846528820.

Problem 16

2^{15} = 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?

Problem16

import java.math.BigInteger;

public class Problem16 {

	public static void main(String[] args) {

		final int NUM = 2;
		final int POWER = 1000;
		int sumOfDigit = 0;	// initialized by zero
		BigInteger src = new BigInteger(String.valueOf(NUM));
		src = src.pow(POWER);
		String[] strAry = src.toString().split("");

		for(String s: strAry) {
			sumOfDigit += Integer.valueOf(s);
		}

		System.out.printf("The answer is %d.\n", sumOfDigit);
	}
}

Ausführungsergebnis

The answer is 1366.

Problem 17

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.

Problem17.java

import java.util.HashMap;

public class Problem17 {

	public static void main(String[] args) {

		HashMap<Integer, String> words = new HashMap<>();
		words.put(0, "");
		words.put(1, "one");
		words.put(2, "two");
		words.put(3, "three");
		words.put(4, "four");
		words.put(5, "five");
		words.put(6, "six");
		words.put(7, "seven");
		words.put(8, "eight");
		words.put(9, "nine");
		words.put(10, "ten");
		words.put(11, "eleven");
		words.put(12, "twelve");
		words.put(13, "thirteen");
		words.put(14, "fourteen");
		words.put(15, "fifteen");
		words.put(16, "sixteen");
		words.put(17, "seventeen");
		words.put(18, "eighteen");
		words.put(19, "nineteen");
		words.put(20, "twenty");
		words.put(30, "thirty");
		words.put(40, "forty");
		words.put(50, "fifty");
		words.put(60, "sixty");
		words.put(70, "seventy");
		words.put(80, "eighty");
		words.put(90, "ninety");

		int sumOfLetterCounts = "onethousand".length(); //initialization

		for(int i=1; i<1000; i++) {

			int digit1 = i%10;		//Platz 1
			int digit2 = i%100/10;	//10. Platz
			int digit3 = i/100;		//100. Platz

			// 1,Berechnung der zweiten Ziffer
			if(digit2 < 2) {
				sumOfLetterCounts += words.get(digit1+digit2*10).length();
			} else {
				sumOfLetterCounts += words.get(digit2*10).length();
				sumOfLetterCounts += words.get(digit1).length();
			}

			//Berechnung der 3. Stelle
			if(digit3 > 0) {
				sumOfLetterCounts += words.get(digit3).length();
				sumOfLetterCounts += "hundred".length();
				if(digit1 != 0 || digit2 != 0) {
					sumOfLetterCounts += "and".length();
				}
			}
		}

		System.out.printf("The answer is %d.\n", sumOfLetterCounts);
	}

}

Ausführungsergebnis

The answer is 21124.

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

   3
  7 4
 2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

              75
             95 64
            17 47 82
           18 35 87 10
          20 04 82 47 65
         19 01 23 75 03 34
        88 02 77 73 07 63 67
       99 65 04 28 06 16 70 92
      41 41 26 56 83 40 80 70 33
     41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
   70 11 33 28 77 73 17 78 39 68 17 57
  91 71 52 38 17 14 91 43 58 50 27 29 48
 63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Problem18.java

public class Problem18 {

	public static void main(String[] args) {
		String src = "75\r\n" +
				" 95 64\r\n" +
				" 17 47 82\r\n" +
				" 18 35 87 10\r\n" +
				" 20 04 82 47 65\r\n" +
				" 19 01 23 75 03 34\r\n" +
				" 88 02 77 73 07 63 67\r\n" +
				" 99 65 04 28 06 16 70 92\r\n" +
				" 41 41 26 56 83 40 80 70 33\r\n" +
				" 41 48 72 33 47 32 37 16 94 29\r\n" +
				" 53 71 44 65 25 43 91 52 97 51 14\r\n" +
				" 70 11 33 28 77 73 17 78 39 68 17 57\r\n" +
				" 91 71 52 38 17 14 91 43 58 50 27 29 48\r\n" +
				" 63 66 04 68 89 53 67 30 73 16 69 87 40 31\r\n" +
				" 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

		String[] strAry = src.split("\r\n ");
		final int HEIGHT = strAry.length;
		Integer[][] intAry = new Integer[HEIGHT][HEIGHT];

		// convert String one-dimentional array to Integer two-dimentional array
		for(int i=0; i<HEIGHT; i++) {
			String[] tempStrAry = strAry[i].split(" ");
			for(int j=0; j<HEIGHT; j++) {
				if (j < tempStrAry.length) {
					intAry[i][j] = Integer.parseInt(tempStrAry[j]);
				} else {
					intAry[i][j] = null;
				}
			}
		}

		// debug
		System.out.println("===== Before =====");
		print2DArray(intAry);

		// calculate the largest sum from the top
		for(int i=1; i<HEIGHT; i++) {
			for(int j=0; j<=i; j++) {
				if(j < 1) {
					intAry[i][j] += intAry[i-1][j]; // leftmost element
				} else if(j == i) {
					intAry[i][j] += intAry[i-1][j-1]; // rightmost element
				} else {
					intAry[i][j] += Math.max(intAry[i-1][j-1], intAry[i-1][j]);  // internal element
				}
			}
		}

		// debug
		System.out.println("\n===== After =====");
		print2DArray(intAry);

		// caluculate the maximum number in the numbers of bottoms
		int maxNum = intAry[HEIGHT-1][0];
		for(int i=1; i<HEIGHT; i++) {
			maxNum = Math.max(maxNum, intAry[HEIGHT-1][i]);
		}

		System.out.printf("The answer is %d.\n", maxNum);
	}

	// method to display two-dimentional array
	public static void print2DArray(Integer[][] ary) {
		for(Integer[] row : ary) {
			for(Integer num : row) {
				if(num != null) {
					System.out.printf("%5d", num);
				} else {
					System.out.print("");
				}
			}
			System.out.println("");
		}
	}
}

Ausführungsergebnis

===== Before =====
   75
   95   64
   17   47   82
   18   35   87   10
   20    4   82   47   65
   19    1   23   75    3   34
   88    2   77   73    7   63   67
   99   65    4   28    6   16   70   92
   41   41   26   56   83   40   80   70   33
   41   48   72   33   47   32   37   16   94   29
   53   71   44   65   25   43   91   52   97   51   14
   70   11   33   28   77   73   17   78   39   68   17   57
   91   71   52   38   17   14   91   43   58   50   27   29   48
   63   66    4   68   89   53   67   30   73   16   69   87   40   31
    4   62   98   27   23    9   70   98   73   93   38   53   60    4   23

===== After =====
   75
  170  139
  187  217  221
  205  252  308  231
  225  256  390  355  296
  244  257  413  465  358  330
  332  259  490  538  472  421  397
  431  397  494  566  544  488  491  489
  472  472  520  622  649  584  571  561  522
  513  520  592  655  696  681  621  587  655  551
  566  591  636  720  721  739  772  673  752  706  565
  636  602  669  748  798  812  789  850  791  820  723  622
  727  707  721  786  815  826  903  893  908  870  847  752  670
  790  793  725  854  904  879  970  933  981  924  939  934  792  701
  794  855  891  881  927  913 1040 1068 1054 1074  977  992  994  796  724
The answer is 1074.

Problem 19

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

・ Der 1. Januar 1900 war ein Montag. ・ Dreißig Tage hat 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. ・ Wie viele Sonntage fielen am ersten des Monats im 20. Jahrhundert (1. Januar 1901 bis 31. Dezember 2000)?

Problem19.java

public class Problem19 {

	public static void main(String[] args) {

		final int START_YEAR = 1901;
		final int END_YEAR = 2000;

		int sumOfDays = 0; // initialized by zero
		int count = 0; // initialized by zero

		for(int currentYear=1900; currentYear<=END_YEAR; currentYear++) {
			for(int currentMonth=1; currentMonth<=12; currentMonth++) {
				if(currentYear >= START_YEAR && sumOfDays%7 == 6) {
					count++;
				}

				if(currentMonth==4 || currentMonth==6 || currentMonth==9 || currentMonth==11) {
					sumOfDays += 30;
				} else if(currentMonth == 2) {
					if(currentYear%4 != 0 || (currentYear%400 != 0 && currentYear%100 == 0)) {
						sumOfDays += 28;
					} else {
						sumOfDays += 29;
					}
				} else {
					sumOfDays += 31;
				}
			}
		}

		System.out.printf("The answer is %d.\n", count);
	}
}

Ausführungsergebnis

The answer is 171.

Problem 20

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!

Problem20.java

import java.math.BigInteger;

public class Problem20 {

	public static void main(String args[]) {
		final int N = 100;
		BigInteger factorial = new BigInteger("1"); // initialized by one
		int sum = 0; // initialized by zero

		for(int i=2; i<=N; i++) {
			factorial = factorial.multiply(new BigInteger(String.valueOf(i)));
		}

		for(String s: factorial.toString().split("")) {
			sum += Integer.parseInt(s);
		}

		System.out.printf("The answer is %d.\n", sum);
	}
}

Ausführungsergebnis

The answer is 648.

Problem 21

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.

java.Problem21.java

import java.util.HashMap;

public class Problem21 {

	public static void main(String[] args) {

		final int MAX_NUM = 10000;
		HashMap<Integer, Integer> sumOfDiv = new HashMap<Integer, Integer>();
		int sumOfAmicableNum = 0; // initilized by zero

		sumOfDiv.put(1, 0);

		for(int num=2; num<MAX_NUM; num++) {
			if(sumOfDiv.get(num) == null) {
				sumOfDiv.put(num, calcSumOfProperDivisors(num));
			}

			Integer partnerNum = sumOfDiv.get(num);
			if(sumOfDiv.get(partnerNum) == null) {
				sumOfDiv.put(partnerNum, calcSumOfProperDivisors(partnerNum.intValue()));
			}

			if(num == sumOfDiv.get(partnerNum) && num != partnerNum) {
				sumOfAmicableNum += sumOfDiv.get(num);
			}
		}
		System.out.printf("The answer is %d.\n", sumOfAmicableNum);
	}

	public static Integer calcSumOfProperDivisors(int num) {
		Integer sum = 1;
		for(int divisor=2; divisor<=Math.sqrt(num); divisor++) {
			if(num%divisor == 0) {
				if(divisor*divisor != num) {
					sum += divisor + num/divisor;
				} else {
					sum += divisor;
				}
			}
		}
		return sum;
	}
}

Ausführungsergebnis

The answer is 31626.

Problem 22

Using names.txt(rightclickand'SaveLink/TargetAs...'), 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?

Problem22.java

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

public class Problem22 {

	public static void main(String[] args) {
		String filePath = "names.txt";

		String[] names = readFile(filePath);
		Arrays.sort(names);
		long sumOfScores = 0L; // initialized by zero

		for(int i=0; i<names.length; i++) {
			for(int j=0; j<names[i].length(); j++) {
				sumOfScores += ((long)names[i].charAt(j) - (long)'A' + 1L) * (i+1);
			}
		}
		System.out.printf("The answer is %d.\n", sumOfScores);
	}

	public static String[] readFile(String path) {

		String[] target = null;

		try (BufferedReader br = new BufferedReader(new FileReader(path))){
			String src = br.readLine();
			src = src.replace("\"", "");
			target = src.split(",");
		} catch (FileNotFoundException e){
			e.printStackTrace();
		} catch(IOException e) {
			e.printStackTrace();
		}
		return target;
	}

}

Ausführungsergebnis

The answer is 871198282.

Problem 23

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.

Problem23

import java.util.ArrayList;
import java.util.Arrays;

public class Problem23 {

	public static void main(String[] args) {
		final int MAX_NUM = 28123;
		ArrayList<Integer> abundantNumbers = new ArrayList<Integer>();
		Boolean[] SumsOfTwoAbundantNumbers = new Boolean[MAX_NUM+1];
		int sum = 0;	// initialized by zero
		Arrays.fill(SumsOfTwoAbundantNumbers, false);

		// calc abundant numbers
		for(int i=2; i<=MAX_NUM; i++) {
			if(isAbundantNumber(i)) {
				abundantNumbers.add(i);
			}
		}

		// calc sums of the two abundant numbers
		for(int i=0; i<=abundantNumbers.size()/2; i++) {
			for(int j=i; j<=abundantNumbers.size(); j++) {
				if(MAX_NUM >= abundantNumbers.get(i) + abundantNumbers.get(j)) {
					SumsOfTwoAbundantNumbers[abundantNumbers.get(i)+abundantNumbers.get(j)] = true;
				} else {
					break;
				}
			}
		}

		// calc non-sum of sums of the two abudndant numbers
		for(int i=1; i<SumsOfTwoAbundantNumbers.length; i++) {
			if(!SumsOfTwoAbundantNumbers[i]) {
				sum += i;
			}
		}
		System.out.printf("The answer is %d.\n", sum);
	}

	public static boolean isAbundantNumber(int num) {
		int sum = 1;		// initialized by one
		double sqrt = Math.sqrt(num);

		for(int divisor=2; divisor<sqrt; divisor++) {
			if(num%divisor == 0) {
				sum += divisor + num/divisor;
			}
		}
		if(sqrt == Math.floor(sqrt)) {
			sum += sqrt;
		}
		return num < sum;
	}
}

Ausführungsergebnis

The answer is 4179871.

Problem 24

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?

Problem24.java

import java.util.ArrayList;

public class Problem24 {

	public static void main(String[] args) {
		final int NUM = 1000000;
		ArrayList<String> srcList = new ArrayList<String>();
		String target = "";

		for(int i=0; i<=10; i++) {
			srcList.add(String.valueOf(i));
		}

		int numberOfCases = 0;
		for(int currentDigit=10; currentDigit>0; currentDigit--) {
			int factorial = 1;
			int srcIndex = 0;
			for(int i=1; i<currentDigit; i++) {
				factorial *= i;
			}

			while(numberOfCases + factorial < NUM) {
				numberOfCases += factorial;
				srcIndex++;
			}
			target += srcList.get(srcIndex);
			srcList.remove(srcIndex);
		}
		System.out.printf("The answer is %s.\n", target);
	}
}

Ausführungsergebnis

The answer is 2783915460.

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_{n−1} + F_{n−2}, where F_1 = 1 and F_2 = 1. Hence the first 12 terms will be:

F_1 = 1 F_2 = 1 F_3 = 2 F_4 = 3 F_5 = 5 F_6 = 8 F_7 = 13 F_8 = 21 F_9 = 34 F_{10} = 55 F_{11} = 89 F_{12} = 144 The 12th term, F_{12}, is the first term to contain three digits.

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

Problem25.java

import java.math.BigInteger;

public class Problem25{
    public static void main(String[] args){
        final int MAX_DIGIT = 1000;
        BigInteger term1 = new BigInteger("1");
        BigInteger term2 = new BigInteger("1");
        BigInteger targetTerm = new BigInteger("2");
        int index = 3;

        while(targetTerm.toString().length()<MAX_DIGIT){
            term1 = term2;
            term2 = targetTerm;

            targetTerm = term1.add(term2);
            index++;
        }

        System.out.printf("The answer is %d.\n", index);
    }
 }

Ausführungsergebnis

The answer is 4782.

Problem 26

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Problem26.java

import java.util.ArrayList;
import java.util.HashMap;

public class Problem26 {
    public static void main(String[] args){
        final int MAX_NUM = 1000;
        int longestRecurringCycle = 0;
        int divisorWithLongestRecurringCycle = 0;

        for(int divisor=2; divisor<MAX_NUM; divisor++){
            ArrayList<Integer> remainders = new ArrayList<Integer>();
            int remainder = 1;
            while(true){
                remainder = remainder*10%divisor;

                if(remainders.contains(remainder)){
                    break;
                }else{
                    remainders.add(remainder);
                }
            }
            if(longestRecurringCycle < remainders.size() - remainders.indexOf(remainder)){
                longestRecurringCycle = remainders.size() - remainders.indexOf(remainder);
                divisorWithLongestRecurringCycle = divisor;
            }
        }
        System.out.printf("The answer is %d.\n", divisorWithLongestRecurringCycle);
    }
}

Ausführungsergebnis

The answer is 983.

Problem 27

Euler discovered the remarkable quadratic formula:

n^2+n+41 It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,40^2+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,41^2+41+41 is clearly divisible by 41.

The incredible formula n^2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n^2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n e.g. |11|=11 and |−4|=4 Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

Problem27.java

import java.util.Arrays;
import java.util.HashMap;

public class Problem27 {

    public static void main(String[] args){

        boolean[] primeNumbers = calcPrimeNumbers(100000);
        HashMap<Character, Integer> answer = new HashMap<Character, Integer>();
        answer.put('n', 0); // initialized

        for(int a=-999; a<1000; a++){
            for(int b=2; b<=1000; b++){
                if(primeNumbers[b]){
                    int n = 0;
                    while(true){
                        int num = n * n + a * n + b;
                        if(num > 1 && primeNumbers[num]){
                            n++;
                        }else{
                            break;
                        }
                    }
                    if(answer.get('n') < n){
                        answer.put('a', a);
                        answer.put('b', b);
                        answer.put('n', n);
                    }
                }
            }
        }
        System.out.printf("The answer is %d.\n", answer.get('a') * answer.get('b'));
    }

    public static boolean[] calcPrimeNumbers(int maxNum) {

        boolean[] primeNumbers = new boolean[maxNum + 1];
        Arrays.fill(primeNumbers, true);
        primeNumbers[0] = false;
        primeNumbers[1] = false;

        for (int i = 2; i <= Math.sqrt(maxNum); i++) {
            if (primeNumbers[i]) {
                for (int j = i * 2; j <= maxNum; j += i) {
                    primeNumbers[j] = false;
                }
            }
        }
        return primeNumbers;
    }
}

Ausführungsergebnis

The answer is -59231.