はじめに
取り急ぎ投下
Project Eulerへのリンク
日本語のリンクはこっち
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.
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);
}
}
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.
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);
}
}
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 ?
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);
}
}
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.
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;
}
}
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?
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;
}
}
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.
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);
}
}
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?
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;
}
}
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
71636269561882670428252483600823257530420752963450Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
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);
}
}
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.
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;
}
}
}
}
}
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.
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);
}
}
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 48The 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?
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;
}
}
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,28We 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?
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;
}
}
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
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";
}
}
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.
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;
}
}
}
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?
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);
}
}
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$?
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);
}
}
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.
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);
}
}
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)
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("");
}
}
}
===== 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)?
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);
}
}
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!
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);
}
}
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.
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;
}
}
The answer is 31626.
Problem 22
Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.
What is the total of all the name scores in the file?
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;
}
}
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.
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;
}
}
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?
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);
}
}
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?
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);
}
}
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.
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);
}
}
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$.
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;
}
}
The answer is -59231.