Continued fractions and quadratic surds

I became interested in the nearest square (NSCF), nearest integer (NICF) and optimal continued fraction (OCF) through Jim White of the ANU, around October 2007. Prior to that I had avoided studying half-regular continued fractions (HRCF). 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  8 below, NSCF has some nice properties. For example, the period-length of the NSCF expansion for √D is no 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 11 below.

One problem remains: Find a more explicit definition of reduced NSCF quadratic surd.

  1. BCMATH continued fraction programs
  2. On the regular continued fraction (RCF) expansion of √22n+1 (pdf)
  3. Some continued fraction identities (pdf)
  4. Primitive Pythagorean triples and the negative Pell equation (pdf)
  5. A unimodular matrix and Pell's equation (pdf)
  6. Reduced quadratic irrationals and Pell's equation (pdf)
  7. 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)
  8. 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 paper was indistinct in many places. Also I have expanded and changed the author's proofs in some places when they were hard to follow.
  9. The nearest square continued fraction expansion of (p+q+√{p2+q2})/p, where p > 2q > 0, gcd(p,q)=1
  10. On the definition of nearest integer reduced quadratic surd (with John Robertson)
  11. Midpoint criteria for solving Pell's equation using the nearest square continued fraction with John Robertson and Jim White, Math. Comp. 79 January (2010), 485-499
  12. John P. Robertson and Keith R. Matthews, A continued fractions approach to a result of Feit, The American Mathematical Monthly 115 April (2008), 346-349
  13. 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
  14. Unisequences and nearest integer continued fraction midpoint criteria for Pell's equation, Journal of Integer Sequences, 12 (2009), Article 09.6.7
  15. Period 2 NSCF and NICF expansions of √D (23rd April 2009)
  16. Continuants and half-regular continued fractions (updated 24th April 2009)
  17. Testing a quadratic surd for being NSCF reduced
Page layout: Alan Offer
Keith Matthews Last modified 13th February 2010