Project Euler: Problem 58 – Spiral primes

Problem 58:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%.
 
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Idea:

Even though I already have a spiral generating method used in Problem 28, I don’t need to generate anything: the diagonals are easily recognized by a pattern of numbers equally spaced apart per layer. Determine which numbers are on a diagonal, check to see if it’s prime, and keep track of the total numbers on the diagonal. While the ratio of primes along the diagonals to the total number of numbers along the diagonal is greater than 10%, keep adding a new layer.

int answer = -1;

boolean LESS_THAN_10_PERCENT = false;
double numberOfPrimes = 0;
int totalNumbers = 1;
int increment = 0;
int start = 1;
     
while(!LESS_THAN_10_PERCENT) {
   increment += 2;
   for(int i = 0; i < 4; i++) {
      start += increment;
      totalNumbers++;
      if(EulerUtils.isProbablePrime(start)) {
         numberOfPrimes++;
      }
   }
   double percentOfPrimes = numberOfPrimes/totalNumbers;
 
   if(percentOfPrimes < 0.1) {
      answer = increment+1;
      System.out.println("Calculated spiral of width: "+(increment+1)+
            " and ratio of: "+percentOfPrimes);
      LESS_THAN_10_PERCENT = true;
   }
}

Project Euler: Problem 51 – Prime digit replacements

Problem 51:

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
 
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
 
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

Idea:

I saw no easy way to do this, so I went with the way I would do it if I had unlimited time. I generated a temporary list of primes below 1 million (for easy traversal). I then counted the number of occurences of each particular digit along with locations. I then stored the number, the digit, and it’s locations in a custom object (“DigitReplacement”).
 
I then compiled a hashset of primes from the DigitReplacement objects to quickly determine prime-ness. I then took the location of all repeated digits in the base prime number, and repeated them with the same digit and checked that number against the hashset. Repeated that from 0 to 9 and counted the total number of primes found. If I found exactly 8 primes, then the base number is the answer.

int answer = -1;

final int BLOCK = 3;
final int GOAL = 8;

TreeSet<Eulerutils.DigitReplacement> primes = new TreeSet<Eulerutils.DigitReplacement>();
{
   int[] p = EulerUtils.generatePrimes(1000000);
   for(int i : p) {
      for(int l=0; l < 10; l++){
         int[][] tmp = EulerUtils.countOccurancesWithIndex((""+l).charAt(0), ""+i);
         if(tmp[0][0] >= BLOCK) {
               if(tmp[1].length > BLOCK) {
                  for(int j = 0; j+BLOCK < = tmp[1].length; j++) {
                     primes.add(new EulerUtils.DigitReplacement(
                             i, l, Arrays.copyOfRange(tmp[1], j, j+BLOCK)));
                  }
               } else {
                  primes.add(new EulerUtils.DigitReplacement(i, l, tmp[1]));
               }
         }
      }
   }
}

HashSet<Integer> hashPrimes = new HashSet<Integer>(primes.size());
for(EulerUtils.DigitReplacement dr : primes) {
   hashPrimes.add(dr.getNumber());
}

for(EulerUtils.DigitReplacement dr : primes) {
   int count = 0;
   int[] locations = dr.getLocations();
   char[] digits = (""+dr.getNumber()).toCharArray();
   for(int i = 0; i < 10; i++) {
      for(int index = 0; index < BLOCK; index++) {
         digits[locations[index]] = (""+i).charAt(0);
      }
      if(hashPrimes.contains(Integer.parseInt(new String(digits)))) {
         count++;
      }
   }
   if(count == GOAL) {
      answer = dr.getNumber();
      break;
   }
}

Project Euler: Problem 50 – Consecutive prime sum

Problem 50:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.
 
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
 
Which prime, below one-million, can be written as the sum of the most consecutive primes?

Idea:

This problem immediately jumped out at me as one that would benefit from stepping in blocks. Since the problem is looking for a prime number below 1 million, I first generated a list of all the primes below 1 million (reason for that in a minute). I then generated a list of the sum of all the primes, so primeSum[0] = 2 (first prime), primeSum[1] = primeSum[n-1] + prime[n] = 2 + 3 = 5, and so on. This would easily allow me to find the sum of the first n-1 (0 offset) prime numbers instantly, as well as help with marching in blocks.
 
Since we need the maximum consecutive sum, I started with the largest possible block: the number of all the primes from 1 to 1 million. From there, I would check to see if the sum is less than the threshold, and if so, do a binary search on the array of primes to see if the sum is prime. If so, I found my answer, if not, I stepped the block forward 1 (staying within boundary) and repeating until the block reach the end. If the answer was not found, decrease the block size, set it back to the beginning, and repeat until I find the maximal answer.

int answer = -1;
int length = -1;

final int THRESHOLD = 1000000;

int[] primes = EulerUtils.generatePrimes(THRESHOLD);
long[] primeSum = new long[primes.length];
primeSum[0] = primes[0];
for(int i = 1; i < primeSum.length; primeSum[i] = primeSum[i-1]+primes[i],i++);

