## Problem 23: Non-abundant sums

*Difficulty: Easy

Problem:

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.

How to solve:

From the description above, sum of all the positive integer which cannot be written as the sum of two abundant numbers = sum of all positive integer smaller than 28124 that cannot be created by sum of two abundant numbers.

To do this we need to do three thing

1. create an abundant numbers list
2. go through that list, calculate the sum of two abundant number, make sure the sum is smaller than 28124, mark it as a number that can be constructed by the sum of two abundant number.
3. go through the list from 1 to 28123, if it is not marked, then it is non-abundant sum number.

In order to create an abundant numbers list, we must have a method to calculate the sum divisors (proper divisors) of a number, I know three ways to do this, I will show you two out of three ways, the last one is using prime factorization, it’s a little bit complicated.

Here is the first one, also the easiest one, go through from 1 to n-1, check if n mod i ==0, count it to sum

The second one is a bit more tricky, as you may know, we just need to loop to square root of n to calculate its sum of divisors, but we need its sum of proper divisors. Hence, before we return the value, we must subtract it from n itself (sum-n)

Create an abundant numbers list

go through the list and mark as described above

go through the list, sum up all the values that is not marked

Solution took 384 ms

## Problem 22: Names scores

*Difficulty: Easy

Problem:

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?

How to solve:

Read file, store in to a string,

split into names, store in a list, calculate score of each name and sum them up

calculate ASCII sum of a name

Solution took 14 ms

## Problem 21: Amicable numbers

*Difficulty: Easy

Problem:

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 ab, 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.

How to solve:

What is AMICABLE NUMBERS : https://en.wikipedia.org/wiki/Amicable_numbers

I can only think of two ways

1. Brute force

Assume  we got a method calculates sum of proper divisors of number, called sumDivisorsOf, then what we have to do is

The runtime heavily depends on how you build the sumDivisorsOf method

This is the most easiest (but runs slowest)

Combine with the above code, the solution took 385ms

To increase the speed, you need to modify the sumOfDivisors method, like using prime factorization, calculate sum of divisors of n, and then minus it from n (sum-=n) in order to get sum of proper divisors of n.

You can you sieve Eratosthenes, or a method to check primality, for example

naive primality test

2. Thābit ibn Qurra theorem

The Thābit ibn Qurra theorem is a method for discovering amicable numbers invented in the ninth century by the Arab mathematician Thābit ibn Qurra

It states that if

p = 3 × 2n − 1 − 1,
q = 3 × 2n − 1,
r = 9 × 22n − 1 − 1,

where n > 1 is an integer and p, q, and r are prime numbers, then 2n×p×q and 2n×r are a pair of amicable numbers. This formula gives the pairs (220, 284) for n=2, (17296, 18416) for n=4, and (9363584, 9437056) for n=7, but no other such pairs are known.

Unfortunately, this method cannot be applied to solve this problem, but here is the code for ones who’s curious.

import java.math.BigInteger;

import java.util.Scanner;

