Luís Ramalho Entrepreneur & Developer

Project Euler — Problem 57

Square root convergents is a problem in which one must find how many fractions of the square root of 2 contain a numerator with more digits than denominator.

Since we are dealing with big numbers, we should use BigIntegers. Then, I looked for a pattern since we are given the first 8 iterations.

Respectively: \(\frac{3}{2}\), \(\frac{7}{5}\), \(\frac{17}{12}\), \(\frac{41}{29}\), \(\frac{99}{70}\), \(\frac{239}{169}\), \(\frac{577}{408}\), \(\frac{1393}{985}\)

I found one that applied for both the numerator and denominator:

Afterwards, it was trivial to code the solution:

ArrayList<BigInteger> n = new ArrayList<>();
n.add(BigInteger.valueOf(3)); // first numerator
n.add(BigInteger.valueOf(7)); // second numerator

ArrayList<BigInteger> d = new ArrayList<>();
d.add(BigInteger.valueOf(2)); // first denominator
d.add(BigInteger.valueOf(5)); // second denominator

BigInteger two = BigInteger.valueOf(2);
for (int i = 1; i < 1000; i++) {
    n.add(n.get(i).multiply(two).add(n.get(i - 1)));
    d.add(d.get(i).multiply(two).add(d.get(i - 1)));
}

int count = 0;
for (int i = 0; i < n.size(); i++) {
    if (n.get(i).toString().length() > d.get(i).toString().length()) {
        count++;
    }
}

return count;

The full solution can be found here.

Project Euler — Problem 56

Powerful digit sum is a problem in which one must find the maximum digital sum considering natural numbers of the form, a^b, where a, b < 100.

Since we are dealing with big numbers, we should use BigIntegers. This library has the method pow() which makes our life easier when calculating powers of BigIntegers.

int max = 0;
BigInteger n;
for (int a = 0; a < 100; a++) {
    for (int b = 0; b < 100; b++) {
        n = BigInteger.valueOf(a).pow(b);
        max = Math.max(digitalSum(n), max);
    }
}
return max;

Then, it is just a matter of calculating the sum of all the digits in the BigInteger, and returning the maximum.

int sum = 0;
String digits = n.toString();
for (int i = 0; i < digits.length(); i++) {
    sum += (int) digits.charAt(i) - '0';
}
return sum;

The full solution can be found here.

Project Euler — Problem 55

Lychrel numbers is a problem in which one must find how many Lychrel numbers are there below ten-thousand. You can read here more about Lychrel numbers.

It was clear since the beginning that we would be dealing with large numbers, so my approach was to use BigIntegers.

int lychrelNumbers = 0;
int i = 0;
BigInteger temp;
BigInteger one = BigInteger.ONE;
BigInteger b = new BigInteger("10");
BigInteger limit = new BigInteger("10000");
for (; b.compareTo(limit) < 0; b = b.add(one), i = 0) {
    temp = b;
    do {
        temp = temp.add(reverse(temp));
        i++;
    } while (!isPalindrome(temp.toString()) && i < 50);

    // Lychrel number
    if (i == 50) {
        lychrelNumbers++;
    }
}
return lychrelNumbers;

I started with 10 because 0 to 9 are palindromes. Inside the for loop we check if the addition of a number with it’s reverse is a palindrome for a maximum of 49 times. If not, then we got a Lychrel numbers.

The full solution can be found here.