Continued fractions and quadratic surds

I became interested in the nearest square (NSCF), nearest integer (NICF) and optimal (OCF) continued fractions through Jim White of the ANU, around October 2007. Coincidentally John Robertson had also been studying the NSCF and NICF and joined the discussion. NICF refers here to a half-regular continued fraction where the partial numerators are allowed to be ±1, in contrast to the nearest integer continued fraction of Adolf Hurwitz and B. Minnegerode, where the partial numerators are all -1. I should also mention Selenius' ideal relative approximation continued fraction (IACF or SK) which is the same as the OCF, but somewhat harder to describe. Selenius first obtains the regular continued fraction (RCF) and replaces all 1's by a process of singularisation. For quadratic surds, the period-lengths of OCF and SK are sometimes double that of the period-length of the corresponding NSCF. Contrary to a disparaging review by D.H. Lehmer of A.A.K. Ayyangar's paper below, NSCF has some nice properties. For example, the period-length of the NSCF expansion for √D is not greater than and can be much shorter than the RCF period-length. Also there are three mid-point criteria for solving Pell's equation - see paper 13 below.
  1. BCMATH continued fraction programs
  2. On the regular continued fraction (RCF) expansion of √22n+1 (pdf).
  3. T.H. Jackson, K.R. Matthews, On Shanks' algorithm for computing the continued fraction of logba, Journal of Integer Sequences 5 (2002) article 02.2.7.

    4. We give a more practical variant of Shanks' 1954 algorithm for computing the continued fraction of logba for integers a > b > 1. See the online BCMath program. Here are the first 1000 partial quotients of the continued fraction expansion of log23.
  4. K.R. Matthews, R.F.C. Walters, Some properties of the continued fraction expansion of (m/n)e1/q, Proc. Camb. Phil. Soc. 67 (1970) 67-74.
    This used the 2x2 matrix point of view that R.F.C. Walters had successfully employed in his novel proofs of the continued fraction expansion of e1/q and e2/q (see R.F.C. Walters, Alternate derivation of some regular continued fractions, J. Austr. Math. Soc 8 (1968), 205-212). We used a result of D.N. Lehmer Arithmetical theory of certain Hurwitzian continued fractions, Amer. J. Math. 40 (1918) 375-390. Also see online BCMath program.
  5. Some continued fraction identities (pdf).
  6. Primitive Pythagorean triples and the negative Pell equation (pdf) - see BCMATH program.
  7. A unimodular matrix and Pell's equation (pdf).
  8. Reduced quadratic irrationals and Pell's equation (pdf).
  9. Solving Ax2 - By2 = N in integers, where A > 0, B > 0 and D = AB is not a perfect square and gcd(A,B) = gcd(A,N) = 1 (pdf).
    This generalises the LMM method for solving x2 - Dy2 = N.
  10. Latexed version of Theory of the nearest square continued fraction, A.A. Krishnaswami Ayyangar, J. Mysore Univ. Sect. A, 1, (1941) 97-117.
    The original is somewhat indistinct in some places, so I retyped it in Latex, expanding and changing the author's proofs in some places when they were hard to follow.
  11. The nearest square continued fraction expansion of ξ = (p+q+√{p2+q2})/p, where p > 2q > 0, gcd(p,q)=1.
    ξ has a purely periodic NSCF expansion. A.A.K. Ayyangar proved that the least period contains at most two complete quotients ξh of this form. We give a variant of his proof.
  12. On the definition of nearest integer reduced quadratic surd (with John Robertson).
    Hurwitz gave a definition of reduced quadratic surd for his nearest integer continued fraction expansion which characterises purely periodic surds. We give a more accessible proof.
  13. Converting the regular continued fraction of √D to the nearest integer continued fraction
  14. Keith R. Matthews, John P. Robertson, Jim White, Midpoint criteria for solving Pell's equation using the nearest square continued fraction, Math. Comp. 79 January (2010), 485-499.
    We derive midpoint criteria for Pell's equation x2-Dy2=±1, using the nearest square continued fraction expansion of √D. The period of the expansion is on average 70% that of the regular continued fraction. We also derive similar criteria for the diophantine equation x2-xy-((D-1)/4)y2=±1, where D ≡ 1 (mod 4). We also present some numerical results and conclude with a comparison of the computational performance of the regular, nearest square and nearest integer continued fraction algorithms.
  15. John P. Robertson, Keith R. Matthews, A continued fractions approach to a result of Feit, The American Mathematical Monthly 115 April (2008), 346-349.
    For any non-square positive integer D for which x2 − Dy2 represents −1, we use the regular continued fraction algorithm to generate particular a and b so that D = a2 + b2, where a is always odd and the parity of b is opposite that of D. We also give explicit solutions to x2 − Dy2 = ±a and x2 − Dy2 = ±2b.
  16. Keith R. Matthews, John P. Robertson, Jim White, Corrigenda to `Calculation of the regulator of Q(√D) by use of the nearest integer continued fraction algorithm', Mathematics of Computation 78, Number 265, January (2009), 615-616.
    While studying the nearest integer continued fraction expansion of √D, we noticed some errors in a paper of H.C. Williams and P.A. Buhr.
  17. Keith R. Matthews, Unisequences and nearest integer continued fraction midpoint criteria for Pell's equation, Journal of Integer Sequences, 12 (2009), Article 09.6.7.
    The nearest integer continued fractions of Hurwitz, Minnegerode (NICF-H) and in Perron's book Die Lehre von den Kettenbrüchen (NICF-P) are closely related. Midpoint criteria for solving Pell's equation x2-Dy2=±1 in terms of the NICF-H expansion of √D were derived by H.C. Williams using singular continued fractions. We derive these criteria without the use of singular continued fractions. We use an algorithm for converting the regular continued fraction expansion of √D to its NICF-P expansion.
  18. Period  two NSCF and NICF expansions of √D (23rd April 2009).
    19. This proves a conjecture of John Robertson.
  19. Continuants and half-regular continued fractions.
    Alan Offer responded to my challenge to give proofs of Perron's inequalities (8) and (9) in §37, pages 135-136, using only the Bλ and not employing the continuants Bλ,ν .
  20. Testing a quadratic surd for being NSCF reduced.
    This used the fact that (i) if ξ is NSCF-reduced, then ξ or ξ - 1 is RCF-reduced and (ii) the NDCF expansion of an NSCF reduced surd is obtained from the RCF positive--negative expansion by a process involving jumps of one or two RCF complete quotients. It was superceded by the more elegant and efficient test of item 9 below.
  21. Keith R. Matthews, John P. Robertson, Period length equality for the nearest integer and nearest square continued fraction expansions of a quadratic surd, Glasnik Matematički, 46.2, 269-282, December 2011.
    We prove equality of the period-lengths of the nearest integer continued fraction and the nearest square continued fraction, for arbitrary real quadratic irrationals, using inequalities for approximation constants Θn due to W. Bosma and C. Kraaikamp.
  22. Keith R. Matthews, John P. Robertson, On Purely Periodic Nearest Square Continued Fractions, Journal of Combinatorics and Number Theory, 2, issue 3 (2010) 239-244.
    We present a test for determining whether a real quadratic irrational has a purely periodic nearest square continued fraction expansion. This test is somewhat more explicit than the standard test and simplifies the programming of the algorithm
  23. Keith R. Matthews, On the optimal continued fraction expansion of a quadratic surd, J. Austr. Math Soc., 93 (2012), issue 1-2, 133-156.
    We describe the period structure of the optimal continued fraction expansion of a quadratic surd, in terms of the period of the nearest square continued fraction expansion. The analysis results in a faster algorithm for determining the optimal continued fraction expansion of a quadratic surd and has been implemented in a BCMATH program.
  24. On the convergents of semi-regular continued fractions (revised 25th November 2010).
  25. K.R. Matthews, J.P. Robertson, J. White, On a diophantine equation of Andrej Dujella, Math. Glasnik, vol. 48, number 2, 2013.
    We investigate positive solutions (x,y) of the Diophantine equation x2-(k2+1)y2=k2 which satisfy y < k-1, where k ≥ 2. It has been conjectured by Andrej Dujella in 2009 that there is at most one such solution for each k.

    26. Improved version of slidetalk given at the ANU on 30th November 2012.
Page layout: Alan Offer
Keith Matthews Last modified 8th December 2020