Monthly Archives: August 2010

Euler Problem 65

The trauma I went through on Problem 64 made this one a breeze. I also used BigFractions class from this website.

public String algorithm ()
    {
        int [] a = new int [100];
        a[0] = 2;
        int k = 1;
        for (int i = 1; i <= 99; i=i+3)
        {
            if (i <= 99)
                a[i] = 1;
            if (i+1 <= 99)
                a[i+1] = 2*k++;
            if (i+2 <= 99)
                a[i+2] = 1;
        }
        BigFraction F = new BigFraction(a[99],1);
        for (int i = 99; i >= 1; i--)
        {
            F = F.inverse();
            F = F.add(a[i-1]);
        }
        int sum = 0;
        String num = F.numerator().toString();
        for (int n = 0; n <= num.length()-1; n++)
            sum += Integer.parseInt(num.substring(n, n+1));
        return String.format("\nAnswer = %s\n", String.valueOf(sum));
    }

I’m on a roll!


So after I did the photo of M57 below using Maxim DL, I though I would take a crack at some of my less successful images that I had previously processed with Registax.

And here is another fantastic result M81 & 82. The initial images showed practically nothing so I have very little to go on. Maxim cleaned it right up and the result are pretty impressive for only a 30 second exposure. I thinkĀ  its time to pick a decent target and really use up some points.

Euler Problem 64

This one was brutal. Initially I tried writing classes to do Square Roots of BigDecimal and Fractions of BigDecimal. What a Big mess. It was also a learning experience using Regex to find matching patterns in the results. Not pretty and pretty damn slow. My attempts usually ran for 20+ hours at a time.

After three weeks of always getting wrong answers, I started reading mathematical papers. This one caught my eye. Theorem 2.3 shows a method to determine length of a Continued Fraction. The paper even had a super short C routine that I translated for my purposes. No Big Decimal. No Regex. No need to import anything. Kind of embarrassing actually.

Works in about 6 seconds on verbose and 61 miliseconds with no reporting.

public String algorithm ()
    {
        int count = 0;
        for (int n = 1; n <= 10000; n++)
        {
            if ((int)Math.sqrt(n) == Math.sqrt(n))
                continue;
            int period = period_length(n);
            if (period % 2 != 0)
                count++;
            v.appendText(String.format("n:%d period:%d count:%d\n", n, period, count));
        }
        return String.format("\nAnswer = %s\n", String.valueOf(count));
    }
    public int period_length (int n)
    {
        int a_0, a, b, c, b_0, c_0, result=0;
        a_0 = (int) Math.sqrt(n);
        b = a_0;
        b_0 = b;
        c = n - a_0*a_0;
        c_0 = c;
        do
        {
            a = (a_0 + b) / c;
            b = a*c - b;
            c = (n - b*b) / c;
            result++;
        } while ((b != b_0) || (c != c_0));
        return result;
    }

Euler Problem 63

Ummm, am I missing something here? This worked first try.

public String algorithm ()
    {
        int count = 0;
        for (int power = 1; power <= 100; power++)
        {
            for (int base = 1; base <= 100; base++)
            {
                BigInteger Big = new BigInteger(String.valueOf(base));
                Big = Big.pow(power);
                if (Big.toString().length() == power)
                {
                    count++;
                    v.appendText(String.format("Count:%d Base:%d Power:%d Value:%s\n", count, base, power, Big.toString()));
                }
            }
        }
        return String.format("\nAnswer = %s\n", String.valueOf(count));
    }

Euler Problem 62

This one is cool. I figured out two new algorithms that I’m sure will be handy later on.

1) Custom signatures. When comparing long lists, its sometimes easier to create a parallel list of representative tokens. This makes filtering, sorting, counting much easier.

2) Collections can be used to sort lists, but also to count duplicates in them. The frequency method is very fast and useful.

public String Problem ()
    {
        ArrayList<String> cubeList = new ArrayList<String>();
        ArrayList<String> S = new ArrayList<String>();
        for (long i = 345; i <= 9999; i++)
        {
            String cube = String.valueOf((long)i*i*i);
            cubeList.add(cube);
            String sig = "";
            int [] d = {0,0,0,0,0,0,0,0,0,0};
            for (int c = 0; c <= cube.length()-1; c++)
                d[Integer.parseInt(cube.charAt(c)+"")]++;
            for (int n = 0; n <= 9; n++)
                sig += d[n];
            S.add(sig);
        }
        String Five = "";
        for (String s:S)
            if (Collections.frequency(S, s) == 5)
            {
                Five = s;
                break;
            }
        return String.valueOf(cubeList.get(S.indexOf(Five)));
    }

Euler Problem 61

This one seemed tricky, but in the end was a pretty straight forward solution once I simplified the digit checking. The other trick was using my old Permutations class from a previous problem.

    public String Problem ()
    {
        Permutations P = new Permutations();
        ArrayList<String> List = P.makePerms("345678");
        int sum = 0;
        int [] s = new int[6];
        main:
        for (String i: List)
        {
            for (int n = 0; n <= 5; n++)
                s[n] = i.charAt(n)-48;
            ArrayList<Integer> P1 = genList(s[0]);
            ArrayList<Integer> P2 = genList(s[1]);
            ArrayList<Integer> P3 = genList(s[2]);
            ArrayList<Integer> P4 = genList(s[3]);
            ArrayList<Integer> P5 = genList(s[4]);
            ArrayList<Integer> P6 = genList(s[5]);
            for (int p1: P1)
                for (int p2: P2)
                    if (front(p2) == back(p1))
                        for (int p3: P3)
                            if (front(p3) == back(p2))
                                for (int p4: P4)
                                    if (front(p4) == back(p3))
                                        for (int p5: P5)
                                            if (front(p5) == back(p4))
                                                for (int p6: P6)
                                                    if (front(p6) == back(p5))
                                                        if (back(p6) == front(p1))
                                                        {
                                                            System.out.format("%d+%d+%d+%d+%d+%d=%d\n",p1,p2,p3,p4,p5,p6,p1+p2+p3+p4+p5+p6);
                                                            sum = p1+p2+p3+p4+p5+p6;
                                                            break main;
                                                        }
        }
        return String.valueOf(sum);
    }
    public int P (int type, int n)
    {
        int result = 0;
        if (type == 3)
            result = n*(n+1)/2;
        if (type == 4)
            result = n*n;
        if (type == 5)
            result = n*(3*n-1)/2;
        if (type == 6)
            result = n*(2*n-1);
        if (type == 7)
            result = n*(5*n-3)/2;
        if (type == 8 )
            result = n*(3*n-2);
        return result;
    }
    public ArrayList<Integer> genList (int type)
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int n = 0;
        while (P(type,n) < 10000)
        {
            if (P(type,n) > 999 && P(type,n) % 100 > 9)
                list.add(P(type,n));
            n++;
        }
        return list;
    }
    public int front (int p)
    {
        return (int) Math.floor (p/100);
    }
    public int back (int p)
    {
        return p % 100;
    }
    public class Permutations
    {
        ArrayList<String> Perms = new ArrayList<String>();
        public ArrayList<String> makePerms (String s)
        {
            Perms.clear();
            p1("",s);
            return Perms;
        }
        public void p1(String prefix, String s)
        {
            int N = s.length();
            if (N == 0)
            {
                if (Perms.contains(prefix) == false)
                    Perms.add(prefix);
            }
            else
                for (int i = 0; i < N; i++)
                    p1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }
    }