# Introduction

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

#### `Execution result`

``````
``````

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

}
}

``````

#### `Execution result`

``````
``````

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

#### `Execution result`

``````
``````

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

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

#### `Execution result`

``````
``````

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

/*
*A method that outputs the least common multiple of two values
*Least common multiple(LCM: Latest common multiple)
*/
public static int getLCM(int x, int y) {
return x*(y/getGCD(x, y));	// overflow taisaku...
}

/*
*A method that outputs the greatest common divisor of two values
*Obtained using the Euclidean algorithm
*Greatest common divisor (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;
}
}
``````

#### `Execution result`

``````
``````

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;

}
}
``````

#### `Execution result`

``````
``````

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;

int number = 3;

}
number += 2;
}
}

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

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

#### `Execution result`

``````
``````

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

}
``````

#### `Execution result`

``````
``````

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)) {
break;
}
}
}
}
}
``````

#### `Execution result`

``````
``````

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

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

#### `Execution result`

``````
``````

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

}

// 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;
}
}
``````

#### `Execution result`

``````
``````

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++;
}

}

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

#### `Execution result`

``````
``````

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) {
}

}

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

``````

#### `Execution result`

``````
``````

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

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

#### `Execution result`

``````
``````

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

#### `Execution result`

``````
``````

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

}
}
``````

#### `Execution result`

``````
``````

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;		//1st place
int digit2 = i%100/10;	//10th place
int digit3 = i/100;		//100th place

// 1,Second digit calculation
if(digit2 < 2) {
sumOfLetterCounts += words.get(digit1+digit2*10).length();
} else {
sumOfLetterCounts += words.get(digit2*10).length();
sumOfLetterCounts += words.get(digit1).length();
}

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

}

}
``````

#### `Execution result`

``````
``````

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

}

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

#### `Execution result`

``````
===== 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
``````

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

#### `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;
}
}
}

}
}
``````

#### `Execution result`

``````
``````

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

}
}
``````

#### `Execution result`

``````
``````

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

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

#### `Execution result`

``````
``````

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.FileNotFoundException;
import java.io.IOException;
import java.util.Arrays;

public class Problem22 {

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

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

public static String[] readFile(String path) {

String[] target = null;

src = src.replace("\"", "");
target = src.split(",");
} catch (FileNotFoundException e){
e.printStackTrace();
} catch(IOException e) {
e.printStackTrace();
}
return target;
}

}
``````

#### `Execution result`

``````
``````

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)) {
}
}

// 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;
}
}
}

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

#### `Execution result`

``````
``````

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++) {
}

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

#### `Execution result`

``````
``````

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;

index++;
}

}
}
``````

#### `Execution result`

``````
``````

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{
}
}
if(longestRecurringCycle < remainders.size() - remainders.indexOf(remainder)){
longestRecurringCycle = remainders.size() - remainders.indexOf(remainder);
divisorWithLongestRecurringCycle = divisor;
}
}
}
}
``````

#### `Execution result`

``````
``````

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.

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){

HashMap<Character, Integer> answer = new HashMap<Character, Integer>();

for(int a=-999; a<1000; a++){
for(int b=2; b<=1000; b++){
int n = 0;
while(true){
int num = n * n + a * n + b;
n++;
}else{
break;
}
}
}
}
}
}
}

public static boolean[] calcPrimeNumbers(int maxNum) {

boolean[] primeNumbers = new boolean[maxNum + 1];

for (int i = 2; i <= Math.sqrt(maxNum); i++) {
for (int j = i * 2; j <= maxNum; j += i) {
#### `Execution result`
``````