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