Project Euler: Problem 34 – Digit factorials

Problem 34:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
 
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
 
Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Idea:

Not knowing how high to calculate, I again just took a shot in the dark with a really high number. Since we’re only calculating the factorial from 0 – 9, I calculated them once and put them into an array for easy access.
 
Then just looped from 3 to at least 400,000 (since 9! = 362,880) and add up the factorial of the digits and see if it equals the original number (in this case, I looped to 1 million). If the sum of the digit factorials is equal to the original number, add that number to the existing sum.

int answer = 0;

int[] factorials = new int[10];
factorials[0] = 1;
for(int i = 1; i < factorials.length; i++) {
   factorials[i] = factorials[i-1]*i;
}

for(int i = 3; i < 1000000; i++) {
   int tmp = i;
   int sum = 0;
   while(tmp > 0) {
      sum += factorials[tmp%10];
      tmp = tmp/10;
   }
   if(sum == i) {
      answer += sum;
   }
}

Project Euler: Problem 33 – Digit canceling fractions

Problem 33:

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
 
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
 
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
 
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Idea:

Since this involves two digits, non-trivial, we know to start at 11 and go to 99, skipping numbers multiples of 10. Since the fraction is less than 1, the denominator is always going to be at least numerator + 1.
 
From there, just need to find duplicate numbers and cancel them, making sure the cancelled fraction is still less than one. Compare the two divisions (tricky given floating point number comparisons, but I ignored it in this case since they’re either exactly the same, or they’re not), and if they’re the same, multiply them to the existing numerators and denominators. After that, just reduce the fraction.

int answer = -1;
int answerTop = 1;
int answerBottom = 1;

for(int top = 11; top < 100; top++) {
   if(top % 10 == 0) {
      continue;
   }
   for(int bottom = top+1; bottom < 100; bottom++) {
      if(bottom % 10 == 0) {
         continue;
      }
      String sTop = String.valueOf(top);
      String sBottom = String.valueOf(bottom);

      //41/49 -> 1/9
      if(sBottom.indexOf(sTop.charAt(0)) == 0) {
         sBottom = sBottom.substring(1);
         sTop = sTop.substring(1);
         //48/74 -> 8/7
      } else if(sBottom.indexOf(sTop.charAt(0)) == 1) {
         sBottom = sBottom.substring(0,1);
         sTop = sTop.substring(1);
         //48/82 -> 4/2
      } else if(sBottom.indexOf(sTop.charAt(1)) == 0) {
         sBottom = sBottom.substring(1);
         sTop = sTop.substring(0,1);
         //49/89 -> 4/8
      } else if(sBottom.indexOf(sTop.charAt(1)) == 1) {
         sBottom = sBottom.substring(0,1);
         sTop = sTop.substring(0,1);
         //no common characters
      } else {
         continue;
      }

      if(sBottom.equals(sTop) || sTop.charAt(0) > sBottom.charAt(0)) {
         continue;
      }
      double divide1 = (top*1.0)/bottom;
      double divide2 = Double.parseDouble(sTop) /
                       Double.parseDouble(sBottom);
      if(divide1 == divide2) {
         answerTop *= top;
         answerBottom *= bottom;
      }
   }
}

int gcd = BigInteger.valueOf(answerTop)
          .gcd(BigInteger.valueOf(answerBottom)).intValue();

answer = answerBottom / gcd;

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

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 31 – Coin sums

Problem 31:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

 
It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

 
How many different ways can £2 be made using any number of coins?

Idea:

I had no idea how I was going to go about this, so I started researching a similar problem I did a while back in college (how many ways can you make change for a dollar?). Stumbled upon Integer Partitions.

int answer = -1;

int[] denomination = {1,2,5,10,20,50,100,200};

answer = integerPartition(200,denomination.length-1,denomination);

System.out.println("Answer: "+answer);
//==================================
private static int integerPartition(int target, int index, int[] denoms) {
   if(target == 0) {
      return 1;
   }
   if(target < 0) {
      return 0;
   }
   if(index < 0 && target > 0) {
      return 0;
   }
   return integerPartition(target,index-1,denoms) +
          integerPartition(target-denoms[index], index,denoms);
}

In my research, I found this is a form of Integer Partition and came across this link.

Project Euler: Problem 27 – Quadratic primes

Problem 27:

Euler published the remarkable quadratic formula:
 
n² + n + 41
 
It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
 
Using computers, the incredible formula  n² – 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
 
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Idea:

I saw no simple way of doing this other than brute force. The number of calculations could be reduced by selecting b to be a prime number (whether positive or negative), but I figured that was too much work when it was much easier (with only slight performance hit) to just try all the numbers and count the number of consecutive primes, taking note of the coefficients when I found a pair that yielded a greater number of consecutive primes.

int answer = -1;
int numberOfPrimes = 0;
int answerA = 0;
int answerB = 0;

for(int a = -999; a < 1000; a++) {
   for(int b = -999; b < 1000; b++) {
      boolean consecutive = true;
      int n = 0;
      while(consecutive) {
         int value = (n*n) + a*n + b;
         if(BigInteger.valueOf(value).isProbablePrime(5)) {
            n++;
         } else {
            if(n > numberOfPrimes) {
               numberOfPrimes = n;
               answerA = a;
               answerB = b;
            }
            consecutive = !consecutive;
         }
      }
   }
}

answer = answerA*answerB;

System.out.println("Answer: "+answer+" (a = "+answerA+", b = "+answerB+", primes = "+numberOfPrimes);