Continued fractions and quadratic surds

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 appears to be essentially the same as, but harder to describe than, the OCF. I marvel at the way Selenius was able to navigate the complexity of the notation in his 1960 paper and discover nice results, some of which I have been able to prove in the case of OCF. Selenius first obtains the regular continued fraction (RCF) and replaces all 1's by a process of singularisation. So far the notation and the fact that it is in German, prevent me from even programming SK!
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 3 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 12 below.

• Prove the conjectures on the structure of OCF for a general quadratic surd at the end of paper 10 below. That paper gives the answer for √D.
• Prove that L_NICF = L_NSCF - ie. the period-lengths of the NICF and NSCF expansions of √D are equal. This is a conjecture of John Robertson and Jim White.
• Is there a sufficient condition for rational number x/y, x > 0, y > 0, gcd(x,y)=1 to be an NSCF convergent to ξ?
  For example H.C. Williams and P.A. Buhr, Calculation of the regulator of Q(√D) by use of the nearest integer continued fraction algorithm, Math. Comp. 33 (1979) 369-381, Theorem page 371, give one for the nearest integer continued fraction of Hurwitz: if β = (3+√5)/2, then

  |ξ - x/y| < 1/(βy^2) implies x/y is a Hurwitz NICF convergent to ξ.

1. BCMATH continued fraction programs
2. On the regular continued fraction (RCF) expansion of √2²ⁿ⁺¹ (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 Ax² - By² = 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 (pdf 347K) 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. (Updates - footnote on page 37, 31st March 2008)
9. The nearest square continued fraction expansion of (p+q+√p²+q²)/p, where p > 2q > 0, gcd(p,q)=1
10. Some connections between the optimal continued fraction (OCF) and the nearest square continued fraction (NSCF) (last updated 31st March 2008)
11. On the definition of nearest integer (NICF) reduced quadratic surd (joint with John Robertson)
12. Midpoint criteria for solving Pell's equation using the nearest square continued fraction, (joint with John Robertson and Jim White, to be submitted)
13. 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
14. 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', (to appear, Mathematics of Computation)

Keith Matthews Last modified 6th May 2008