#### 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.
- We were given to start with 9, so c has to start with 9. Thus 9 <= c < 9,999.
- 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])); } }