Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

On a relationship between the convergents of the nearest integer and regular continued fractions


Author: William W. Adams
Journal: Math. Comp. 33 (1979), 1321-1331
MSC: Primary 10K10; Secondary 10K15
MathSciNet review: 537978
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we derive a relation concerning the speed of convergence of the nearest integer and regular continued fractions. If $ {A_n}/{B_n}$, $ {p_k}/{q_k}$ denote the convergents of the nearest integer and regular continued fractions of an irrational number $ \alpha $, then for all n there is a $ k(n)$ such that $ {A_n}/{B_n} = {p_{k(n)}}/{q_{k(n)}}$. It is shown that

$\displaystyle \mathop {\lim }\limits_{n \to \infty } \;\frac{n}{{k\left( n \right)}} = \frac{{\log \left( {\frac{{1 + \sqrt 5 }}{2}} \right)}}{{\log \;2}}$

for almost all $ \alpha $. This problem is reduced to a special case of a general result concerning the frequency of partial quotients in the regular continued fraction (Theorem 2).

References [Enhancements On Off] (What's this?)

  • [1] P. BILLINGSLEY, Ergodic Theory and Information, Wiley, New York, 1965. MR 0192027 (33:254)
  • [2] A. KHINTCHINE, Continued Fractions, Univ. of Chicago Press, Chicago, 1964.
  • [3] W. PHILIPP, "Some metrical theorems in number theory," Pacific J. Math., v. 29, 1967, pp. 109-127. MR 0205930 (34:5755)
  • [4] D. SHANKS, Review of the UMT file: "Two related quadratic surds having continued fractions with exceptionally long periods," Math. Comp., v. 28, 1974, pp. 333-334. MR 0352049 (50:4537)
  • [5] J. SCHOCKLEY, Introduction to Number Theory, Holt, Rinehart and Winston, New York, 1967. MR 0210649 (35:1535)
  • [6] H. WILLIAMS & J. BROERE, "A computational technique for evaluating $ L(1,\chi )$ and the class number of a real quadratic field," Math. Comp., v. 30, 1976, pp. 887-893. MR 0414522 (54:2623)
  • [7] H. WILLIAMS & P. BUHR, "Calculation of the regulator of $ Q(\sqrt d )$ by use of the nearest integer continued fraction algorithm," Math. Comp., v. 33, 1979, pp. 369-381. MR 514833 (80e:12003)
  • [8] H. WILLIAMS, "Some results concerning the nearest integer continued fraction algorithm," J. Reine Angew. Math. (To appear.)
  • [9] G. J. RIEGER, "Über die mittlere Schrittanzahl bei Divisionsalgorithmen," Math. Nachr., v. 82, 1978, pp. 157-180. MR 0480366 (58:533)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10K10, 10K15

Retrieve articles in all journals with MSC: 10K10, 10K15


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1979-0537978-9
Article copyright: © Copyright 1979 American Mathematical Society