Project Euler, problem 4, palindromes

Problem 4:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Firstly I decided to try and solve the problem using two 2-digit numbers so I can understand how the creator of this problem got to 9009.

In about 15 minutes I was able to come up with this brute force hack:

public class Problem4 {

    public static void main(String[] args) {
        solve();
    }

    private static void solve() {
        int highestPalindrome = 0;

        for (int left = 99; left > 2; left--) {
            for (int right = 99; right > 2; right--) {
                int candidate = left * right;
                if (isPalindrome(candidate)) {
                    System.out.println(format("Palindrome found! Using %d * %d = %d ", left, right, candidate));
                    if (candidate > highestPalindrome) {
                        highestPalindrome = candidate;
                    }
                }
            }
        }
        System.out.println("Highest palindrome is " + highestPalindrome);
    }

    private static boolean isPalindrome(int palindrome) {
        String palindromeString = "" + palindrome;
        String reversed = new StringBuilder(palindromeString).reverse().toString();
        return palindromeString.equals(reversed);
    }
}

Which gives the output of

Highest palindrome is 9009

Excellent, so we’re on the right track. The next thing I did was alter the loop statements to start at 999, which then prints the following

Highest palindrome is 906609

Which is the correct answer!

Any suggestions on improvements? Please comment!

Project Euler, problem 3, largest prime factor

Problem 3 :

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

To solve this, I needed to understand the process of prime factorisation (surprisingly, it is something which I was never taught at school/uni).

What we need to do, is to take the number 13195, then try and divide it by the smallest prime number; 2.

If it doesn’t divide equally, we try it with the next prime number; 3, and so on, until it divides evenly with no remainder.

So 13195 divides into 5 evenly, and we get a result of 2639.

We can retain that number 5, but since we’re only interested in the largest prime factor, we reset our divisor count to 2 and start the process again, trying to divide 2639 until we find a number that it divides evenly by, which happens to be 7.

  • 13195 / 5 = 2639
  • 2639 / 7 = 377
  • 377 / 13 = 29

On the last stage of prime factorisation, we’re trying to find a number that fits into 29 evenly, but there isn’t one, so we’re left with the prime number of 29.

We’re left with the prime factors of 5, 7, 13 and 29.

I found that the MathsIsFun.com had a good article on prime factorisation, with several examples and explanations.

Here is my solution using Java

/**
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * <p/>
 * What is the largest prime factor of the number 600851475143 ?
 */
public class Problem3 {

    public static void main(String[] args) {
        System.out.println(solve(600851475143l));
    }

    public static int solve(long number) {
        int i;

        // start dividing by 2, as that is the smallest prime number, keep going until we're trying to divide the number by itself,
        // this indicates we've finished.
        for (i = 2; i <= number; i++) {
            //We're only interested in "i" if it divides evenly by the number
            if (number % i == 0) {
                // divide number by i and re-assign, so we can start counting up from 2 again
                number /= i;
                // the for loop will increment i, however if number is divisible by i with no remainder, we want to try again.
                // for example, if we divide number 2000 by 2, we want to decrement i so we can try to divide the resulting 1000 by 2 again
                i--;
            }
        }

        return i;
    }
}

Don’t forget the “L” on the end of the number, we need to use a long as its too large to fit in an int.

The answer is 6857

Project Euler, problem 2, fibonacci sequence

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Attacking this problem in using brute force, I create a left and right ints, to hold 1 and 2 respectively, I use these to walk along the fibonacci sequence.

To count along the fibonacci sequence I add the left and right together, and shift them leftwards, until I reach the desired upper limit. On each sequence number, I check if it is even and add to a total if it is.

Here is my solution using Java

public class Problem2
{
    public static void main(String[] args)
    {
        System.out.println(execute(4000000));
    }


    public static int execute(int upperLimit)
    {
        // since we start with 1 & 2, we can assume result always starts from 2, as it's even
        int result = 2;
        int left = 1;
        int right = 2;

        while (left + right < upperLimit)
        {
            int temp = left + right;
            left = right;
            right = temp;
            if (right % 2 == 0)
            {
                result += right;
            }
        }

        return result;
    }
}

The answer is 4613732

Project Euler, problem 1, multiple factors

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

To solve this in a brute force manner, we can count up to 1000, for each number we check to see if it divides into 3 and 5 leaving no remainder. If it does, they we add that number into our running total.

Heres my solution using Java.

public class Problem1 {

    public static void main(String[] args) {
        System.out.println(solve(1000));
    }

    public static int solve(final int subject) {
        int sum = 0;
        for (int i = 0; i < subject; i++) {
            if ((i % 3 == 0) || (i % 5 == 0)) {
                sum += i;
            }
        }
        return sum;
    }
}

The answer is 233168