Posted on Tuesday, January 6th, 2009 at 11:50 pm by Universe Queen
Problem 35:
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
Answer: 55
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
| public class Euler35
{
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 String[] circularCombinations( String number )
{
String[] c = new String[number.length()];
c[0] = number;
for( int i=1; i<c.length; i++ )
{
c[i] = number.substring(i)+number.substring(0,i);
}
return c;
}
public static boolean isCircularPrimer( int number )
{
if( !isPrime(number) )
{
return false;
}
String s = String.valueOf( number );
String[] c = circularCombinations( s );
for( int i=0; i<c.length; i++ )
{
int n = Integer.valueOf( c[i] );
if( !isPrime(n) )
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
int result = 0;
for( int i=2; i<=1000000; i++ )
{
if( isCircularPrimer(i) )
{
result ++;
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（35）" | 306 Comments »
Posted on Tuesday, January 6th, 2009 at 12:24 am by Universe Queen
Problem 34:
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.
Answer: 40730
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
| public class Euler34
{
public static int factory( int n )
{
int result = 1;
for( int i=1; i<=n; i++ )
{
result *= i;
}
return result;
}
public static boolean isOK( int n )
{
int result = 0;
int number = n;
int tmp;
while( number > 0 )
{
tmp = number - number/10*10;
result += factory( tmp );
number /= 10;
}
if( n == result )
{
return true;
}
return false;
}
public static void main(String[] args)
{
int result = 0;
for( int i=3; i<=2540160; i++ )
{
if( isOK(i) )
{
result += i;
}
}
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（34）" | 282 Comments »
Posted on Friday, January 2nd, 2009 at 10:50 pm by Universe Queen
Problem 33:
The fraction ^(49)/_(98) is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ^(49)/_(98) = ^(4)/_(8), which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ^(30)/_(50) = ^(3)/_(5), to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
Answer: 100
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
| public class Euler33
{
public static boolean isOK( int numerator, int denominator )
{
double f = (double)(numerator) / denominator;
String n = String.valueOf( numerator );
String d = String.valueOf( denominator );
if( n.charAt(1) == d.charAt(1) && n.charAt(1) != '0' )
{
numerator /= 10;
denominator /= 10;
}
else if( n.charAt(1) == d.charAt(0) && n.charAt(1) != '0' )
{
numerator /= 10;
denominator -= denominator/10*10;
}
else if( n.charAt(0) == d.charAt(1) && n.charAt(0) != '0' )
{
numerator -= numerator/10*10;
denominator /= 10;
}
else if( n.charAt(0) == d.charAt(0) && n.charAt(0) != '0' )
{
numerator -= numerator/10*10;
denominator -= denominator/10*10;
}
else
{
return false;
}
f = (double)numerator/denominator - f;
if( f < 0.000000001 && f > -0.000000001 )
{
return true;
}
return false;
}
public static void main(String[] args)
{
int result = 0;
int denominator = 10;
int numerator = 10;
int[] numbers = new int[8];
int counter = 0;
while(true)
{
while( numerator < denominator )
{
if( isOK( numerator, denominator ) )
{
numbers[counter*2] = numerator;
numbers[counter*2+1] = denominator;
counter++;
break;
}
numerator++;
}
if( counter == 4 )
{
break;
}
denominator++;
numerator = 10;
}
result = numbers[1]/numbers[0]*numbers[3]/numbers[2]*numbers[5]/numbers[4]*numbers[7]/numbers[6];
System.out.println( result );
}
} |
Tags: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（33）" | 609 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（32）" | 322 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（31）" | 201 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（30）" | 388 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（29）" | 690 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（28）" | 421 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（27）" | 578 Comments »
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: Project Euler
Posted in Project Euler | Permanent Link to "Project Euler（26）" | 1,319 Comments »
