Posted on Tuesday, December 16th, 2008 at 11:00 pm by Universe Queen
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 first term in the Fibonacci sequence to contain 1000 digits?
Answer: 4782
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.math.*;
public class Euler25
{
public static void main(String[] args)
{
BigInteger current = BigInteger.valueOf(1);
BigInteger pre = BigInteger.valueOf(1);
BigInteger tmp;
String s;
int result = 2;
while(true)
{
tmp = current.add(pre);
pre = current;
current = tmp;
s = current.toString();
result++;
if( s.length() >= 1000 )
{
break;
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（25）" | 616 Comments »
Posted on Tuesday, December 16th, 2008 at 10:40 pm by Universe Queen
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?
Answer: 2783915460
Explanation: When you run the program, maybe you need to add “-Xms128m -Xmx640m -XX:MaxPermSize=256M” as the VM argument to overcome “Exception in thread “main” java.lang.OutOfMemoryError: Java heap space”. In eclipse, you should click Run–>Run Configurations–>(x)= Arguments and add the argument.
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public class Euler24
{
public static String[] permutations( String digits )
{
String[] result;
String[] resultSub;
String digitsSub;
int n = 1;
for( int i=1; i<=digits.length(); i++ )
{
n *= i;
}
result = new String[n];
if( n == 1 )
{
result[0] = digits;
return result;
}
for( int i=0; i<digits.length(); i++ )
{
digitsSub = digits.substring(0,i)+digits.substring(i+1);
resultSub = permutations( digitsSub );
for( int j=0; j<resultSub.length; j++ )
{
result[i*resultSub.length+j] = digits.charAt(i) + resultSub[j];
}
}
return result;
}
public static void main(String[] args)
{
String[] result = permutations("0123456789");
System.out.println( result[999999] );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（24）" | 417 Comments »
Posted on Tuesday, December 16th, 2008 at 8:59 pm by Universe Queen
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 whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.
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.
Answer: 4179871
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| import java.util.*;
public class Euler23
{
public static boolean isAbundant( int n )
{
int sum = 0;
for( int i=1; i<n; i++ )
{
if( n%i == 0 )
{
sum += i;
}
}
if( sum > n )
{
return true;
}
return false;
}
public static void main(String[] args)
{
int result = 0;
int[] numbers = new int[28123];
ArrayList abundants = new ArrayList();
for( int i=0; i<numbers.length; i++ )
{
numbers[i] = i+1;
result += numbers[i];
if( isAbundant(numbers[i]) )
{
abundants.add( numbers[i] );
}
}
for( int i=0; i<abundants.size(); i++ )
{
for( int j=i; j<abundants.size(); j++ )
{
int index = (Integer)abundants.get(i) + (Integer)abundants.get(j) - 1;
if( index < numbers.length )
{
result -= numbers[index];
numbers[index] = 0;
}
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（23）" | 138 Comments »
Posted on Saturday, December 13th, 2008 at 7:51 pm by Universe Queen
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?
Answer: 871198282
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| import java.io.BufferedReader;
import java.io.FileReader;
import java.util.*;
public class Euler22
{
public static void main(String[] args) throws Exception
{
int result = 0;
BufferedReader r = new BufferedReader( new FileReader("names.txt") );
String s = r.readLine();;
int score = 0;
String[] names = s.split(",");
for( int i=0; i<names.length; i++ )
{
names[i] = names[i].substring( 1, names[i].length()-1 );
}
Arrays.sort(names);
for( int i=0; i<names.length; i++ )
{
score = 0;
for( int j=0; j<names[i].length(); j++ )
{
score += (names[i].charAt(j) - 'A') + 1;
}
result += score*(i+1);
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（22）" | 315 Comments »
Posted on Saturday, December 13th, 2008 at 7:08 pm by Universe Queen
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.
Answer: 31626
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class Euler21
{
public static int d( int n )
{
int result = 0;
for( int i=1; i<n; i++ )
{
if( n%i == 0 )
{
result += i;
}
}
return result;
}
public static void main(String[] args)
{
int result = 0;
int tmp;
for( int i=1; i<10000; i++ )
{
tmp = d(i);
if( i == d(tmp) && i != tmp )
{
result += i;
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（21）" | 92 Comments »
Posted on Monday, December 8th, 2008 at 9:56 pm by Universe Queen
Problem 20:
n! means n × (n − 1) × … × 3 × 2 × 1
Find the sum of the digits in the number 100!
Answer: 648
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.math.*;
public class Euler20
{
public static void main(String[] args)
{
int result = 0;
BigInteger b = BigInteger.valueOf(1);
String s;
for( int i=2; i<=100; i++ )
{
b = b.multiply( BigInteger.valueOf(i) );
}
s = b.toString();
for( int i=0; i<s.length(); i++ )
{
result += Integer.valueOf(s.charAt(i)-'0');
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（20）" | 132 Comments »
Posted on Monday, December 8th, 2008 at 9:31 pm by Universe Queen
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)?
Answer: 171
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| public class Euler19
{
public static boolean isLeapYear( int year )
{
if( year/400 == 0 )
{
return true;
}
else if( year/100 == 0 )
{
return false;
}
else if( year/4 == 0 )
{
return true;
}
else
{
return false;
}
}
public static void main(String[] args)
{
int result = 0;
int year = 1900;
int month = 1;
int[] monthsDaysNumber = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int weekday = 1;
for( ; year<=2000; year++ )
{
for( ; month<=12; month++ )
{
int daysNumber = monthsDaysNumber[month];
if( month == 2 && isLeapYear(year) )
{
daysNumber++;
}
for( int i=0; i<daysNumber; i++ )
{
if( year > 1900 && i == 0 && weekday == 7 )
{
result++;
}
weekday++;
if( weekday > 7 )
{
weekday = 1;
}
}
}
month = 1;
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（19）" | 511 Comments »
Posted on Saturday, December 6th, 2008 at 12:11 am by Universe Queen
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 5
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)
Answer: 1074
Problem 67:
Find the maximum total from top to bottom in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
Answer: 7273
Explanation: The method I used to solve this problem is called Dynamic Programming. But I think a slightly changed Dijkstra’s Algorithm can also deal with this problem.
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| import java.io.BufferedReader;
import java.io.FileReader;
public class Euler18
{
public static void main(String[] args) throws Exception
{
int result = 0;
int rowsNumber = 100;
int[][] numbers = new int[rowsNumber][(rowsNumber-1)*2+1];
int[][] qValues = new int[rowsNumber][(rowsNumber-1)*2+1];
int[][] preQValues = new int[rowsNumber][(rowsNumber-1)*2+1];
for( int i=0; i<numbers.length; i++ )
{
for( int j=0; j<numbers[i].length; j++ )
{
numbers[i][j] = 0;
qValues[i][j] = 0;
preQValues[i][j] = 0;
}
}
try
{
BufferedReader r = new BufferedReader( new FileReader("triangle.txt") );
String[] s;
for( int i=0; i<numbers.length; i++ )
{
int j=numbers.length-1-i;
s = r.readLine().split(" ");
for( int k=0; k<s.length; k++ )
{
numbers[i][j] = Integer.parseInt( s[k] );
j += 2;
}
}
}
catch ( Exception e )
{
throw e;
}
boolean converge = true;
do
{
for( int i=0; i<qValues.length; i++ )
{
for( int j=0; j<qValues[i].length; j++ )
{
if( i == qValues.length-1 )
{
qValues[i][j] = numbers[i][j];
}
else
{
if( numbers[i][j] != 0 )
{
if( preQValues[i+1][j-1] > preQValues[i+1][j+1] )
{
qValues[i][j] = numbers[i][j] + preQValues[i+1][j-1];
}
else
{
qValues[i][j] = numbers[i][j] + preQValues[i+1][j+1];
}
}
}
}
}
converge = true;
for( int i=0; i<qValues.length; i++ )
{
for( int j=0; j<qValues[i].length; j++ )
{
if( preQValues[i][j] != qValues[i][j] )
{
converge = false;
for( int m=0; m<qValues.length; m++ )
{
for( int n=0; n<qValues[m].length; n++ )
{
preQValues[m][n] = qValues[m][n];
}
}
break;
}
}
if( !converge )
{
break;
}
}
}
while(!converge);
result = qValues[0][qValues.length-1];
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（18）&（67）" | 1,028 Comments »
Posted on Monday, December 1st, 2008 at 7:19 pm by Universe Queen
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.
Answer: 21124
By the way, you can see all the numbers in words here. And if you are not sure how to say numbers in English, you can look at here.
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| public class Euler17
{
public static String numberTransfer( int number )
{
String s = null;
if( number <= 19 && number >=1 )
{
switch( number )
{
case 1: s = "one";break;
case 2: s = "two";break;
case 3: s = "three";break;
case 4: s = "four";break;
case 5: s = "five";break;
case 6: s = "six";break;
case 7: s = "seven";break;
case 8: s = "eight";break;
case 9: s = "nine";break;
case 10: s = "ten";break;
case 11: s = "eleven";break;
case 12: s = "twelve";break;
case 13: s = "thirteen";break;
case 14: s = "fourteen";break;
case 15: s = "fifteen";break;
case 16: s = "sixteen";break;
case 17: s = "seventeen";break;
case 18: s = "eighteen";break;
case 19: s = "nineteen";break;
}
}
else if( number == 20 )
{
s = "twenty";
}
else if( number >= 20 && number <= 29 )
{
number -= number/10*10;
s = "twenty-"+ numberTransfer( number );
}
else if( number == 30 )
{
s = "thirty";
}
else if( number >= 31 && number <= 39 )
{
number -= number/10*10;
s = "thirty-"+ numberTransfer( number );
}
else if( number == 40 )
{
s = "forty";
}
else if( number >= 41 && number <= 49 )
{
number -= number/10*10;
s = "forty-"+ numberTransfer( number );
}
else if( number == 50 )
{
s = "fifty";
}
else if( number >= 51 && number <= 59 )
{
number -= number/10*10;
s = "fifty-"+ numberTransfer( number );
}
else if( number == 60 )
{
s = "sixty";
}
else if( number >= 61 && number <= 69 )
{
number -= number/10*10;
s = "sixty-"+ numberTransfer( number );
}
else if( number == 70 )
{
s = "seventy";
}
else if( number >= 71 && number <= 79 )
{
number -= number/10*10;
s = "seventy-"+ numberTransfer( number );
}
else if( number == 80 )
{
s = "eighty";
}
else if( number >= 81 && number <= 89 )
{
number -= number/10*10;
s = "eighty-"+ numberTransfer( number );
}
else if( number == 90 )
{
s = "ninety";
}
else if( number >= 91 && number <= 99 )
{
number -= number/10*10;
s = "ninety-"+ numberTransfer( number );
}
else if( number == 100 || number == 200 || number == 300 || number == 400 || number == 500 || number == 600 || number == 700 || number == 800 || number == 900 )
{
number /= 100;
s = numberTransfer( number ) + " hundred";
}
else if( number >= 101 && number <= 999 )
{
int h = number/100;
number = number - h*100;
s = numberTransfer( h ) + " hundred and " + numberTransfer( number );
}
else if( number == 1000 )
{
s = "one thousand";
}
else if( number >=1000 && number <= 9999 )
{
int t = number/1000;
number = number - t*1000;
s = numberTransfer( t ) + " thousand " + numberTransfer( number );
}
else
{
s = "ERROR";
}
return s;
}
public static void main(String[] args)
{
int result = 0;
String s;
for( int i=1; i<=1000; i++ )
{
s = numberTransfer( i );
for( int j=0; j<s.length(); j++ )
{
if( s.charAt(j) != ' ' && s.charAt(j) != '-' )
{
result++;
}
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（17）" | 910 Comments »
Posted on Monday, December 1st, 2008 at 12:42 am by Universe Queen
Problem 16:
2E15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2E1000?
Answer: 1366
By the way 2E1000 is:
1071508607186267320948425049060001810561404811705533607443750388370351051124936
122493198378815695858127594672917553146825187145285692314043598457757469857480393
456777482423098542107460506237114187795418215304647498358194126739876755916554394
6077062914571196477686542167660429831652624386837205668069376
Implementation in Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public class Euler16
{
public static void main(String[] args)
{
int result = 0;
int[] n = new int[302];
int b = 0;
int currnetcarry = 0;
int nextcarry = 0;
for( int i=0; i<n.length; i++ )
{
n[i] = 0;
}
n[0] = 2;
for( int i=1; i<=999; i++ )
{
for( int j=0; j<=b; j++ )
{
n[j] *= 2;
if( n[j] >= 10 )
{
nextcarry = 1;
n[j] -= 10;
}
else
{
nextcarry = 0;
}
n[j] += currnetcarry;
if( n[j] >= 10 )
{
nextcarry++;
n[j] -= 10;
}
currnetcarry = nextcarry;
}
if( nextcarry > 0 )
{
b++;
n[b] = 1;
}
currnetcarry = 0;
}
for( int i=n.length-1; i>=0; i-- )
{
result += n[i];
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（16）" | 166 Comments »