public class Prob21 {

publicstaticvoidmain(String[] args) {

Scannerinput = new Scanner(System.in);

BigIntegersum = BigInteger.ZERO;

int i = 1;

int n = input.nextInt();

long cur = System.currentTimeMillis();

while(i < n) {

BigIntegertwoPower_N_1 = BigInteger.valueOf(2l).pow(i1);

BigIntegertwoPower_N = BigInteger.valueOf(2l).pow(i);

BigIntegertwoPower_2N_1 = BigInteger.valueOf(2l).pow(2*i1);

BigIntegerp = BigInteger.valueOf(3l).multiply(twoPower_N_1).subtract(BigInteger.ONE);

BigIntegerq = BigInteger.valueOf(3l).multiply(twoPower_N).subtract(BigInteger.ONE);

BigIntegerr = BigInteger.valueOf(9l).multiply(twoPower_2N_1).subtract(BigInteger.ONE);

System.out.println(p+“-“+q+“-“+r);

if(isPrime(p)&&isPrime(q)&&isPrime(r)) {

BigIntegeran1 = BigInteger.valueOf(2l).pow(i).multiply(p).multiply(q);

BigIntegeran2 = BigInteger.valueOf(2l).pow(i).multiply(r);

System.out.println(an1 + ” – “ + an2);

}

i+=1;

}

System.out.println(sum);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

privatestaticbooleanisPrime(BigInteger bigN) {

if(bigN.compareTo(BigInteger.ONE) <= 0)

returnfalse;

else if(bigN.compareTo(BigInteger.valueOf(3l))<=0)

returntrue;

else if(bigN.mod(BigInteger.valueOf(2l)).compareTo(BigInteger.ZERO)==0

||bigN.mod(BigInteger.valueOf(3l)).compareTo(BigInteger.ZERO)==0)

returnfalse;

BigIntegerbigI = BigInteger.valueOf(5l);

while(bigI.multiply(bigI).compareTo(bigN)<=0){

if(bigN.mod(bigI).compareTo(BigInteger.ZERO)==0

returnfalse;

}

returntrue;

}

}

## Problem 20: Factorial digit sum

*Difficulty: Easy

Problem:

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!

How to solve :

Dealing with big numbers (hundreds number of digits) is tough. But BigInteger in Java will make it easier than ever. By using BigInteger, this problem can be solve in just the matter of minutes.

Solution took 3 ms

Implementation: Java

import java.math.BigInteger;

public class Prob20 {

publicstaticvoidmain(String[] args) {

long cur = System.currentTimeMillis();

BigIntegerbigN = BigInteger.valueOf(1);

for(long i = 2; i <= 100; ++i) {

bigN = bigN.multiply(BigInteger.valueOf(i));

}

int sum = 0;

String s = bigN.toString();

for(int i = 0; i < s.length(); ++i) {

sum += Integer.valueOf(s.charAt(i)+“”);

}

System.out.println(sum);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

}

## Problem 19: Counting Sundays

*Difficulty: Easy

Problem:

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

How to solve:

First , we need a class that represent a date

private static class Date implements Comparable<Date>{

public static final int[] dayInMonth = {0,31,28,31,30,31,30,31,31,30,31,30,31};

public static final String[] monthNames = {“”,“Jan”,“Feb”,“Mar”,“Apr”,“May”,

“jun”,“Jul”,“Aug”,“Sep”,“Oct”,“Nov”,“Dec”};

publicintday;

publicintmonth;

publicintyear;

publicDate(int day, int month, int year) {

this.year = (year >= 1900 ) ? year : 1900;

this.month = (month>=1&&month<=12) ? month : 1;

if(day == 29 && month == 2 && isLeapYear(this.year)) {

this.day = day;

} else {

this.day = day>=1 && day <= dayInMonth[month] ? day : 1;

}

}

publicDate() {

this.day = 1;

this.month = 1;

this.year = 1900;

}

privatestaticbooleanisLeapYear(int year) {

return (year%4==0&&year%100!=0) || (year%400==0);

}

private Date increaseOneDay() {

Date result = new Date(this.day, this.month, this.year);

if(result.day < dayInMonth[result.month]) {

result.day += 1;

} else {

if((result.day == 28 || result.day==29) && result.month == 2 && isLeapYear(result.year)) {

if(result.day < 29)

result.day += 1;

else {

result.day = 1;

result.month += 1;

}

} else {

result.day = 1;

if(result.month < 12) {

result.month += 1;

} else {

result.month = 1;

result.year += 1;

}

}

}

returnresult;

}

@Override

publicintcompareTo(Date d) {

int yearCompare = this.year d.year;

int monthCompare = this.month d.month;

int dayCompare = this.day d.day;

return yearCompare != 0 ? yearCompare : monthCompare != 0 ? monthCompare : dayCompare;

}

@Override

public String toString() {

returnthis.day + ” “ + monthNames[this.month] + ” “ + this.year;

}

}

This class with the increaseOneDay method that can be used to solve this problem. We loop from the start day, 1/1/1901 , which is Tuesday, until we reach 31/12/2000. And we check if date.day == 1 and that date is Sunday (or equal 6) .

You got the idea.

Solution took 26 ms.

Implementation:

import java.util.Hashtable;

import java.util.Scanner;

public class Prob19 {

privatestaticclassDate implements Comparable<Date>{

public static final int[] dayInMonth = {0,31,28,31,30,31,30,31,31,30,31,30,31};

public static final String[] monthNames = {“”,“Jan”,“Feb”,“Mar”,“Apr”,“May”,

“jun”,“Jul”,“Aug”,“Sep”,“Oct”,“Nov”,“Dec”};

publicintday;

publicintmonth;

publicintyear;

publicDate(int day, int month, int year) {

this.year = (year >= 1900 ) ? year : 1900;

this.month = (month>=1&&month<=12) ? month : 1;

if(day == 29 && month == 2 && isLeapYear(this.year)) {

this.day = day;

} else {

this.day = day>=1 && day <= dayInMonth[month] ? day : 1;

}

}

publicDate() {

this.day = 1;

this.month = 1;

this.year = 1900;

}

privatestaticbooleanisLeapYear(int year) {

return (year%4==0&&year%100!=0) || (year%400==0);

}

private Date increaseOneDay() {

Date result = new Date(this.day, this.month, this.year);

if(result.day < dayInMonth[result.month]) {

result.day += 1;

} else {

if((result.day == 28 || result.day==29) && result.month == 2 && isLeapYear(result.year)) {

if(result.day < 29)

result.day += 1;

else {

result.day = 1;

result.month += 1;

}

} else {

result.day = 1;

if(result.month < 12) {

result.month += 1;

} else {

result.month = 1;

result.year += 1;

}

}

}

returnresult;

}

@Override

publicintcompareTo(Date d) {

int yearCompare = this.year d.year;

int monthCompare = this.month d.month;

int dayCompare = this.day d.day;

return yearCompare != 0 ? yearCompare : monthCompare != 0 ? monthCompare : dayCompare;

}

@Override

public String toString() {

returnthis.day + ” “ + monthNames[this.month] + ” “ + this.year;

}

}

privatestaticHashtable<Date, String> dayInWeekOfDate = new Hashtable<>();

public static final String[] dayInWeek = {“Monday”,“Tuesday”,“Wednesday”,“Thursday”,

“Friday”,“Sartuday”,“Sunday”};

privatestaticfinalintNUMBER_OF_DAY_IN_WEEK = 7;

publicstaticvoidmain(String[] args) {

Scannerinput = new Scanner(System.in);

int startDay,startMonth,startYear;

int endDay, endMonth,endYear;

int dayOfWeek;

System.out.println(“Enter start date(d,m,yyyy): “);

startDay= input.nextInt();

startMonth= input.nextInt();

startYear= input.nextInt();

System.out.println(“The day of week of start day:(0-6): “);

dayOfWeek= input.nextInt();

System.out.println(“Enter end date(d,m,yyyy): “);

endDay= input.nextInt();

endMonth= input.nextInt();

endYear= input.nextInt();

Date date = new Date(startDay, startMonth, startYear);

int count = dayOfWeek;

dayInWeekOfDate.put(date, dayInWeek[count++]);

int countSundayOnFirstMonth = 0;

Date endDate = new Date(endDay,endMonth,endYear);

while(true) {

date = date.increaseOneDay();

dayInWeekOfDate.put(date, dayInWeek[count]);

if(date.day == 1 && (count+1) == 7) {

++countSundayOnFirstMonth;

}

count = (count+1)%NUMBER_OF_DAY_IN_WEEK;

if(date.compareTo(endDate) == 0) {

System.out.println(countSundayOnFirstMonth);

break;

}

}

}

}

Input/Output:

Enter start date(d,m,yyyy):

1 1 1901

The day of week of start day:(0-6):

1

Enter end date(d,m,yyyy):

31 12 2000

171

## Problem 18: Maximum path sum I

*Difficulty: Easy

Problem:

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)

How to solve:

The ‘pyramid’ above can be rewritten as matrix like this

3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

We can go bottom up or top down, here I’m using top-down mechanism. By looking ahead one step, you can tell that from the current position, either left or right will produce the maximum path sum. Here’s how it works

Step 1: start from line 1 (because we want to one step ahead, we start at one and look back at line 0)

3 0 0 0

10 7 0 0

Step 2: start from line 2

10 7 0 0

12 14 13 0

(12 = 2 + 10,7, 14 = 4 + max(10,7), 13 = 6 + max(7,0))

Step 3: line 3 (also is the last line – the base of the pyramid)

12 14 13 0

20 19 23 16

(20 = 8+12, 19 = 5 + max(12,14), 23 = 8 + max(13,14), 16 = 3 + max(13,0)

We reach the base of the pyramid, each element in this line contains the maximum sum path from top to itself. The last work we need to do is just find the max value from this line. In this case, is 23. Same for the bigger pyramid below

75   0   0   0   0   0   0   0   0   0   0   0   0   0   0

95  64   0   0   0   0   0   0   0   0   0   0   0   0   0

17  47  82   0   0   0   0   0   0   0   0   0   0   0   0

18  35  87  10   0   0   0   0   0   0   0   0   0   0   0

20   4  82  47  65   0   0   0   0   0   0   0   0   0   0

19   1  23  75   3  34   0   0   0   0   0   0   0   0   0

88   2  77  73   7  63  67   0   0   0   0   0   0   0   0

99  65   4  28   6  16  70  92   0   0   0   0   0   0   0

41  41  26  56  83  40  80  70  33   0   0   0   0   0   0

41  48  72  33  47  32  37  16  94  29   0   0   0   0   0

53  71  44  65  25  43  91  52  97  51  14   0   0   0   0

70  11  33  28  77  73  17  78  39  68  17  57   0   0   0

91  71  52  38  17  14  91  43  58  50  27  29  48   0   0

63  66   4  68  89  53  67  30  73  16  69  87  40  31   0

4  62  98  27  23   9  70  98  73  93  38  53  60   4  23

As in implementation code, you just need to input the pyramid as a string format, then it will split up and calculate the level (the height) of the pyramid.

Solution took 0 ms (the chunk of code that find out the biggest path sum, from the beginning, program run ~30ms )

Implementation: Java

public class Prob18 {

privatestaticint[][] pyramid;

privatestaticString input =

“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″;

//”3 7 4 2 4 6 8 5 9 3″;

publicstaticvoidmain(String[] args) {

//create a pyramid with any given input (string)

long cur = System.currentTimeMillis();

int rowLength = 1;

String[] tokens = input.split(” “);

//calculate the size of the pyramid

int a = 1, b = 1, c = tokens.length*2*-1;

int delta = b*b4*a*c;

int size = (b+(int)Math.sqrt(delta))/2*a;

pyramid = new int[size][size];

//get input

int elementAt = 0;

for(int i = 0; i < pyramid.length; ++i) {

for(int j = 0; j < rowLength; ++j) {

pyramid[i][j] = Integer.valueOf(tokens[elementAt]);

++elementAt;

}

++rowLength;

}

//print out the pyramid

for(int i = 0; i < pyramid.length;++i) {

for(int j = 0; j < pyramid.length; ++j)

System.out.printf(“%4d”, pyramid[i][j]);

System.out.println();

}

int maxPathSum = Integer.MIN_VALUE;

//because we look one step ahead, we

//start from i = 1, and look back i-1

rowLength= 2;

for(int i = 1; i < pyramid.length; ++i) {

for(int j = 0; j < rowLength; ++j)

pyramid[i][j] += (j==0) ? pyramid[i1][j]

: Integer.max(pyramid[i1][j], pyramid[i1][j1]);

//get the max sum path from the base of the pyramid

if(i == pyramid.length1) {

for(int j = 0; j < rowLength; ++j)

maxPathSum= Integer.max(maxPathSum, pyramid[i][j]);

break;

}

++rowLength;

}

System.out.println(maxPathSum);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

}

## Problem 17: Number letter counts

*Difficulty: Easy

Problem:

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.

How to solve:

This is what you need to solve this problem

numbers = {“”,“one”,“two”,“three”,“four”,“five”,“six”,“seven”,

“eight”,“nine”,“ten”};

dozens =  {“”,“”,“twenty”,“thirty”,“forty”,“fifty”,“sixty”,

“seventy”, “eighty”, “ninety”};

lessThanTwenty = {“”,“”,“”,“”,“”,“”,“”,“”,“”,“”,“”,“eleven”,“twelve”,“thirteen”,“fourteen”,“fifteen”,“sixteen”,“seventeen”,“eighteen”,“nineteen”};

1 = numbers[1];

10 = numbers[10]

11 = lessThanTwenty[11];

20 = dozens[20/10]

21 = dozens[20/10]+numbers[20%10]

….

You got the idea

Or you could analyze the problem like this

Project Euler 17: Letters in the numbers 1-1000

Solution took 36 ms

Implementation: Java

public class Prob17 {

private static final String[] numbers = {“”,“one”,“two”,“three”,“four”,“five”,“six”,“seven”,

“eight”,“nine”,“ten”};

private static final String[] dozens =  {“”,“”,“twenty”,“thirty”,“forty”,“fifty”,“sixty”,

“seventy”, “eighty”, “ninety”};

privatestaticfinalString[] lessThanTwenty = {

“”,“”,“”,“”,“”,“”,“”,“”,“”,“”,“”,

“eleven”,“twelve”, “thirteen”,“fourteen”,

“fifteen”,“sixteen”,“seventeen”,“eighteen”,“nineteen”};

private static String returnNumberInWords(int n) {

Strings = String.valueOf(n);

StringBuilderresult = new StringBuilder();

if(s.length() == 4)

result.append(“onethousand”);

else{

switch(s.length()) {

case1:

result.append(numbers[n]);

break;

case2:

if(n==10) result.append(numbers[n]);

else if( n < 20) {

result.append(lessThanTwenty[n]);

} else {

result.append(dozens[Integer.valueOf(s.charAt(0)+“”)]);

result.append((n%10!=0 ? numbers[Integer.valueOf(s.charAt(1)+“”)] : “”));

}

break;

case3:

//if(s.charAt(0) == ‘1’)

//result.append(“ahundred“);

//else

result.append(numbers[Integer.valueOf(s.charAt(0)+“”)] + “hundred”);

if(n%100!=0) {

String dozenS = s.substring(1);

int dozenN = Integer.valueOf(dozenS);

result.append(“and”);

if(dozenN <= 10)

result.append(numbers[dozenN]);

else if(dozenN < 20){

result.append(lessThanTwenty[dozenN]);

} else {

result.append(dozens[dozenN/10]);

}

if(dozenN > 20) {

int unit = Integer.valueOf(dozenS.charAt(1)+“”);

result.append(unit!=0 ? numbers[unit] : “”);

}

}

break;

}

}

System.out.println(result.length() + ” – “ + result.toString());

return result.toString();

}

publicstaticvoidmain(String[] args) {

int sum = 0;

int count1_9 = 0;

int count10_19 = 0;

int count20_99 = 0;

int count100_999 = 0;

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

int length =  returnNumberInWords(i).length();

sum+= length;

if(i >= 1 && i < 10) count1_9 += length;

else if(i >= 10 && i < 20) count10_19 += length;

else if(i >= 20 && i < 100) count20_99 += length;

else if(i >= 100 && i < 1000) count100_999 +=length;

}

System.out.println(sum);

System.out.println(“1-9: “ + count1_9

+“\n10-19: ” + count10_19

+“\n20-99: ” + count20_99

+“\n100_999: ” + count100_999);

}

}

## Prob 16: Power digit sum

*Difficulty: Easy

Problem:

215 = 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?

How to solve:

Using BigInteger in Java.

There is no type of data in any programming languages that can store a number having hundreds or thousands digits.
Solution took 6ms

Implementation: Java (Very short)

import java.math.BigInteger;

public class Prob16 {

publicstaticvoidmain(String[] args) {

long cur = System.currentTimeMillis();

Stringresult = BigInteger.valueOf(2).pow(1000).toString();

int sumDigits = 0;

for(int index = 0; index < result.length(); ++index) {

sumDigits+= Integer.valueOf(result.charAt(index)+“”);

}

System.out.println(sumDigits);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

}

## Problem 15: Lattice paths

*Difficulty: Easy

Problem:

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?

How to solve:

First, what is Lattice path?

Lattice Path is a path that lead from one lattice point to the next.

two paths, from the leftmost corner to the rightmost, through a 1×1 lattice

six paths through a 2×2 lattice

Here are the Lattice paths for 4×4 grid

Here is the grid 4×4 in matrix-view

1     1     1     1     1

1     2     3    4     5

1     3     6   10    15

1     4    10  20   35

1     5    15   35   70

What we need is calculating the value at the position (3,3) in the grid, which is 70.

Do we have a formula for this? Like input the size of the grid and instantly got the number of the Lattice paths. The answer is: no, but as you will be showed next, we have a mechanism to calculate the number of the Lattice paths of a nxn size grid, and it runs incredibly fast. (With the brute force approach, this problem cant be solved in an acceptable amount of time with a grid of size just 20, or 30)  .

As you can see :

2 = 1*2, 6 = 3*2, 20 = 10*2, 70 = 35*2

What I want to point out here is from the 0th line, we can compute the value of the next line.

Like this

1     1     1     1     1

Take the second element and multiply it by 2, placing it below the second element:

1     1     1     1     1

——2

Add that to the next element in the above row (2 + 1):

1      1     1     1     1

——2     3

And keep going on going:

1     1     1     1     1

——2     3    4     5

Then work on the third row by taking the second element of the second row (3) and repeating the process, 3 * 2 = 6 hence:

1     1     1     1     1

——2     3    4     5

————6

Take 6 and add it to the next element in the second row (4):

1     1     1     1     1

——2     3    4     5

————6   10

And then take that and add it to the last element in the second row:

1     1     1     1     1

——2     3    4     5

————6   10   15

Continue

1     1     1     1     1

——2     3    4     5

————6   10   15

——————20  35

And finally

1     1     1     1     1

——2     3    4     5

————6   10   15

——————20  35

————————70

This algorithm allows you determine the number of paths from on edge to the other without actually drawing a diagram and manually counting the paths.

Implementation: Java

import java.util.Arrays;

public class Prob15 {

publicstaticvoidmain(String[] args) {

long cur = System.currentTimeMillis();

System.out.println(possibleLatticePath(20));

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

privatestaticlongpossibleLatticePath(int size) {

Long[] firstLine = new Long[size+1];

Arrays.fill(firstLine, 1l);

if(firstLine.length==2) return 2;

do{

if(firstLine.length > 2) {

for(int count = 2; count < firstLine.length; ++count) {

}

firstLine= new Long[nextLine.size()];

nextLine.toArray(firstLine);

}

}while(nextLine.size()>1);

return nextLine.getLast();

}

}

## Problem 14: Longest Collatz sequence

*Difficulty: Easy

Problem:

The following iterative sequence is defined for the set of positive integers:

nn/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.

How to solve:

The only way I can think of is doing exactly as above ,that is, I generate and count how long a Collatz sequence of a number is.

Solution took 465ms

Implementation: Java

public class Prob14 {

private static int maxStartingNumber = Integer.MIN_VALUE;

publicstaticvoidmain(String[] args) {

int n = 2;

int max = Integer.MIN_VALUE;

long cur = System.currentTimeMillis();

int countRepeat = 0;

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

long temp = i;

int chain = 0;

while( temp > 1) {

if (temp % 2 == 0) temp /= 2;

else temp = 3*temp + 1;

++chain;

if(temp <= 1) {

chain++; //add the i value itself

if(chain > max) {

max = chain;

maxStartingNumber= i;

}

break;

}

}

}

System.out.println(max + “, “ + maxStartingNumber);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

}

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r