Archive for May, 2009

Project Euler（51）

Posted on Wednesday, May 27th, 2009 at 5:16 am by Universe Queen

Problem 51:

By replacing the 1^(st) digit of *57, it turns out that six of the possible values: 157, 257, 457, 557, 757, and 857, are all prime.

By replacing the 3^(rd) and 4^(th) digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

Answer: 121313

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

public class Euler51 
{
	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[][] getCombinations( int n, int[] array  )
	{	
		int[][] result;
 
		if( n == 1 )
		{
			result = new int[array.length][1];
 
			for( int i=0; i<array.length; i++ )
			{
				result[i][0] = array[i];
			}
		}
		else if( n == array.length )
		{
			result = new int[1][];
 
			result[0] = array.clone();
		}
		else	
		{
			int numberOfCombinations = factory(array.length) / ( factory(n) * factory(array.length-n) );
			result = new int[numberOfCombinations][n];
			int index = 0;
 
			for( int i=0; i<=array.length-n; i++ )
			{
				int[] a = new int[array.length-i-1];
 
				for( int j=0; j<a.length; j++ )
				{
					a[j] = array[i+1+j];
				}
 
				int[][] left = getCombinations( n-1, a );
 
				for( int j=0; j<left.length; j++ )
				{
					result[index][0] = array[i];
 
					for( int m=0; m<left[j].length; m++ )
					{
						result[index][m+1] = left[j][m];
					}
 
					index++;
				}
			}
		}
 
		return result;
	}
 
	public static void main(String[] args)
	{
		int result = 0;
		int counter = 0;
 
		while( true )
		{
			if( isPrime( result ) )
			{
				String number = String.valueOf( result );
 
				for( int numberOfSameDigiters=2; numberOfSameDigiters<=number.length(); numberOfSameDigiters++ )
				{
					for( int index=0; index<=number.length()-numberOfSameDigiters; index++ )
					{
						if( number.charAt( index ) - '0' > 2 )
						{
							continue;
						}
 
						int[] indexes;
						int c = 0;
 
						for( int i=index+1; i<number.length(); i++ )
						{
							if( number.charAt(i) == number.charAt(index) )
							{
								c++;
							}
						}
 
						indexes = new int[c];
						c = 0;
 
						for( int i=index+1; i<number.length(); i++ )
						{
							if( number.charAt(i) == number.charAt(index) )
							{
								indexes[c] = i;
								c++;
							}
						}
 
						int[][] p = getCombinations( numberOfSameDigiters-1, indexes );
 
						for( int m=0; m<p.length; m++ )
						{
							int v = number.charAt(index) - '0' + 1;
							char[] s = new String( number ).toCharArray();
 
							while( v <= 9 )
							{
								char z = (char)(v + '0');
								s[0] = z;
 
								for( int b=0; b<p[m].length; b++ )
								{
									s[p[m][b]] = z;
								}
 
								int y = Integer.valueOf( new String(s) );
 
								if( isPrime(y) )
								{
									counter++;
								}
 
								v++;
							}
 
							if( counter >= 7 )
							{
								System.out.println( result );
								return;
							}
							else
							{
								counter = 0;
							}
						}
 
					}
				}
			}
 
			result++;
		}		
	}
}

Tags:
Posted in Project Euler | 493 Comments »

Project Euler（50）

Posted on Sunday, May 24th, 2009 at 2:49 am by Universe Queen

Problem 50:

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Answer: 997651

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

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
 
 
public class Euler50 
{
	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 void main(String[] args)
	{
		int result = 0;
		int maxLength = 0;
		Set primers = new TreeSet();
 
		for( int i=2; i<1000000; i++ )
		{
			if( isPrime(i) )
			{
				primers.add( i );
			}
		}
 
		Integer[] p = (Integer[])primers.toArray(new Integer[primers.size()]);
 
		for( int i=0; i<p.length; i++ )
		{
			long tmp = 0;
 
			for( int k=i; k<p.length; k++ )
			{
				tmp += p[k];
			}
 
			for( int j=p.length-1; j>i; j-- )
			{
				if( tmp < 1000000 && isPrime((int)tmp) && (j-i) >= maxLength )
				{
					maxLength = j - i;
					result = (int)tmp;
					break;
				}
 
				tmp -= p[j];
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 681 Comments »

Project Euler（49）

Posted on Saturday, May 23rd, 2009 at 5:19 am by Universe Queen

Problem 49:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Answer: 296962999629

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

import java.util.*;
 
public class Euler49 
{
	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 isPermutation( int n1, int n2 )
	{
		boolean result = true;
		String s1 = String.valueOf( n1 );
		String s2 = String.valueOf( n2 );
 
		for( int i=0; i<s1.length(); i++ )
		{
			if( !s2.contains( String.valueOf( s1.charAt(i) ) ) )
			{
				result = false;
			}
		}
 
		for( int i=0; i<s2.length(); i++ )
		{
			if( !s1.contains( String.valueOf( s2.charAt(i) ) ) )
			{
				result = false;
			}
		}
 
		return result;
	}
 
	public static void main(String[] args)
	{
		String result = null;
		Set smallerPrimers = new TreeSet();
		boolean find = false;
 
		for( int i=1000; i<10000; i++ )
		{
			if( isPrime(i) )
			{
				Iterator it = smallerPrimers.iterator();
 
				while( it.hasNext() )
				{
					int pre = (Integer)(it.next());
 
					if( isPermutation( pre, i ) )
					{
						int next = i + ( i - pre );
 
						if( isPrime( next ) && isPermutation( i, next ) && next < 10000 )
						{
							result = String.valueOf( pre ) + String.valueOf( i ) + String.valueOf( next );
							find = true;
							break;
						}
					}
				}
 
				if( find && i != 4817 )
				{
					break;
				}
				else
				{
					find = false;
				}
 
				smallerPrimers.add( i );
			}
		}
 
		System.out.println( result );
	}
}

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

Project Euler（48）

Posted on Saturday, May 23rd, 2009 at 4:33 am by Universe Queen

Problem 48:

The series, 1^(1) + 2^(2) + 3^(3) + … + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + … + 1000^(1000).

Answer: 9110846700

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

public class Euler48 
{
	public static long final10( int number )
	{
		long result = 1;
 
		for( int i=0; i<number; i++ )
		{
			result *= number;
 
			if( result > 9999999999l )
			{
				result = result % 10000000000l;
			}
		}
 
		return result;
	}
 
	public static void main(String[] args)
	{
		long result = 0;
 
		for( int i=1; i<=1000; i++ )
		{
			result += final10( i );
		}
 
		result = result % 10000000000l; 
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 460 Comments »