Project Euler: Problem 52 – Permuted multiples

Problem 52:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
 
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Idea:

I felt like being lazy for this one, partly because the method I had in mind would fail quickly for each incorrect answer, and partly because I already have a method to see if a number is a permutation thanks in part to Problem 24. I just did what the problem said:
 
Pick a number, multiply it by 2, see if it’s a permutation. If not, continue to the next number, otherwise, repeat with 3x, 4x, 5x, and 6x.

int answer = -1;

boolean found = false;

int number = 1;
while(!found) {
   if(EulerUtils.Permutation.isPermutation(number, number*2)) {
      if(EulerUtils.Permutation.isPermutation(number, number*3)) {
         if(EulerUtils.Permutation.isPermutation(number, number*4)) {
            if(EulerUtils.Permutation.isPermutation(number, number*5)) {
               if(EulerUtils.Permutation.isPermutation(number, number*6)) {
                  found = true;
                  answer = number;
               }
            }
         }
      }
   }
   number++;
}

Project Euler: Problem 49 – Prime permutations

Problem 49:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
 
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
 
What 12-digit number do you form by concatenating the three terms in this sequence?

Idea:

The problem mentioned permutations, so right away I know I’m going to need to use the nextPermutation method I wrote for problem 24. I’m also going to need a list of all the 4 digit prime numbers (well, not really, but I thought it would be faster to compute them once rather than repeatedly call “isProbablePrime” in the BigInteger class.
 
I also made a “visited” array to see if any of the primes later on were permutations of a previous prime number (so I could skip over them). I then decided to generate a list of prime permutations based off a given number.
 
Now, since I didn’t know if the next answer would also exhibit the characteristic of being able to add 3330 to it and get 2 more prime permutations, I assumed that wouldn’t be the case (since the problem only said “increasing sequence” but failed to mention by how much).
 
Since the sequence had to contain at least 3 terms, I ignored anything less than that. From there I started adding 1 to 5000 to the initial number to see if the next number was prime, and if so, added that same number again.

long answer = -1;
//get list of 4 digit primes
LinkedHashSet<Integer> primes = new LinkedHashSet<Integer>();
{
   BigInteger number = BigInteger.valueOf(1000);
   number = number.nextProbablePrime();
   while(number.compareTo(BigInteger.valueOf(10000)) < 0) {
      primes.add(number.intValue());
      number = number.nextProbablePrime();
   }
}

Iterator<Integer> itr = primes.iterator();
boolean[] visited = new boolean[9000];
while(itr.hasNext()) {
   Integer num = itr.next();
   //check to see if this is a permutation of an earlier prime
   if(visited[num.intValue()-1000]) {
      continue;
   }
   visited[num.intValue()-1000] = true;
   ArrayList<Integer> perms = new ArrayList<Integer>();
   perms.add(num);
   while((num = EulerUtils.Permutation.nextPermutation(num)) != null) {
      //build list of prime permutations
      if(primes.contains(num) && num > 1000) {
         perms.add(num);
         visited[num.intValue()-1000] = true;
      }
   }
   //analyze list of prime permutations for condition
   boolean found = false;
   if(perms.size() >= 3) {
      for(Integer i : perms) {
         for(int add = 1; add < 5000 && !found; add++) {
            int secondTerm = i.intValue() + add;
            boolean inPrimes = primes.contains(secondTerm);
            boolean inPerms = perms.contains(secondTerm);
            if(!inPrimes || !inPerms) {
               continue;
            } else {
               int thirdTerm = secondTerm + add;
               inPrimes = primes.contains(thirdTerm);
               inPerms = perms.contains(thirdTerm);
               if(!inPrimes || !inPerms) {
                  continue;
               } else {
                  //adding to a prime twice resulted in 2 primes
                  if(i.intValue() == 1487) {
                     //already have this, find the next one
                     continue;
                  }
                  String tmp = ""+i.intValue()+""+secondTerm+""+thirdTerm;
                  answer = Long.parseLong(tmp);
                  found = true;
               }
            }
         }
         if(found) {
            break;
         }
      }
   }
}

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 24 – Lexicographic permutations

Problem 24:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
 
012   021   102   120   201   210
 
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Idea:

This problem reminded me of a similar problem I encountered at Pacific Lutheran University. I was presented with two options: develop a method to calculate all the permutations and stop at the one I wanted (easier, but inefficient), or given a set, find the next permutation (slightly more difficult, but efficient if you just want to find the next, without having to recalculate all the previous ones). Fearing permutations would arise again in future problems, I went with the latter.
 
Once the permutation algorithm was handled, the only part that concerned me was: does the first ordering count as the first permutation, or does the second ordering count as the first permutation. Worst case scenario, I’d just have to try submitting 2 answers.

String answer = "";
int[] numbers = {0,1,2,3,4,5,6,7,8,9};

for(int i = 1; i < 1000000; i++) {
   Permutation.nextPermutation(numbers);
}

for(int i = 0; i < numbers.length; i++) {
   answer += ""+numbers[i];
}

System.out.println("Answer: "+answer);
//==================================
public static boolean nextPermutation(int[] array) {
   //check for reverse lexicographical order
   int index1 = array.length - 2;
   while (index1 >= 0 && array[index1] >= array[index1 + 1]) {
      index1--;
   }

   //if in reverse lexicographical order, no more permutations
   if (index1 == -1) {
      return false;
   }

   //find first element from the end
   //that's greater than the element from above
   int index2 = array.length - 1;
   while (array[index2] <= array[index1]) {
      index2--;
   }

   //swap those elements;
   int tmp = array[index1];
   array[index1] = array[index2];
   array[index2] = tmp;

   //reverse the remaining elements to complete
   //the next lexicographical permutation
   for (int i = index1 + 1, j = array.length - 1; i < j; i++, j--) {
      tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
   }
   return true;
}