[seqfan] Diophantine Approximation to Sqrt(n) .
Brad Klee
bradklee at gmail.com
Sat May 5 19:38:06 CEST 2018
Hi Seqfans,
Previously we have debated on the topic of Diophantine approximations [1].
This present effort follows up on the idea of constructing geometric
iterations for sqrt(n), any positive integer n. If you aren't fixated on
the standard Pell equation, and find Newton's method suspect, perhaps this
geometry will interest you.
Intersect a hyperbola "0=H=1-n+p^2-q^2" with a line "0=L=1+q" in two (q,p)
points (-1, sqrt(n)) and (-1, -sqrt(n)). Choose a rational point on the
line with p>sqrt(n) and a rational point on the hyperbola with q>0, p<0.
The line connecting these points has a negative slope and intersects the
hyperbola in another rational point, yet closer to sqrt(n). Reflecting p to
-p between branches sets up an iteration of chords where one point remains
fixed on the line L, while another point takes discrete steps along
hyperbola H. Points of intersection approach arbitrarily near to sqrt(n).
Convergence depends quite obviously on the fixed point, with more rapid
convergence near (-1, sqrt(n)).
As an example, let's compare some of these iterations on sqrt(17) to
A041024 / A041025 :
Fixed Point : (-1,5), Initial Condition : (9/10, -41/10) .
num: 41, 404, 4201, 87413, 1818869, 37846597, 787503061
den: 10, 99, 1020, 21203, 441145, 9179157, 190997565
Fixed Point (-1,21/5), Initial Condition : (9/10, -41/10) .
num: 41, 4201, 1818869, 787503061, 340959723509, 147622960230421,
63915286424196149
den: 10, 1020, 441145, 190997565, 82694879725, 35803826929485,
15501733942269805
Fixed Point (-1,413/100), Initial Condition : (9/10, -41/10) .
num: 41, 26435929, 18006502533001, 12264904563400426169,
8354086734702172892963561, 5690281959403802288882037110809,
3875864568536911769534334994806747721
den: 10, 6412290, 4367218708410, 2974676294501187890,
2026163647808846656648810, 1380096091656970745916672731490,
940035235686276916363314933981021210
The third sequence moves faster than the convergents, gaining about three
digits of decimal precision per iteration. The main disadvantage is that
the fractions are not concise. Perhaps this is reason enough to exclude
these sequences from OEIS?
Cheers,
Brad
PS. Okay, okay, there is one last non-issue about existence of solutions
[2]. The hyperbola H takes such a simple form that it's relatively easy to
find a rational parametrization, "( q(t) , p(t) ) = ( (1-n)/(4 t) + t ,
(1-n)/(4 t) - t )".
[1] starting with:
http://list.seqfan.eu/pipermail/seqfan/2017-September/017940.html
[2] http://www.ams.org/notices/200202/fea-lenstra.pdf
More information about the SeqFan
mailing list