findAnswer:
for(int blockWidth = primes.length-1; blockWidth >= 0; blockWidth--) {
   if(primeSum[blockWidth] < THRESHOLD) {
      int index = Arrays.binarySearch(primes, (int)primeSum[blockWidth]);
      if(index > -1 && primes[index] == primeSum[blockWidth]) {
         answer = (int)primeSum[blockWidth];
         length = blockWidth+1;
         break findAnswer;
      }
   }
   for(int j = 0; j+blockWidth < primeSum.length; j++) {
      long upper = primeSum[j+blockWidth];
      long lower = primeSum[j];
      long difference = upper - lower;
      if(difference > THRESHOLD) continue;
      int index = Arrays.binarySearch(primes, (int)difference);
      if(index > -1 && primes[index] == difference) {
         answer = (int)difference;
         length = blockWidth;
         break findAnswer;
      }
   }
}

Project Euler: Problem 47 – Distinct primes factors

Problem 47:

The first two consecutive numbers to have two distinct prime factors are:
 
14 = 2 x 7
15 = 3 x 5
 
The first three consecutive numbers to have three distinct prime factors are:
 
644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.
 
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

Idea:

This seemed like a pretty simple problem, until the second example included a prime factor to a power. My first task is to get the distinct prime factors, including prime factors to a power. I already had a method that would return a list of the prime factors, so I just called that method, sorted the list, and combined like terms to get a list of distinct prime factors, including those raised to a power.
 
The next order of business is to start finding the numbers for the solution. I started with 210 (smallest number with 4 distinct prime factors), even though I was pretty certain the answer would be larger than 646 in the example, however I didn’t want to make any false assumptions.
 
I started with 210 as the “base” number and incremented by 1 until I found a base number with exactly 4 distinct prime factors, and stored that number, and the list of factors, in a map. Then I added 1 to the base number, and checked that to see if it had 4 distinct prime factors. I repeated this until I got to the “base+3” that had 4 distinct prime factors, storing all the numbers and their respective list of distinct prime factors in a map. If any numbers in between didn’t have exactly 4 distinct prime factors, I discarded all the numbers I had saved so far, and incremented my base number by that amount.
 
When I found a “base+3” with 4 distinct prime factors, I checked to see if the 4 lists of prime factors were all mutually disjoint. If they were, the “base” number was the answer; if they weren’t, I incremented the base number by 1 and continued my search. I chose to only increment by 1 instead of 3-4 in case I ran into a situation where, for example, there were 4 or more consecutive numbers who had exactly 4 distinct prime factors, and it just so happens that the first number in the series shares factors with one of the next 3 numbers, but the second number in the series is the start of the 4 numbers that all have mutually distinct prime factors.
 
During execution, I used the debugger in Eclipse and recognized most of the program execution time was in finding the prime factors. I left a note to myself that the program could be more efficient if I used a sieve method for finding the factors, but I got the program working, and as a rule that was drilled into me from school: make it work first, optimize later.

//IMPROVE: use sieve approach to count # of factors
//and don't save all the factors to compare
int answer = -1;

boolean done = false;
int number = 210; //2*3*5*7 (smallest number w/ 4 distinct prime factors)
List<Integer> base,plus1,plus2,plus3;
Map<Integer ,List<Integer>> dpf = new Hashtable<Integer ,List<Integer>>();
while(!done) {
   if(!dpf.containsKey(number)) {
      dpf.put(number,EulerUtils.distinctPrimeFactors(number));
   }
   base = dpf.get(number);
   if(base.size() != 4) {
      dpf.remove(number); //remove existing number from map
      number += 1;
      continue;
   }
  
   if(!dpf.containsKey(number+1)) {
      dpf.put(number+1,EulerUtils.distinctPrimeFactors(number+1));
   }
   plus1 = dpf.get(number+1);
   if(plus1.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      number = (number+1)+1; //skip ahead to plus2 number
      continue;
   }
  
   if(!dpf.containsKey(number+2)) {
      dpf.put(number+2,EulerUtils.distinctPrimeFactors(number+2));
   }
   plus2 = dpf.get(number+2);
   if(plus2.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      dpf.remove(number+2); //remove plus2 number from map
      number = (number+2)+1; //skip ahead to plus3 number
      continue;
   }
  
   if(!dpf.containsKey(number+3)) {
      dpf.put(number+3,EulerUtils.distinctPrimeFactors(number+3));
   }
   plus3 = dpf.get(number+3);
   if(plus3.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      dpf.remove(number+2); //remove plus2 number from map
      dpf.remove(number+3); //remove plus3 number from map
      number = (number+3)+1; //skip ahead to the 5th number
      continue;
   }

   if(Collections.disjoint(base, plus1) && Collections.disjoint(base, plus2) &&
         Collections.disjoint(base, plus3) && Collections.disjoint(plus1, plus2) &&
         Collections.disjoint(plus1, plus3) && Collections.disjoint(plus2, plus3)) {
      answer = number;
      done = true;
   } else {
      dpf.remove(number);
      number += 1;
   }
}

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;
         }
      }
   }
}