Monthly Archives: July 2010

Euler Problem 60

This is a real exercise in efficiency. Stay away from variable declarations, trick parseInt to convert strings and test using OR not AND.

public String Problem ()
    {
        int P [] = new int [5];
        int sum = 0;
        for (int i = 2; i < primeLimit; i++)
            isP[i] = true;
        for (int p = 2; p*p < primeLimit; p++)
            if (isP[p] == true)
                for (int m = p*p; m < primeLimit; m = m+p)
                    if (m % p == 0)
                        isP[m] = false;
        mainLoop:
        for (P[0] = 3; P[0] < testLimit; P[0] = nextP(P[0]))
        {
            for (P[1] = nextP(P[0]); P[1] < testLimit; P[1] = nextP(P[1]))
            {
                if (!isP[Integer.parseInt(P[0] + "" + P[1])] ||
                !isP[Integer.parseInt(P[1] + "" + P[0])])
                    continue;
                for (P[2] = nextP(P[1]); P[2] < testLimit; P[2] = nextP(P[2]))
                {
                    if (!isP[Integer.parseInt(P[0] + "" + P[2])] ||
                    !isP[Integer.parseInt(P[1] + "" + P[2])] ||
                    !isP[Integer.parseInt(P[2] + "" + P[0])] ||
                    !isP[Integer.parseInt(P[2] + "" + P[1])])
                        continue;
                    for (P[3] = nextP(P[2]); P[3] < testLimit; P[3] = nextP(P[3]))
                    {
                        if (!isP[Integer.parseInt(P[0] + "" + P[3])] ||
                        !isP[Integer.parseInt(P[1] + "" + P[3])] ||
                        !isP[Integer.parseInt(P[2] + "" + P[3])] ||
                        !isP[Integer.parseInt(P[3] + "" + P[0])] ||
                        !isP[Integer.parseInt(P[3] + "" + P[1])] ||
                        !isP[Integer.parseInt(P[3] + "" + P[2])])
                            continue;
                        for (P[4] = nextP(P[3]); P[4] < testLimit; P[4]= nextP(P[4]))
                        {
                            if (!isP[Integer.parseInt(P[0] + "" + P[4])] ||
                            !isP[Integer.parseInt(P[1] + "" + P[4])] ||
                            !isP[Integer.parseInt(P[2] + "" + P[4])] ||
                            !isP[Integer.parseInt(P[3] + "" + P[4])] ||
                            !isP[Integer.parseInt(P[4] + "" + P[0])] ||
                            !isP[Integer.parseInt(P[4] + "" + P[1])] ||
                            !isP[Integer.parseInt(P[4] + "" + P[2])] ||
                            !isP[Integer.parseInt(P[4] + "" + P[3])])
                                continue;
                            System.out.format("P[0]:%d P[1]:%d P[2]:%d P[3]:%d P[4]:%d\n", P[0],P[1],P[2],P[3],P[4]);
                            sum = P[0]+P[1]+P[2]+P[3]+P[4];
                            break mainLoop;
                        }
                    }
                }
            }
        }
        return String.valueOf(sum);
    }
    public int nextP (int P)
    {
        P++;
        while (isP[P] == false)
            P++;
        return P;
    }

Euler Problem 59

There are two key points here. The key consists of lower case letters, so although its a brute force attack you can reduce the scope to speed it up. The second is when testing the resulting string, search for multiple occurences of the most common English words.

public String Problem ()
    {
        String cipher = "", line = "";
        int key [] = new int [3];
        int cycle = 0, result = 0;
        try
        {
            FileInputStream stream = new FileInputStream("F:/Development/Java/EULER/src/euler/cipher1.txt");
            DataInputStream in = new DataInputStream(stream);
            BufferedReader buffer = new BufferedReader(new InputStreamReader(in));
            line = buffer.readLine();
            in.close();
        }
        catch (Exception e)
        {
              System.out.print(e+"\n");
        }
        MAIN:
        for (key[0] = 97; key[0] <= 122; key[0]++)
        {
            for (key[1] = 97; key[1] <= 122; key[1]++)
            {
                for (key[2] = 97; key[2]  5 && numOccur(cipher,"and") > 3)
                    {
                        System.out.format ("[0][1][2]:[%d][%d][%d]:%s [...]\n", key[0],key[1],key[2],cipher.substring(0, 100));
                        break MAIN;
                    }
                }
            }
        }
        for (int c = 0; c <= cipher.length()-1; c++)
        {
           result += cipher.charAt(c);
        }
        return String.valueOf(result);
    }
    public int numOccur (String source, String target)
    {
        int count = 0;
        int start = source.indexOf(target);
        while (start != -1)
        {
            count++;
            start = source.indexOf(target, start+target.length());
        }
        return count;
    }

Pigs are more aerodynamic than previously thought.

