Archive for the ‘Project Euler’ Category

« Older Entries
Newer Entries »

Project Euler（45）

Posted on Tuesday, January 27th, 2009 at 9:45 pm by Universe Queen

Problem 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, …
Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, …

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Answer: 1533776805

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

import java.math.*;
import java.util.*;
 
public class Euler45 
{
	public static void main(String[] args)
	{
		String result = null;
		Set setPentagonal = new TreeSet();
		Set setHexagonal = new TreeSet();
 
		for( int i=166; i<99999; i++ )
		{
			BigInteger tmp1 = new BigInteger( String.valueOf(i) );
			BigInteger tmp2 =  tmp1.multiply( new BigInteger( String.valueOf(3) ) );
			tmp2 = tmp2.subtract( new BigInteger( String.valueOf(1) ) );
			tmp1 = tmp1.multiply( tmp2 );
			tmp1 = tmp1.divide( new BigInteger( String.valueOf(2) ) );
 
			setPentagonal.add( tmp1.toString() );
		}
 
		for( int i=144; i<99999; i++ )
		{
			BigInteger tmp1 = new BigInteger( String.valueOf(i) );
			BigInteger tmp2 =  tmp1.multiply( new BigInteger( String.valueOf(2) ) );
			tmp2 = tmp2.subtract( new BigInteger( String.valueOf(1) ) );
			tmp1 = tmp1.multiply( tmp2 );
 
			setHexagonal.add( tmp1.toString() );
		}
 
		for( int i=285; i<Integer.MAX_VALUE; i++ )
		{
			BigInteger tmp1 = new BigInteger( String.valueOf(i) );
			tmp1 = tmp1.multiply( tmp1.add( new BigInteger( String.valueOf(1) ) ) );
			tmp1 = tmp1.divide( new BigInteger( String.valueOf(2) ) );
			String tmp = tmp1.toString();
 
			if( setPentagonal.contains(tmp) && setHexagonal.contains(tmp) )
			{
				result = tmp;
				break;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 923 Comments »

Project Euler（44）

Posted on Thursday, January 22nd, 2009 at 9:45 pm by Universe Queen

Problem 44:

Pentagonal numbers are generated by the formula, P_(n)=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P_(4) + P_(7) = 22 + 70 = 92 = P_(8). However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_(j) and P_(k), for which their sum and difference is pentagonal and D = |P_(k) − P_(j)| is minimised; what is the value of D?

Answer: 5482660

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

public class Euler44 
{
	public static boolean isPentagonal( long number )
	{
		number = 24*number+1;
		double s = Math.sqrt(number);
		number = (long)s;
 
		if( s-number > 0.0000001 || s-number < -0.0000001 )
		{
			return false;
		}
 
		number++;
 
		if( number%6 != 0 )
		{
			return false;
		}
 
		return true;		
	}
 
	public static void main(String[] args)
	{
		long result = Long.MAX_VALUE;
		long[] p = new long[20000];
 
		for( int i=0; i<p.length; i++ )
		{
			if( 3*(i+1)-2 > result )
			{
				break;
			}
 
			p[i] = (3*(i+1)-1)*(i+1)/2;
 
			for( int j=0; j<i; j++ )
			{
				long sum = p[i] + p[j];
 
				if( !isPentagonal(sum) )
				{
					continue;
				}
 
				long dif = p[i] - p[j];
 
				if( isPentagonal(dif) && dif < result )
				{
					result = dif;
				}
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 989 Comments »

Project Euler（43）

Posted on Saturday, January 17th, 2009 at 11:54 pm by Universe Queen

Problem 43:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d_(1) be the 1^(st) digit, d_(2) be the 2^(nd) digit, and so on. In this way, we note the following:

* d_(2)d_(3)d_(4)=406 is divisible by 2
* d_(3)d_(4)d_(5)=063 is divisible by 3
* d_(4)d_(5)d_(6)=635 is divisible by 5
* d_(5)d_(6)d_(7)=357 is divisible by 7
* d_(6)d_(7)d_(8)=572 is divisible by 11
* d_(7)d_(8)d_(9)=728 is divisible by 13
* d_(8)d_(9)d_(10)=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Answer: 16695334890

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

public class Euler43 
{
	public static int factory( int n )
	{
		int result = 1;
 
		for( int i=1; i<=n; i++ )
		{
			result *= i;
		}
 
		return result; 
	}
 
	public static String[] getAllCombinations( String s )
	{
		String[] combinations = new String[factory(s.length())];
 
		if( combinations.length == 1 )
		{
			combinations[0] = s;
			return combinations;
		}
 
		int n = factory( s.length() - 1 );
 
		for( int i=0; i<s.length(); i++ )
		{
			String sub;
			String[] subs;
 
			if( i == 0 )
			{
				sub = s.substring( 1 );
			}
			else if( i == s.length()-1 )
			{
				sub = s.substring( 0, s.length()-1 );
			}
			else
			{
				sub = s.substring( 0, i ) + s.substring( i+1 );
			}
 
			subs = getAllCombinations( sub );
 
			for( int j=0; j<subs.length; j++ )
			{
				combinations[i*n+j] = s.charAt(i) + subs[j];
			}		
		}
 
		return combinations;
	}
 
	public static void main(String[] args) 
	{
		long result = 0;
		String[] s = new String[9];
		s[0] = new String( "023456789" );
		s[1] = new String( "013456789" );
		s[2] = new String( "021456789" );
		s[3] = new String( "023156789" );
		s[4] = new String( "023416789" );
		s[5] = new String( "023451789" );
		s[6] = new String( "023456189" );
		s[7] = new String( "023456719" );
		s[8] = new String( "023456781" );
		int tmp;
		String[] ss;
 
		for( int i=0; i<s.length; i++ )
		{
			ss = getAllCombinations( s[i] );
 
			for( int j=0; j<ss.length; j++ )
			{
				ss[j] = String.valueOf(i+1)+ss[j];
 
				tmp = Integer.valueOf( ss[j].substring( 1, 4 ) );
				if( tmp % 2 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 2, 5 ) );
				if( tmp % 3 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 3, 6 ) );
				if( tmp % 5 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 4, 7 ) );
				if( tmp % 7 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 5, 8 ) );
				if( tmp % 11 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 6, 9 ) );
				if( tmp % 13 != 0 )
				{
					continue;
				}
 
				tmp = Integer.valueOf( ss[j].substring( 7, 10 ) );
				if( tmp % 17 == 0 )
				{
					result += Long.valueOf( ss[j] );
				}
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 903 Comments »

Project Euler（42）

Posted on Monday, January 12th, 2009 at 7:04 pm by Universe Queen

Problem 42:

The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t_(10). If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Answer: 162

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

import java.io.BufferedReader;
import java.io.FileReader;
 
public class Euler42 
{
	public static boolean isTriangleWords( String s )
	{
		int number = 0;
 
		for( int i=0; i<s.length(); i++ )
		{
			number += s.charAt(i) - 'A' + 1;
		}
 
		int n = (int)Math.floor( Math.sqrt( number*2 ) );
 
		if( n*(n+1) == number*2 )
		{
			return true;
		}
 
		return false;
	}
 
	public static void main(String[] args)  throws Exception
	{
		int result = 0;
		try
		{
			BufferedReader r = new BufferedReader( new FileReader("words.txt") );		
			String[] s = r.readLine().split(",");
			for( int i=0; i<s.length; i++ )
			{
				s[i] = s[i].substring( 1, s[i].length()-1 );
 
				if( isTriangleWords( s[i] ) )
				{
					result++;
				}
			}
		}
		catch ( Exception e ) 
		{
			throw e;  
		}	
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 338 Comments »

Project Euler（41）

Posted on Monday, January 12th, 2009 at 6:30 pm by Universe Queen

Problem 41:

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, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

Answer: 7652413

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

public class Euler41 
{
	public static boolean isPrime( int 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 int factory( int n )
	{
		int result = 1;
 
		for( int i=1; i<=n; i++ )
		{
			result *= i;
		}
 
		return result; 
	}
 
	public static int[] getPandigits( int bitLength )
	{
		String s = String.valueOf(bitLength);
 
		for( int i=bitLength-1; i>=1; i-- )
		{
			s += String.valueOf( i );
		}
 
		String[] strings = getAllCombinations( s );
		int[] numbers = new int[strings.length];
 
		for( int i=0; i<strings.length; i++ )
		{
			numbers[i] = Integer.valueOf( strings[i] );
		}
 
		return numbers;
	}
 
	public static String[] getAllCombinations( String s )
	{
		String[] combinations = new String[factory(s.length())];
 
		if( combinations.length == 1 )
		{
			combinations[0] = s;
			return combinations;
		}
 
		int n = factory( s.length() - 1 );
 
		for( int i=0; i<s.length(); i++ )
		{
			String sub;
			String[] subs;
 
			if( i == 0 )
			{
				sub = s.substring( 1 );
			}
			else if( i == s.length()-1 )
			{
				sub = s.substring( 0, s.length()-1 );
			}
			else
			{
				sub = s.substring( 0, i ) + s.substring( i+1 );
			}
 
			subs = getAllCombinations( sub );
 
			for( int j=0; j<subs.length; j++ )
			{
				combinations[i*n+j] = s.charAt(i) + subs[j];
			}		
		}
 
		return combinations;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
		boolean find = false;
 
		for( int i=9; i>0; i-- )
		{
			int[] numbers = getPandigits( i );
 
			for( int j=0; j<numbers.length; j++ )
			{
				if( isPrime( numbers[j] ) )
				{
					result = numbers[j];
					find = true;
					break;
				}
			}
 
			if( find )
			{
				break;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 213 Comments »

Project Euler（40）

Posted on Sunday, January 11th, 2009 at 10:11 pm by Universe Queen

Problem 40:

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the 12^(th) digit of the fractional part is 1.

If d_(n) represents the n^(th) digit of the fractional part, find the value of the following expression.

d_(1) × d_(10) × d_(100) × d_(1000) × d_(10000) × d_(100000) × d_(1000000)

Answer: 210

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

public class Euler40 
{
	public static void main(String[] args) 
	{
		int result = 1;
		char[] number = new char[1000000];
		String s;
		int n = 1;
		int index = 0;
 
		while( index < number.length )
		{
			s = String.valueOf( n );
 
			for( int i=0; i<s.length(); i++ )
			{
				if( index + i >= number.length )
				{
					break;
				}
 
				number[index+i] = s.charAt(i);
			}
 
			index += s.length();
			n++;
		}
 
		for( n=1; n<=1000000; n*=10 )
		{
			result *= ( number[n-1] - '0' );
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 392 Comments »

Project Euler（39）

Posted on Sunday, January 11th, 2009 at 9:45 pm by Universe Queen

Problem 39:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Answer: 840

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 Euler39 
{
	public static int numberOfSolutions( int p )
	{
		int a;
		int b;
		int c;
		int counter = 0;
 
		for( a=1; a<p/3; a++ )
		{
			for( b=a; b<(p-a)/2; b++ )
			{
				c = p - a - b;
 
				if( a*a + b*b == c*c )
				{
					counter++;
				}
			}
		}
 
		return counter;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
		int tmp;
		int max = 0;
 
		for( int p=3; p<=1000; p++ )
		{
			tmp = numberOfSolutions( p );
 
			if( tmp > max )
			{
				max = tmp;
				result = p;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 423 Comments »

Project Euler（38）

Posted on Saturday, January 10th, 2009 at 9:22 pm by Universe Queen

Problem 38:

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

Answer: 932718654

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

public class Euler38 
{
	public static boolean is9BitsPandigital( String number )
	{
		if( number.length() != 9 )
		{
			return false;
		}
 
		for( int i=number.length()-1; i>=0; i-- )
		{
			for( int j=0; j<i; j++ )
			{
				if( number.charAt(i) == number.charAt(j) || number.charAt(i) == '0' || number.charAt(j) == '0' )
				{
					return false;
				}
			}
		}
 
		return true;
 
	}
 
	public static String getPandigital( int number )
	{
		String s = String.valueOf( number );
		int counter = 2;
 
		while( s.length() < 9 )
		{
			s += String.valueOf( number*counter );
			counter++;
		}
 
		if( is9BitsPandigital(s) )
		{
			return s;
		}
 
		return null;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
		String s;
		int tmp;
 
		for( int i=1; i<99999; i++ )
		{
			s = getPandigital( i );
 
			if( s != null )
			{
				tmp = Integer.valueOf( s );
 
				if( tmp > result )
				{
					result = tmp;
				}
			}
		}
 
		System.out.println( result );
	}
}

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

Project Euler（37）

Posted on Wednesday, January 7th, 2009 at 9:42 pm by Universe Queen

Problem 37:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Answer: 748317

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

public class Euler37 
{
	public static boolean isPrime( int 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 boolean isTruncatable ( int number )
	{
		String s = String.valueOf( number );
		String sub;
 
		for( int i=0; i<s.length(); i++ )
		{
			sub = s.substring( i );
 
			if( !isPrime(Integer.valueOf(sub)) )
			{
				return false;
			}
		}
 
		for( int i=s.length(); i>0; i-- )
		{
			sub = s.substring( 0, i );
 
			if( !isPrime(Integer.valueOf(sub)) )
			{
				return false;
			}
		}
 
		return true;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
		int counter = 0;
		int i = 8;
 
		while( true )
		{
			if( isTruncatable(i) )
			{
				result += i;
				counter++;
			}
 
			if( counter == 11 )
			{
				break;
			}
 
			i++;
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 448 Comments »

Project Euler（36）

Posted on Wednesday, January 7th, 2009 at 9:13 pm by Universe Queen

Problem 36:

The decimal number, 585 = 1001001001_(2) (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Answer: 872187

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

public class Euler36 
{	
	public static boolean isPalindromic( int number )
	{
		String s = String.valueOf( number );
 
		for( int i=0; i<s.length()/2; i++ )
		{
			if( s.charAt(i) != s.charAt(s.length()-1-i) )
			{
				return false;
			}
		}
 
		s = Integer.toBinaryString( number );
 
		for( int i=0; i<s.length()/2; i++ )
		{
			if( s.charAt(i) != s.charAt(s.length()-1-i) )
			{
				return false;
			}
		}
 
		return true;
	}
 
	public static void main(String[] args) 
	{
		int result = 0;
 
		for( int i=1; i<1000000; i++ )
		{
			if( isPalindromic(i) )
			{
				result += i;
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 442 Comments »

« Older Entries
Newer Entries »