Tag Archives: square root

Euler Problem 206 – Don’t be such a square!


Check out the wikipedia article on square numbers (the numbers article, not the algebra one).
A couple few interesting properties emerge that can be exploited.

http://en.wikipedia.org/wiki/Square_number

1) A square number can end only with digits 00,1,4,6,9, or 25 in base 10; So that eliminates 2 digits, we now end with a 9.
2) Squares of odd numbers are odd.
3) If the last digit of a number is 3 or 7, its square ends in 9.

and if, and if, and if … you get the idea.

PS. I could have used the divisible by 4 rule also here, but I didn’t need to. This routine still runs in under a minute without importing psyco.

class Problem:
    def test (self, n):
        N = str(n*n)
        if N[0] == '1':
            if N[2] == '2':
                if N[4] == '3':
                    if N[6] == '4':
                        if N[8] == '5':
                            if N[10] == '6':
                                if N[12] == '7':
                                    if N[14] == '8':
                                        if N[16] == '9':
                                            return True
        return False
    def Solution(self):
        number = 0
        start = int(math.floor(math.sqrt(10203040506070809)))
        end = int(math.floor(math.sqrt(19293949596979899)))
        for i in range (start,end):
            if i % 2 != 0:
                if int(str(i)[-1]) == 3 or int(str(i)[-1]) == 7:
                    if self.test(i) == True:
                        number = int(math.sqrt(int(str(i*i)+"00")))
                        break
        print "Answer =", number
if __name__ == '__main__':
    P = Problem()
    P.Solution()

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