Tag Archives: fractions

Euler Problem 73

Just use brute force to test the GCD for each iteration.

#Euler73
class Algorithms:
    def gcd(self, a, b):
        while b:
            a, b = b, a%b
        return a
class Problem73:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range(5, self.limit+1):
            for d in range(n/3 + 1, (n-1)/2 + 1):
                if self.Euler.gcd(n,d) == 1:
                    count += 1
            if n % 1000 == 0:
                print n, count
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem73(12000)
    print P.Solution()

Euler Problem 71

A lot of simplification and reduction. Not too complicated. Nice and short. Runs fast.

#Euler71
class Problem71:
    def __init__(self, limit):
        self.limit = limit
    def Solution(self):
        min = 0
        min_n = 0
        for n in range (int(min*self.limit), int(self.limit*float(3)/7)):
            f = float(n)/self.limit
            if f < float(3)/7:
                if f > min:
                    min = f
                    min_n = n
        return "Answer:"+str(min_n)
if __name__ == '__main__':
    P = Problem71(1000000)
    print P.Solution()

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));
    }

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;
    }