Project Euler: Problem 53 – Combinatoric selections

Problem 53:

There are exactly ten ways of selecting three from five, 12345:
 
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
 
In combinatorics, we use the notation, 5C3 = 10.
 
In general,

nCr =
n!
r!(n-r)!
,where r <= nn! = nx(n-1)x…x3x2x1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
 
How many, not necessarily distinct, values of  nCr, for 1 <= n <= 100, are greater than one-million?

Idea:

I recognized this as another repeat of Binomial Coefficients as seen in Problem 15. I just needed to plug in the numbers in a nested loop and count how many times the answer was greater than 1 million.

int answer = 0;

final BigInteger ONE_MILLION = BigInteger.valueOf(1000000);

for(int n = 1; n <= 100; n++) {
   for(int r = 1; r <= n; r++) {
      if(ONE_MILLION.compareTo(EulerUtils.nChooseM(n, r)) < 0) {
         answer++;
      }
   }
}

Project Euler: Problem 56 – Powerful digit sum

Problem 56:

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
 
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

Idea:

I was wondering how long it was going to be until googol came up in a problem (although I was part expecting googolplex)
 
I didn’t see any easy way to do this, as it’s pretty straight forward, raise a to the power of b, for all possible combinations of a and b < 100, take the sum of the digits, and repeat until you reach 9999, keeping track of the maximal sum.

int answer = -1;

for(int a = 1; a < 100; a++) {
   for(int b = 1; b < 100; b++) {
      BigInteger base = BigInteger.valueOf(a);
      BigInteger result = base.pow(b);
      int[] digits = EulerUtils.numberToDigits(result.toString());
      int sum = 0;
      for(int i : digits) {
         sum+=i;
      }
      if(sum > answer) answer = sum;
   }
}

Project Euler: Problem 80 – Square root digital expansion

Problem 80:

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
 
The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.
 
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Idea:

Since I need a lot of digits / precision, I need to use the sister class of BigInteger: BigDecimal. I saw BigDecimal had no square root method, so I was going to use the power method, but it only accepts integers (so I can’t raise a decimal to the 1/2 power, i.e. square root). So I had to create a square root method myself (after a little research).
 
With that completed, I just needed to check to see if the resulting square root was an integer or decimal. From there, just add the first 100 decimal values together for all the non-integer square roots.

int answer = 0;

MathContext precision = new MathContext(105);
for(int i = 1; i <= 100; i++) {
    BigDecimal temp = EulerUtils.sqrt(BigDecimal.valueOf(i), precision);
    String number = temp.toString();
    if(number.indexOf(".") == -1) {
        continue;
    } else {
        number = number.substring(0,101);
        number = number.replace(".","");
        for(char c:number.toCharArray()) {
            answer += Integer.parseInt(""+c);
        }
    }
}

Note: sqrt() is a method I wrote to calculate the square root of a BigDecimal up to a given precision.

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