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 48 – Self powers

Problem 48:

The series, 11 + 22 + 33 + … + 1010 = 10405071317.
 
Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

Idea:

Straight forward problem thanks to the BigInteger class.

String answer = "";

BigInteger sum = BigInteger.ZERO;

for(int i = 1; i <= 1000; i++) {
   sum = sum.add(BigInteger.valueOf(i).pow(i));
}

answer = sum.toString();
answer = answer.substring(answer.length()-10);

Project Euler: Problem 46 – Goldbach’s other conjecture

Problem 46:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
 
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
 
It turns out that the conjecture was false.
 
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Idea:

First, I had to look up what “odd composite” meant (in short: odd, non-prime number). From there, I made a list of the first 10000 prime numbers and I started with 3 and looped through every odd number to see if it was prime. If it wasn’t, I looped through the list of prime numbers and applied the formula above until I found and odd composite that couldn’t be written as the sum of a prime and twice a square.

int answer = -1;

int[] primes = new int[10000];
BigInteger base = BigInteger.ONE;
for(int i = 0; i < primes.length; i++) {
   base = base.nextProbablePrime();
   primes[i] = base.intValue();
}

boolean found = false;
int number = 3;
while(!found) {
   //test odd composite for prime-ness
   if(BigInteger.valueOf((long)number).isProbablePrime(10)) {
      number += 2;
      continue;
   }
   boolean cantBeWritten = true;
   for(int i = 0; primes[i] < number && cantBeWritten; i++) {
      int tmp = number-primes[i];
      tmp = tmp / 2;
      int result = (int)Math.sqrt(tmp);
      if(result*result*2 + primes[i] == number) {
         cantBeWritten = false;
      }
   }
   if(cantBeWritten) {
      answer = number;
      found = true;
      break;
   }
   number += 2;
}

Project Euler: Problem 45 – Triangular, pentagonal, and hexagonal

Problem 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755.
 
Find the next triangle number that is also pentagonal and hexagonal.

Idea:

Looking at the list of triangle and hexagonal numbers, I made an educated guess that all hexagonal numbers are triangle numbers, so that narrowed down the problem to “Find the next pentagonal number that is also hexagonal”.
 
From there I just generated the next hexagonal number (since it grows faster than pentagonal numbers), and started generating pentagonal numbers until they were no longer smaller than the hexagonal number. If it just so happened that the pentagonal number was equal to the hexagonal number, I found my answer.

String answer = "";

BigInteger pent = new BigInteger("40755");
BigInteger hex = new BigInteger("40755");
int h = 143;
int p = 165;
boolean matches = false;

while(!matches) {
   h++;
   hex = BigInteger.valueOf(h).multiply(
            BigInteger.valueOf(2).multiply(
               BigInteger.valueOf(h)).subtract(BigInteger.ONE));
   while(pent.compareTo(hex) < 0) {
      p++;
      pent = BigInteger.valueOf(p).multiply(
               BigInteger.valueOf(3).multiply(
                  BigInteger.valueOf(p)).subtract(BigInteger.ONE))
                   .divide(BigInteger.valueOf(2));
   }
   if(pent.compareTo(hex) == 0) {
      matches = true;
   }
}

answer = hex.toString();

Project Euler: Problem 44 – Pentagon numbers

Problem 44:

Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. The first ten pentagonal numbers are:
 
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
 
It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 – 22 = 48, is not pentagonal.
 
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk – Pj| is minimized; what is the value of D?

Idea:

First I generated a large list of pentagonal numbers (not knowing how many I would need). I used two lists, one regular so I could access the numbers by index (i.e. 5th pentagonal number + 7th pentagonal number), and one hashed so I could quickly find out if the resulting sum and difference were pentagonal numbers (I initially tried it without, and found that seeing if the regular list contained a number was taking up a significant amount of time).
 
If the difference was smaller than anything I’ve encountered so far, save it.

int answer = Integer.MAX_VALUE;

List<Integer> nums = EulerUtils.pentagonalNumbers(5000);
HashSet<Integer> numbers = new HashSet<Integer>();
for(Integer n:nums) {
   numbers.add(n);
}
for(int j = 0; j < numbers.size()-1; j++) {
   for(int k = j+1; k < numbers.size(); k++) {
      int sum = nums.get(j) + nums.get(k);
      if(!numbers.contains(sum)) {
         continue;
      }
      int difference = nums.get(k) - nums.get(j);
      if(!numbers.contains(difference)) {
         continue;
      }
      if(difference < answer) {
         answer = difference;
      }
   }
}

Note: pentagonalNumbers() is a utility method that generates a list of pentagonal numbers.