Problem 43: The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2 d3d4d5=063 is divisible by 3 d4d5d6=635 is divisible by 5 d5d6d7=357 is divisible by 7 d6d7d8=572 is divisible by 11 d7d8d9=728 is divisible by 13 d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
import java.math.BigInteger;
import java.util.Vector;
class runner
{
private static boolean isValid(String x){
if(Integer.valueOf(x.substring(1,4)) % 2 != 0)
return false;
if(Integer.valueOf(x.substring(2,5)) % 3 != 0)
return false;
if(Integer.valueOf(x.substring(3,6)) % 5 != 0)
return false;
if(Integer.valueOf(x.substring(4,7)) % 7 != 0)
return false;
if(Integer.valueOf(x.substring(5,8)) % 11 != 0)
return false;
if(Integer.valueOf(x.substring(6,9)) % 13 != 0)
return false;
if(Integer.valueOf(x.substring(7,10)) % 17 != 0)
return false;
return true;
}
//Concept from Steinhaus–Johnson–Trotter
public static void permute(String obj, Vector arr){
if(arr.size() == 0){
arr.add(obj);
return;
}
Vector result = new Vector();
for(String str: arr){
for(int i=0;i vector = new Vector();
for(int i=0;i<10;i++){
permute(String.valueOf(i),vector);
}
BigInteger sum = new BigInteger("0");
for(String str : vector){
//System.out.println(str);
sum = sum.add(new BigInteger(str));
}
System.out.println("S:"+sum);
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}
Note:
The isValid call should probably be called outside than when building the permutations.
However due to issues with memory on my computer when generating array sizes of 10!, it seemed the quickest way of injecting the call.