@@ -0,0 +1,1952 @@
+import itertools%0Aimport math%0A%0Afrom fractions import Fraction%0A%0Adef _find_fraction_period_helper(n, nume, sub):%0A    # of the form (nume / (sqrt(n) - sub))%0A%0A    seen_states = set()%0A    period_values = %5B%5D%0A%0A    while True:%0A        current_state = (nume, sub)%0A        if current_state in seen_states:%0A            return period_values%0A        seen_states.add(current_state)%0A%0A        # We start with%0A        #   nume / (sqrt(n) - sub)%0A        # then convert this to%0A        #   nume * (sqrt(n) + sub) / (n - sub ** 2)%0A        # by multiplying top and bottom by (sqrt(n) + sub).%0A%0A        # This is the value of the denominator after we flip the fraction.%0A        # We also know that %60nume%60 evenly divides (n - sub ** 2), so we factor%0A        # that in immediately.%0A        denom = int((n - sub ** 2) / nume)%0A        # To compute the next period value, we take the integer portion of this%0A        # new fraction.%0A        next_value = int((math.sqrt(n) + sub) / denom)%0A        period_values.append(next_value)%0A        # Subtract (next_value * (denom/denom))%0A        sub = -(sub - denom * next_value)%0A        nume = denom%0A%0A%0Adef get_partial_values(n):%0A    first = int(math.sqrt(n))%0A    period = _find_fraction_period_helper(n, 1, first)%0A    pvs = itertools.chain(%5Bfirst%5D, itertools.cycle(period))%0A    return pvs%0A%0A%0Adef gen_convergents(pvs):%0A    current = next(pvs)%0A    yield current%0A    # Lazily recurse in continued fraction form%0A    fun = lambda x: current + Fraction(1, x)%0A    yield from map(fun, gen_convergents(pvs))%0A%0A%0Adef solve():%0A    MAX = 1000%0A    max_x = (0, 0)%0A    for d in range(1, MAX + 1):%0A        if int(math.sqrt(d)) ** 2 == d:%0A            continue%0A        for conv in gen_convergents(get_partial_values(d)):%0A            if conv.numerator ** 2 - d * conv.denominator ** 2 == 1:%0A                max_x = max(max_x, (conv.numerator, d))%0A                break%0A    return max_x%5B1%5D%0A%0A%0Aif __name__ == '__main__':%0A    print('The answer is %7B%7D'.format(solve()))%0A

Solve problem 66