Project Euler: Problem 43 – Sub-string divisibility

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.

Idea:

Re-used the nextPermutation() method I wrote for problem 24 and started at the largest 0 – 9 pandigital number that started with 0 (because the leading zero is ignored, and the next permutation will start with the smallest true 0 – 9 pandigital number).
 
Simply went though all the permutations, checking the substring divisibility, and adding the number to a running total as I found ones that fit the given characteristics.

BigInteger answer = BigInteger.ZERO;

int[] number = {0,9,8,7,6,5,4,3,2,1}; //last 0-9 pandigital starting w/ 0
while(EulerUtils.Permutation.nextPermutation(number)) {
   String tmp = EulerUtils.intArrayToBigInt(number).toString();
   if(Integer.parseInt(tmp.substring(1,4)) % 2 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(2,5)) % 3 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(3,6)) % 5 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(4,7)) % 7 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(5,8)) % 11 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(6,9)) % 13 != 0) {
      continue;
   }
   if(Integer.parseInt(tmp.substring(7,10)) % 17 != 0) {
      continue;
   }
   //if you get here, it's divisible by all the above
   answer = answer.add(EulerUtils.intArrayToBigInt(number));
}

Project Euler: Problem 38 – Pandigital multiples

Problem 38:

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?

Idea:

Since I know I multiply an integer by 1, 2…,n), and that it needs to be 9 digit pandigital, I realized my actual number of calculations will be small: concatenate the products until it is 9 digits.
 
Again chose an arbitrarily large number just to make sure I didn’t fall into any “gotcha” traps. Re-used the pandigital method I wrote for Problem 32.

int answer = -1;

for(int i = 1; i < 10000; i++) {
   String number = "";
   for(int j = 1; number.length() < 9; j++) {
      number += ""+(i*j);
   }
   if(EulerUtils.isPandigital(number)) {
      answer = Integer.parseInt(number);
   }
}

Note: isPandigital() is a helper method I wrote that determines whether a given number is pandigital.

Project Euler: Problem 32 – Pandigital products

Problem 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
 
The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
 
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
 
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Idea:

Right away, the problem is nice enough to state that I’ll encounter duplicates, so right off the bat, I know I want a data type that doesn’t permit duplicates.
 
Not knowing the range of the multiplicand and multiplier, I just took a guess at something I knew was relatively overkill for not wanting to have to go back and adjust my bounds. Expecially when all I’m doing is multiplying numbers together. Concatenate all the numbers together and check to see if it’s pandigital.

int answer = 0;
HashSet<Integer> products = new HashSet<Integer>();

for(int left = 1; left < 10000; left++) {
   for(int right = left; right < 10000; right++) {
      int product = left * right;
      String number = ""+product+""+left+""+right;
      if(isPandigital(number)){
         products.add(product);
      }
   }
}

for(Integer product:products) {
   answer += product;
}

System.out.println("Answer: "+answer);

Very inefficient brute-force, but hey, it worked. Initial attempt had the loop boundary too low.

Project Euler: Problem 41 – Pandigital prime

Problem 41:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
 
What is the largest n-digit pandigital prime that exists?

Idea:

We know that the largest possible pandigital number is 9 digits (since the problem specifically mentions starting at 1 and not 0). Given that, this problem is basically permuting the set of numbers from 1 to 9, except in reverse (for efficiency). I took the permutation algorithm I had for Problem 24, duplicated it, and modified it to get the previous permutation. Starting with the number 987654321, I kept getting the previous permutation and checking to see if it was prime using the BigInteger class, and stopped when I found the first one that was prime (the largest pandigital prime).

int answer = -1;

int count = 9;
ArrayList<Integer> numbers = new ArrayList<Integer>();
for(int i = count; i > 0; numbers.add(i),i--);
boolean found = false;

while(!found) {
   BigInteger num = listToBigInt(numbers);
   if(num.isProbablePrime(5)) {
      answer = num.intValue();
      found = true;
      break;
   }

   while(Permutation.previousPermutation(numbers)) {
      num = listToBigInt(numbers);
      if(num.isProbablePrime(5)) {
         answer = num.intValue();
         found = true;
         break;
      }
   }

   if(!found) {
      count--;
      numbers = new ArrayList<Integer>();
      for(int i = count; i > 0; numbers.add(i),i--);
   }
}

System.out.println("Answer: "+answer);