# 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
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
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 ;
a = 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,1);
for (int i = 99; i >= 1; i--)
{
F = F.inverse();
}
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;
}```