# Project Euler

### A Taste of Number Theory

#### Problem 38: Pandigital Multiples

Take the number 192 and multiply it by each of 1, 2, and 3:
192 x 1 = 192
192 x 2 = 384
192 x 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?

#### The Catch

How to find the optimal range of a candidate number c, which is to be multiplied with (1, 2, ... n) where n > 1 to form the concatenated-product-pandigital number.
How to check if a number is pandigital.

#### The Light

The desired pandigital number p has to have 9 digits from 1-9, exactly once each. A candidate number c has to be multiplied with 1 to n, with n > 1. The products are then concatenated to form p. Define the notation (a)(b) to be "a concatenates b", or ab. To find the range of c, observe:

• c has to have less than 5 digits because the smallest 5-digit number is 10,000 and the smallest possible value for n is 2 (n > 1). This gives (10,000 * 1)(10,000 * 2) = 1,000,020,000, which has 10 digits and thus does not satisfy the 9-digit condition. Thus c < 10,000.
• If c has 2 digits, its lowest value is 90. Assume n = 2 (lowest possible value), (90 * 1)(90 * 2) = 90,180, which does not satisfy the 9-digit condition. n = 3 gives 90,180,270 and n = 4 gives 90,180,270,360, both of which do not satisfy the 9-digit condition. Thus 90 <= c < 9,999.
• If c has 3 digits, its lowest value is 900. Assume n = 2 (lowest possible value), (900 * 1)(900 * 2) = 9,001,800, which does not satisfy the 9-digit condition. n = 3 gives 90,018,002,700 and n = 4 gives 900,180,027,003,600, both of which do not satisfy the 9-digit condition. Thus 900 <= c < 9,999.
• If c has 4 digits, its lowest value is 9,000. Assume n = 2 (lowest possible value), (9,000 * 1)(9,000 * 2) = 900,018,000, which satisfies the 9-digit condition. n = 3 gives 90,001,800,027,000, violating the 9-digit condition, thus any n > 2 will not work.
• Range for candidate c is 9,000 <= c < 9,999 and n can only be 2.

Since we're looking for the largest instance, start with the greatest possible c candidate and decrement.

Follow the discussion in Problem 41 to check if a number is pandigital.

#### The Code

```import java.util.Arrays;

public class Problem38
{
public static char[][] p = {"1".toCharArray(), "12".toCharArray(),
"123".toCharArray(), "1234".toCharArray(),
"12345".toCharArray(), "123456".toCharArray(),
"1234567".toCharArray(), "12345678".toCharArray(),
"123456789".toCharArray()};

public static void main(String[] args)
{
for(int i = 9999; i >= 9000; i--)
{
String s = Integer.toString(i);
s = s.concat(Integer.toString(i*2));
if(isPan(s))
{
System.out.println(s);
break;
}
}
}

public static boolean isPan(String s)
{
char[] c = s.toCharArray();
Arrays.sort(c);
return (Arrays.equals(c, p[c.length - 1]));
}
}
```