In this post, we will try to solve project Euler problem 66 called "Diophantine equation". It revolves around the following equation:
$$ x^2 – D \, y^2 = 1 $$Some help is provided by the text:
What we need to do in order to solve the problem question is two-fold:
Wikipedia has a nice link about this equation, which is called Pell's equation. Geometrically, this equation ressembles a parabola.
from pylab import *
%matplotlib inline
from IPython.html.widgets import interact
y = linspace(0, 20)
def plot_equation(D):
x_plus = sqrt(1 + D * y**2)
x_minus = -sqrt(1 + D * y**2)
plot(x_plus, y)
plot(x_minus, y)
plot(x_plus, -y)
plot(x_minus, -y)
grid(True)
xlim(-y.max(), y.max())
ylim(-y.max(), y.max())
interact(plot_equation,
D=(1, 10))
As one can see from the plots below, the higher D, the smaller the angle of the upward pointing branches of the graphical form:
figure(figsize=(10, 4))
subplot(131)
plot_equation(1)
title('$D = 1$')
subplot(132)
plot_equation(10)
title('$D = 10$')
subplot(133)
plot_equation(100)
title('$D = 100$')
<matplotlib.text.Text at 0xb9c3080>
We are looking for minimal solutions which I gather from wikipedia can be obtained via an algorithm converging to the square root of D using continued fractions. We use the following recurrence equations:
$$ \begin{align} A_{-1}& = 1& B_{-1}& = 0\\ A_0& = b_0& B_0& = 1\\ A_{n+1}& = b_{n+1} A_n + a_{n+1} A_{n-1}& B_{n+1}& = b_{n+1} B_n + a_{n+1} B_{n-1}\, \end{align} $$def converge_to_sqrt(D):
File "<ipython-input-6-18198abe484a>", line 2 ^ IndentationError: expected an indented block