**Problem:**

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, ... , ak} is called a product-sum number: N = a1 + a2 + ... + ak = a1 [×] a2 [×] ... [×] ak.

For example, 6 = 1 + 2 + 3 = 1 [×] 2 [×] 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 [×] 2 = 2 + 2

k=3: 6 = 1 [×] 2 [×] 3 = 1 + 2 + 3

k=4: 8 = 1 [×] 1 [×] 2 [×] 4 = 1 + 1 + 2 + 4

k=5: 8 = 1 [×] 1 [×] 2 [×] 2 [×] 2 = 1 + 1 + 2 + 2 + 2

k=6: 12 = 1 [×] 1 [×] 1 [×] 1 [×] 2 [×] 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2[≤]k[≤]6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2[≤]k[≤]12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2[≤]k[≤]12000?

For example, 6 = 1 + 2 + 3 = 1 [×] 2 [×] 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 [×] 2 = 2 + 2

k=3: 6 = 1 [×] 2 [×] 3 = 1 + 2 + 3

k=4: 8 = 1 [×] 1 [×] 2 [×] 4 = 1 + 1 + 2 + 4

k=5: 8 = 1 [×] 1 [×] 2 [×] 2 [×] 2 = 1 + 1 + 2 + 2 + 2

k=6: 12 = 1 [×] 1 [×] 1 [×] 1 [×] 2 [×] 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2[≤]k[≤]6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2[≤]k[≤]12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2[≤]k[≤]12000?

**Solution:**

932718654

**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 38

* By Nayuki Minase

*

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

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

*/

import java.util.Arrays;

public final class p038 implements EulerSolution {

public static void main(String[] args) {

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

}

public String run() {

int max = -1;

for (int n = 2; n <= 9; n++) {

for (int i = 1; i < Library.pow(10, 9 / n); i++) {

String concat = "";

for (int j = 1; j <= n; j++)

concat += i * j;

if (isPandigital(concat))

max = Math.max(Integer.parseInt(concat), max);

}

}

return Integer.toString(max);

}

private static boolean isPandigital(String s) {

if (s.length() != 9)

return false;

char[] temp = s.toCharArray();

Arrays.sort(temp);

return new String(temp).equals("123456789");

}

}

88 != 38

ReplyDelete