Monthly Archives: May 2010

Euler Problem 38

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

This one was easier than it sounded. Just created a list of all the concatenated products. Then filtered the list for pandigital numbers. The highest one was the winner.

import java.util.*;

public class Euler38
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 38:\n”);
        Euler38 e = new Euler38();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<String> list = new ArrayList<String>();
        ArrayList<String> list2 = new ArrayList<String>();
        String[] digits = {“1″,”2″,”3″,”4″,”5″,”6″,”7″,”8″,”9”};
        for (int i = 9; i <= 1000000; i++)
        {
            String S = “”;
            for (int n = 1; n <= 100; n++)
            {
                if (S.length() < 9)
                    S += i*n;
                if (S.contains(“0”))
                    break;
                if (S.length() == 9)
                    list.add(S);
                if (S.length() > 9)
                    break;
            }
        }
        for (String n: list)
        {
            boolean flag = true;
            for (String d: digits)
            {
                if (n.contains(d))
                    if (n.replace(d,””).length() != 8)
                        flag = false;
            }
            if (flag)
                list2.add(n);
        }
        Collections.sort(list2);
        return String.valueOf(list2.get(list2.size()-1));
    }
}

Euler Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Got it, but its not pretty. This one almost amounts to brute force, although I figured out to split the right-to-left first, to reduce the pool before doing the left-to-right. This cut the time down in half to 4 mins on a loaded system.

import java.util.*;

public class Euler37
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 37:\n”);
        Euler37 e = new Euler37();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P1 = new ArrayList<Integer>();
        ArrayList<Integer> P2 = new ArrayList<Integer>();
        String l2r = “”, r2l = “”;
        boolean flag = true;
        int n = 1000000, sum = 0;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < n; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < n; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < n; i++)
            if (isPrime[i] == true)
                P1.add(i);
        for (int i : P1)
            if (i >= 11)
            {
                l2r = Integer.toString(i);
                flag = true;
                for (int m = 0; m <= l2r.length()-1; m++)
                    if (P1.contains(Integer.valueOf(l2r.substring(m))) == false)
                        flag = false;
                if (flag)
                    P2.add(i);
            }
        for (int i : P2)
        {
            r2l = Integer.toString(i);
            flag = true;
            for (int m = 0; m <= r2l.length()-1; m++)
                if (P1.contains(Integer.valueOf(r2l.substring(0,r2l.length()-m))) == false)
                    flag = false;
            if (flag)
            {
                System.out.format(“%d\n”,i);
                sum += i;
            }
        }
        return String.valueOf(sum);
    }
}

package euler;

import java.util.*;
//import java.math.*;

public class Euler37
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 37:\n”);
        Euler37 e = new Euler37();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P1 = new ArrayList<Integer>();
        ArrayList<Integer> P2 = new ArrayList<Integer>();
        String l2r = “”, r2l = “”;
        boolean flag = true;
        int n = 1000000, sum = 0;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < n; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < n; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < n; i++)
            if (isPrime[i] == true)
                P1.add(i);
        for (int i : P1)
            if (i >= 11)
            {
                l2r = Integer.toString(i);
                flag = true;
                for (int m = 0; m <= l2r.length()-1; m++)
                    if (P1.contains(Integer.valueOf(l2r.substring(m))) == false)
                        flag = false;
                if (flag)
                    P2.add(i);
            }
        for (int i : P2)
        {
            r2l = Integer.toString(i);
            flag = true;
            for (int m = 0; m <= r2l.length()-1; m++)
                if (P1.contains(Integer.valueOf(r2l.substring(0,r2l.length()-m))) == false)
                    flag = false;
            if (flag)
            {
                System.out.format(“%d\n”,i);
                sum += i;
            }
        }
        return String.valueOf(sum);
    }
}

Euler Problem 36

The decimal number, 585 = 1001001001_(2) (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

No problems here. Flew through this one fast. The trick is to compare strings, not numbers. But use the Integer class to do the base conversion to string for you.

public class Euler36
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 36:\n”);
        Euler36 e = new Euler36();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        int sum = 0;
        for (int i10 = 1; i10 <= 1000000; i10++)
        {
            String r10 = “”;
            String r2 = “”;
            String s10 = Integer.toString(i10);
            String s2 = Integer.toBinaryString(i10);
            for (int i = s10.length()-1; i >=0; i–)
                r10 += s10.charAt(i);
            for (int i = s2.length()-1; i >=0; i–)
                r2 += s2.charAt(i);
            if (s10.equals(r10) && s2.equals(r2))
            {
                sum += i10;
                System.out.format(“%s:%s %s:%s\n”, s10, r10, s2, r2);
            }
        }
        return String.valueOf(sum);
    }
}

Euler Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

