**Problem:**

Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d M(4, d) N(4, d) S(4, d)

0 2 13 67061

1 3 9 22275

2 3 1 2221

3 3 12 46214

4 3 2 8888

5 3 1 5557

6 3 1 6661

7 3 9 57863

8 3 1 8887

9 3 7 48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d M(4, d) N(4, d) S(4, d)

0 2 13 67061

1 3 9 22275

2 3 1 2221

3 3 12 46214

4 3 2 8888

5 3 1 5557

6 3 1 6661

7 3 9 57863

8 3 1 8887

9 3 7 48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

**Solution:**

70600674

**Code:**

The solution may include methods that will be found here: Library.java .

The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/*

* Solution to Project Euler problem 11

* By Nayuki Minase

*

* http://nayuki.eigenstate.org/page/project-euler-solutions

* https://github.com/nayuki/Project-Euler-solutions

*/

public final class p011 implements EulerSolution {

public static void main(String[] args) {

System.out.println(new p011().run());

}

public String run() {

int max = -1;

max = Math.max(maxProduct(1, 0), max);

max = Math.max(maxProduct(0, 1), max);

max = Math.max(maxProduct(1, 1), max);

max = Math.max(maxProduct(1, -1), max);

return Integer.toString(max);

}

private static int maxProduct(int dx, int dy) {

int max = -1;

for (int y = 0; y < SQUARE.length; y++) {

for (int x = 0; x < SQUARE[y].length; x++)

max = Math.max(product(x, y, dx, dy, 4), max);

}

return max;

}

private static int product(int x, int y, int dx, int dy, int n) {

// First endpoint is assumed to be in bounds. Check if second endpoint is in bounds.

if (!isInBounds(x + (n - 1) * dx, y + (n - 1) * dy))

return -1;

int prod = 1;

for (int i = 0; i < n; i++, x += dx, y += dy)

prod *= SQUARE[y][x];

return prod;

}

private static boolean isInBounds(int x, int y) {

return 0 <= y && y < SQUARE.length && 0 <= x && x < SQUARE[y].length;

}

private static int[][] SQUARE = {

{ 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8},

{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},

{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},

{52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},

{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},

{24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},

{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},

{67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},

{24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},

{21,36,23, 9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},

{78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14, 9,53,56,92},

{16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},

{86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},

{19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},

{04,52, 8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},

{88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},

{04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},

{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},

{20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},

{01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}

};

}

## No comments :

## Post a Comment