Archive for December, 2008

« Older Entries

Project Euler（32）

Posted on Wednesday, December 31st, 2008 at 9:15 pm by Universe Queen

Problem 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigitial.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Answer: 45228

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

import java.util.*;
 
public class Euler32 
{
	public static boolean isRepeat( int n )
	{
		String s = String.valueOf( n );
 
		for( int i=s.length()-1; i>=0; i-- )
		{
			for( int j=0; j<i; j++ )
			{
				if( s.charAt(i) == s.charAt(j) || s.charAt(i) == '0' || s.charAt(j) == '0' )
				{
					return true;
				}
			}
		}
 
		return false;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
		Set set = new TreeSet();
		String tmp;
		int r;
 
		for( int a=1; a<=98765; a++ )
		{
			if( isRepeat(a) )
			{
				continue;
			}
 
			for( int b=1; b<=98765; b++ )
			{
				if( isRepeat(b) )
				{
					continue;
				}
 
				tmp = String.valueOf(a) + String.valueOf(b);
 
				if( tmp.length() > 5 )
				{
					break;
				}
 
				if( isRepeat( Integer.valueOf(tmp) ) )
				{
					continue;
				}
 
				r = a * b;
 
				if( isRepeat( r ) )
				{
					continue;
				}
 
				tmp = tmp + String.valueOf(r);
 
				if( tmp.length() != 9 )
				{
					continue;
				}
 
				if( !isRepeat( Integer.valueOf(tmp) ) )
				{
					set.add( r );
				}
			}
		}
 
		Iterator it = set.iterator();
 
		while( it.hasNext() )
		{
			result += (Integer)(it.next());
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 322 Comments »

Project Euler（31）

Posted on Wednesday, December 31st, 2008 at 8:10 pm by Universe Queen

Problem 31:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Answer: 73682

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

public class Euler31 
{
	public static void main(String[] args) 
	{		
		int result = 0;
		int target = 200;
		int[] m = { 1, 2, 5, 10, 20, 50, 100 };
		int[] i = { 0, 0, 0, 0, 0, 0, 0 };
		int[] n = { 0, 0, 0, 0, 0, 0, 0 };
 
		while( true )
		{
			n[6] = m[6]*i[6];
 
			if( n[6] > target )
			{
				break;
			}
 
			while( true )
			{
				n[5] = n[6] + m[5]*i[5];
 
				if( n[5] > target )
				{
					break;
				}
 
				while( true )
				{
					n[4] = n[5] + m[4]*i[4];
 
					if( n[4] > target )
					{
						break;
					}
 
					while( true )
					{
						n[3] = n[4] + m[3]*i[3];
 
						if( n[3] > target )
						{
							break;
						}
 
						while( true )
						{
							n[2] = n[3] + m[2]*i[2];
 
							if( n[2] > target )
							{
								break;
							}
 
							while( true )
							{
								n[1] = n[2] + m[1]*i[1];
 
								if( n[1] > target )
								{
									break;
								}
 
								while( true )
								{
									n[0] = n[1] + m[0]*i[0];
 
									if( n[0] > target )
									{
										break;
									}
									else if( n[0] == target )
									{
										result++;
										break;
									}
 
									i[0]++;
								}
 
								i[1]++;
								i[0]=0;
							}
 
							i[2]++;
							i[1]=i[0]=0;
						}
 
						i[3]++;
						i[2]=i[1]=i[0]=0;
					}
 
					i[4]++;
					i[3]=i[2]=i[1]=i[0]=0;
				}
 
				i[5]++;
				i[4]=i[3]=i[2]=i[1]=i[0]=0;
			}
 
			i[6]++;
			i[5]=i[4]=i[3]=i[2]=i[1]=i[0]=0;
		}
 
		result++;
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 200 Comments »

Project Euler（30）

Posted on Monday, December 29th, 2008 at 8:57 pm by Universe Queen

Problem 30:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^(4) + 6^(4) + 3^(4) + 4^(4)
8208 = 8^(4) + 2^(4) + 0^(4) + 8^(4)
9474 = 9^(4) + 4^(4) + 7^(4) + 4^(4)

As 1 = 1^(4) is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Answer: 443839

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

public class Euler30 
{
	public static boolean isOK( int number )
	{
		int n = number;
		int r = 0;
		int tmp;
 
		while( n > 0 )
		{
			tmp = n%10;
			int v = 1;
 
			for( int i=0; i<5; i++ )
			{
				v *= tmp;
			}
 
			r += v;
			n /= 10;
		}
 
		if( number == r )
		{
			return true;
		}
 
		return false;
	}
 
	public static void main(String[] args) 
	{		
		int result = 0;
 
		for( int i=2; i<354294; i++ )
		{
			if( isOK(i) )
			{
				result += i;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 388 Comments »

Project Euler（29）

Posted on Sunday, December 28th, 2008 at 11:42 pm by Universe Queen

Problem 29:

Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(5)=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Answer: 9183

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

import java.math.*;
import java.util.*;
 
public class Euler29 
{
	public static void main(String[] args) 
	{		
		int result;
		BigInteger n;
		BigInteger e;
		Set set = new TreeSet();
 
		for(int a=2; a<=100; a++ )
		{
			for(int b=2; b<=100; b++ )
			{
				n = new BigInteger(String.valueOf(a));
				e = new BigInteger(String.valueOf(a));
 
				for( int i=0; i<b-1; i++ )
				{
					e = e.multiply(n);
				}
 
				set.add( e.toString() );
			}
		}
 
		result = set.size();
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 690 Comments »

Project Euler（28）

Posted on Thursday, December 25th, 2008 at 9:18 pm by Universe Queen

Problem 28:

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

Answer: 669171001

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

public class Euler28 
{
	public static void main(String[] args) 
	{
		int result = 0;		
		int[][] spiral = new int[1001][1001];
 
		int x = spiral[0].length/2;
		int y = spiral.length/2;
		int length = 2;
		int directionChangeCounter = 1;
		int direction = 0;
		int n = 1;
 
		spiral[x][y] = n;
 
		while(true)
		{
			if( n+1 > spiral.length*spiral[0].length )
			{
				break;
			}
 
			if( n == length*length )
			{
				length++;
			}
 
			if( directionChangeCounter == length )
			{
				if( direction == 3 )
				{
					direction = 0;
				}
				else
				{
					direction++;
				}
 
				directionChangeCounter = 1;
			}
 
			switch(direction)
			{
			case 0:
				y++;
				break;
			case 1:
				x++;
				break;
			case 2:
				y--;
				break;
			case 3:
				x--;
				break;
			}
 
			n++;		
			spiral[x][y] = n;
			directionChangeCounter++;
		}
 
		for( int i=0; i<spiral.length; i++ )
		{	
			result += spiral[i][i];
			result += spiral[spiral[i].length-i-1][i];
		}
 
		result--;
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 421 Comments »

Project Euler（27）

Posted on Thursday, December 25th, 2008 at 8:25 pm by Universe Queen

Problem 27:

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + 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.

Answer: -59231

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 Euler27 
{
	public static boolean isPrime( long number )
	{
		if( number < 2 )
		{
			return false;
		}
		else if ( number == 2 )
		{
			return true;
		}
		else
		{
			for( long i=2; i<=Math.sqrt(number); i++ )
			{
				if( number%i == 0 )
				{
					return false;
				}
			}
		}
 
		return true;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;		
		int max = 0;
 
		for( int a=-999; a<=999; a++ )
		{
			for( int b=-999; b<=999; b++ )
			{
				int n = 0;
				int number = 0;
 
				while(true)
				{
					number = n*n + a*n + b;
 
					if( !isPrime(number) )
					{
						break;
					}
 
					n++;
				}
 
				if( n > max )
				{
					max = n;
					result = a * b;
				}
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 578 Comments »

Project Euler（26）

Posted on Thursday, December 25th, 2008 at 7:53 pm by Universe Queen

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.

Answer: 983

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

public class Euler26 
{
	public static int lengthOfRecurringCycle( int n )
	{
		int[] quotients = new int[1000];
		int[] remainders = new int[1000];
 
		remainders[0] = 1;
		quotients[0] = 0;
 
		for( int i=1; i<quotients.length; i++ )
		{
			quotients[i] = remainders[i-1]*10/n;
			remainders[i] = remainders[i-1]*10 - quotients[i]*n;
 
			for( int j=1; j<i; j++ )
			{
				if( quotients[j] == quotients[i] && remainders[j] == remainders[i] )
				{
					return (i-j);
				}
			}
 
		}
 
		return -1;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;		
		int maxLength = 0;
		int length;
 
		for( int i=1; i<1000; i++ )
		{
			length = lengthOfRecurringCycle(i);
 
			if( length > maxLength )
			{
				result = i;
				maxLength = length;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 1,319 Comments »

Project Euler（25）

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:
Posted in Project Euler | 1,678 Comments »

Project Euler（24）

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:
Posted in Project Euler | 667 Comments »

Project Euler（23）

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:
Posted in Project Euler | 396 Comments »

« Older Entries