From: Jpr2718@aol.com (John Robertson)
Subject: Periods of Continued Fractions
Date: 5 May 00 12:58:29 GMT
Newsgroups: sci.math.numberthy

In reply to some queries I made regarding the length of the period of
continued fractions of sqrt(d), Hugh Williams suggested the following
references:

R. G. Stanton, C. Sudler, Jr., and H. C. Williams, "An Upper Bound for
the Period of the Simple Continued Fraction for Sqrt(D)," Pacific
Journal of Math., Vol. 67 (1976), No. 2, pp. 525-536.

H. C. Williams, "A Numerical Investigation Into the Length of the
Period of the Continued Fraction Expansion of Sqrt(D)," Mathematics of
Computation, Vol. 36 (April 1981), No. 154, pp. 593-601.

C. D. Patterson and H. C. Williams, "Some Periodic Continued Fractions
with Long Periods," Mathematics of Computation, Vol. 44 (April 1985),
No. 170, pp. 523-532.

Assuming the extended Riemann Hypothesis for zeta_Q(sqrt(D)) and
Levy's Law, for squarefree D it follows that p(D)/f(D) < 1.50103 +
o(1), where p(D) is the length of the period of the continued fraction
expansion of sqrt(D) and f(D) = sqrt(d)*ln(ln(D)) for D==1 (mod 8) and
f(D)= sqrt(d)*ln(ln(4D)) otherwise.

These papers list quite a few D with p(D)/f(D) greater than 1.0.  For
D=46257585588439, p(D) = 25679652, p(D)/f(D) = 1.081244, and
p(D)/sqrt(D) = 3.776.

Comments are also made on the propensity of D with long periods to be
quadratic residues of small primes.

Wladyslaw Narkiewicz adds, "It has been shown by V.D.Podsypanin
(Uchen. Zapiski Nauchn. Semin. LOMI, 82, 1979, 95--99) that the
Extended Riemann hypothesis implies the bound $O(\sqrt d\log\log d)$
for it.  On the other hand J.C.Lagarias (Trans. Amer.Math.Soc. 260,
1980, 485-508) obtained the lower bound $(1/3)/sqrt d\log^{-1}d$ for
infitely many squarefree $d$'s."

I am still interested in any comments on my observation, based on
numerical evidence, that for D=1 (mod 4), if x=l(sqrt(D)) and
y=l((1+sqrt(D))/2), where l(*) is the length of the period of the
continued fraction of *, then x/y falls between 1/3 and 5 inclusive.
In fact, it appears that x+y is divisible by 4 if x/y is near 1 and
x-y is divisible by 4 if x/y is near 3.

John Robertson
==============================================================================

From: igor@txc.com (Igor Schein)
Subject: Re: Periods of Continued Fractions
Date: 1 May 00 17:55:59 GMT
Newsgroups: sci.math.numberthy

On Sat, Apr 22, 2000 at 04:30:54PM -0400, John Robertson wrote:
> Where can I find a proof that the period of the continued fraction
> expansion of sqrt(d) is at most 4*sqrt(d)*ln(d) [call this period
> L(d)]?  (A. Rockett and P. Szusz, Continued Fractions, prove that this
> upper bound is O(sqrt(d)*ln(d))).  Is a better upper bound known?  Are
> other upper bounds conjectured?

Without any proofs, just based on looking at empirical data, I think
that L(d) is O(sqrt(d)*ln(ln(d))).  In particular,

L(d) < 2.3*sqrt(d)*ln(ln(d))

The maximum occurs at
d=7, L(d)=4, L(d)/(sqrt(d)*ln(ln(d)))=2.27098

Any comments?

Thanks

Igor