Project EulerをJavaで解いてみる

# はじめに
取り急ぎ投下
[Project Eulerへのリンク](https://projecteuler.net/)
[日本語のリンクはこっち](http://odz.sakura.ne.jp/projecteuler/)


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

```java: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);
    }
}
```

```text:実行結果
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.


```java: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);
    }
}


```

```text:実行結果
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 ?


```java: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);
	}
}
```

```text:実行結果
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.



```java: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;
	}
}
```

```text:実行結果
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?



```java: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);
	}

	/*
	 *  2つの値の最小公倍数を出力するメソッド
	 *	最小公倍数(LCM: Latest common multiple)
	 */
	public static int getLCM(int x, int y) {
		return x*(y/getGCD(x, y));	// overflow taisaku...
	}

	/*
	 * 2つの値の最大公約数を出力するメソッド
	 * 	ユークリッドの互除法を用いて求める
	 *	最大公約数（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;
	}
}
```
```text:実行結果
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.


```java: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);
	}
}
```

```text:実行結果
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?


```java: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;
	}
}
```

```text:実行結果
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?

```java: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);
	}

}
```
```text:実行結果
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.



```java: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;
				}
			}
		}
	}
}
```
```text:実行結果
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.

```java: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);
	}
}
```
```text:実行結果
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?



```java: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;
	}
}
```
```text:実行結果
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?


```java: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;
	}
}
```
```text:実行結果
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



```java: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";
	}
}


```
```text:実行結果
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.

```java: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;
		}
	}
}
```
```text:実行結果
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?

```java: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);
	}
}
```

```text:実行結果
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$?

```java: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);
	}
}
```

```text:実行結果
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.

```java: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;		// 1の位
			int digit2 = i%100/10;	// 10の位
			int digit3 = i/100;		// 100の位

			// 1, 2桁目の計算
			if(digit2 < 2) {
				sumOfLetterCounts += words.get(digit1+digit2*10).length();
			} else {
				sumOfLetterCounts += words.get(digit2*10).length();
				sumOfLetterCounts += words.get(digit1).length();
			}

			// 3桁目の計算
			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);
	}

}
```

```text:実行結果
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.

```text
   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:

```text
              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)



```java: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("");
		}
	}
}
```

```text:実行結果
===== 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.

>・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)?

```java: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);
	}
}
```

```text:実行結果
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!

```java: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);
	}
}
```

```text:実行結果
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;
	}
}
```

```text:実行結果
The answer is 31626.
```

# Problem 22

>Using [names.txt](https://projecteuler.net/project/resources/p022_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?

```java: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;
	}

}
```

```text:実行結果
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.


```java: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;
	}
}
```

```text:実行結果
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?

```java: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);
	}
}
```

```text:実行結果
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?

```java: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);
    }
 }
```

```text:実行結果
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.

```java: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);
    }
}
```

```text:実行結果
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$.

```java: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;
    }
}
```

```text:実行結果
The answer is -59231.
```