I bought a Mac. Actually a Mac Mini for the LCD TV in the livingroom. The Dell notebook I was using was starting to act wonky. I decided to head for the dark side after recently getting an iPhone — which totally rocks by the way. I figured Macs can’t be all that bad if they’re like my iPhone. And besides everyone says Macs are great for multimedia, which is what this thing is supposed to do.

The Mini works flawlessly. I’m actually astonished at the lack of bloatware. Normally with new PC hardware it takes me an hour to clear off crap I don’t need. The nice clean OS X interface is a pleasant change. But finding stuff does takes some getting used to as its all in different locations, but application management has never been easier.

My primary Dell Notebook at home is still working well, but maybe for the next upgrade a MacBook might be considered. I hear OS X and Java integration is pretty tight. Worth playing with …

Euler Problem 58

This one was pretty easy except for the fact that I need about 1024M of heap space to run it. 800M prime numbers will do that you know. Initially did it with ArrayLists but took too long. Used raw boolean arrays and dropped it to 4 mins.

public String Problem ()
    {
        Primes P = new Primes();
        P.buildPrimes();
        double ratio = 1;
        int count = 0, side = 3, number = 3;
        while (ratio >= .1)
        {
            if (side > 3)
                number += (side - 1);
            for (int i = 1; i <= 3; i++)
            {
                if (P.testPrime(number))
                    count++;
                number += (side - 1);
            }
            ratio = (double) count/(2*side-1);
            side = side + 2;
        }
        return String.valueOf(side-2);
    }
    public class Primes
    {
        int limit = 800000000;
        boolean [] isPrime = new boolean [limit];
        public void buildPrimes ()
        {
            for (int i = 2; i < limit; i++)
                isPrime[i] = true;
            for (int p = 2; p*p < limit; p++)
                if (isPrime[p] == true)
                    for (int m = p*p; m < limit; m = m+p)
                        if (m % p == 0)
                            isPrime[m] = false;
        }
        public boolean testPrime (int num)
        {
            return isPrime[num];
        }
    }

Euler Problem 57

With a little research, you realize that this continued fraction is related to Pell numbers and Companion Pell numbers. Wikipedia has some simple formulas to implement to calculate a given numerator or denominator. Just be sure to use BigInteger class for the number representation as they can get pretty big.

    import java.math.*;

    public class Euler57
    {
        public static void main(String[] args)
        {
            Euler57 e = new Euler57();
            System.out.format(“Problem: %s\n”, e.getClass().getName());
            System.out.format(“Answer = %s\n”, e.Problem());
        }
        public String Problem ()
        {
            int count = 0;
            BigInteger [] N = new BigInteger[1001];
            BigInteger [] D = new BigInteger[1001];
            for (int f = 1; f  2)
                {
                    N[f] = N[f-1].multiply(BigInteger.valueOf(2));
                    N[f] = N[f].add(N[f-2]);
                    D[f] = D[f-1].multiply(BigInteger.valueOf(2));
                    D[f] = D[f].add(D[f-2]);
                }
                if (N[f].toString().length() > D[f].toString().length())
                    count++;
            }
            return String.valueOf(count);
        }
    }

Euler Problem 56

Easy. Used BigInteger class and long variables just to be on the safe side. Didn’t need to be. Small answer.

    import java.math.*;

    public class Euler56
    {
        public static void main(String[] args)
        {
            Euler56 e = new Euler56();
            System.out.format(“Problem: %s\n”, e.getClass().getName());
            System.out.format(“Answer = %s\n”, e.Problem());
        }
        public String Problem ()
        {
            long max = 0;
            for (int a = 1; a < 100; a++)
                for (int b = 1; b  max)
                        max = GooSum;
                }
            return String.valueOf(max);
        }
        public long digitalSum(String number)
        {
            long sum = 0;
            for (int n = 0; n <= number.length()-1; n++)
                sum += (number.charAt(n)-48);
            return sum;
        }
    }

Euler Problem 55

Not too tricky. Use the BigInteger class.

    import java.math.*;

    public class Euler55
    {
        public static void main(String[] args)
        {
            Euler55 e = new Euler55();
            System.out.format(“Problem: %s\n”, e.getClass().getName());
            System.out.format(“Answer = %s\n”, e.Problem());
        }
        public String Problem ()
        {
            int count = 0;
            for (int n = 1; n < 10000; n++)
            {
                BigInteger N = new BigInteger (String.valueOf(n));
                boolean flag = true;
                for (int i = 1; i <= 50; i++)
                {
                    N = N.add(new BigInteger (Rev(N.toString())));
                    System.out.format(“Number:%d Iteration:%d Sum:%s\n”,n, i, N.toString());
                    if (N.toString().equals(Rev(N.toString())))
                    {
                        System.out.format(“Palindrome in %d. Count = %d\n”,i,count);
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    count++;
            }
            return String.valueOf(count);
        }
        public String Rev (String n)
        {
            return new StringBuffer(n).reverse().toString();
        }
    }