This one was pretty easy, but parts of the program aren’t optimized. Just generate all the primes under one million, then test for circular prime. Generating the primes is easy and the fast part (as per previous problems). But I couldn’t work out an efficient routine for the testing. This one took about 5 minutes to run.

import java.util.*;

public class Euler35
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 35:\n”);
        Euler35 e = new Euler35();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        ArrayList<Integer> C = new ArrayList<Integer>();
        ArrayList<Integer> g = new ArrayList<Integer>();
        String s = “”;
        boolean flag = true;
        int i2 = 0;
        int n = 1000000;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < n; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < n; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < n; i++)
            if (isPrime[i] == true)
                P.add(i);
        for (int i: P)
        {
            s = String.valueOf(i);
            g.clear();
            g.add(i);
            flag = true;
            for (int j = 1; j <= s.length()-1; j++)
            {
                i2 = Integer.valueOf(s.substring(j) + s.substring(0, j));
                if (P.contains(i2) && flag)
                    g.add(i2);
                else
                    flag = false;
            }
            if (flag)
                for (int m: g)
                    if (C.contains(m) == false)
                        C.add(m);
        }
        return String.valueOf(C.size());
    }
}

Euler 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.

This one is a staight forward as it seems. Don’t need to iterate too high as the sum of lots of 9-bang’s can’t catch up to a long digit number consisting of many nines.

public class Euler34
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 34:\n”);
        Euler34 e = new Euler34();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        long bigSum = 0;
        for (int i = 3; i <= 100000; i++)
        {
            int littleSum = 0;
            String digits = String.valueOf(i);
            for (int n = 0; n <= digits.length()-1; n++)
                littleSum += F(digits.charAt(n)-48);
            if (littleSum == i)
            {
                bigSum += littleSum;
                System.out.format(“%s:%d\n”, i, littleSum);
            }
        }
        return String.valueOf(bigSum);
    }
    public int F (int d)
    {
        int sum = 1;
        for (int i = d; i >= 1; i–)
            sum *= i;
        return sum;
    }
}

Euler Problem 33

The fraction ^(49)/_(98) is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ^(49)/_(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.

Just a bunch of cascaded if’s.

public class Euler33
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 33:\n”);
        Euler33 e = new Euler33();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        int numProd = 1, denomProd = 1;
        String [] digits = {“1″,”2″,”3″,”4″,”5″,”6″,”7″,”8″,”9”};
        for (int num = 11; num <= 99; num++)
            for (int denom = 11; denom <= 99; denom++)
                if ((double)num/(double)denom < 1)
                {
                    String numStr = String.valueOf(num);
                    String denomStr = String.valueOf(denom);
                    for (String d : digits)
                        if (numStr.contains(d) && denomStr.contains(d))
                        {
                            String newNum = numStr.replace(d,””);
                            String newDenom = denomStr.replace(d,””);
                            if (newNum.equals(“”) == false && newDenom.equals(“”) == false)
                                if (newDenom.equals(“0”) == false)
                                    if ((double)num/(double)denom == (Double.valueOf(newNum)/Double.valueOf(newDenom)))
                                    {
                                        System.out.format (“%d / %d = %s / %s\n”, num, denom, newNum, newDenom);
                                        numProd *= Double.valueOf(newNum);
                                        denomProd *= Double.valueOf(newDenom);
                                    }
                        }
                }
        return String.valueOf(denomProd/numProd);
    }
}

Euler 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 × 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.
I’m surprise I got this one so easily. Mind you I had to think of a few ways to simplify. One was to realize that if I iterated up to 4000, the resulting product would easily exceed 7 digits, which is the largest possible product size.
Next I had to find an efficient way to confirm if only one digit was used. String.split might have worked, but what if the digit is at the beginning or end? I settled on String.replace, and tested for a reduction in length of only one. Works fast. The answer pops out the end in only 11 seconds.
import java.util.*;

public class Euler32
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 32:\n”);
        Euler32 e = new Euler32();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        ArrayList<Integer> p = new ArrayList<Integer>();
        String [] digits = {“1″,”2″,”3″,”4″,”5″,”6″,”7″,”8″,”9”};
        String num = “”;
        boolean flag = true;
        int len = 0;
        int sum = 0;
        for (int a = 1; a <= 4000; a++)
        {
            for (int b = 1; b <= 4000; b++)
            {
                num = String.valueOf(a)+String.valueOf(b)+String.valueOf(a*b);
                len = num.length();
                flag = true;
                if (num.contains(“0”) == false && len == 9)
                {
                    for (String d: digits)
                    {
                        if (num.replace(d, “”).length() != len -1)
                            flag = false;
                    }
                    if (flag)
                    {
                        if (p.contains(a*b) == false)
                            p.add(a*b);
                        System.out.format(“%s\n”, num);
                    }
                }
            }
        }
        for (int n: p)
            sum +=n;
        return String.valueOf(sum);
    }
}