Continued fraction for $\sqrt{D}$ upper bound of cycle length Is there a formula for determining the upper bound for the length of the cycle for the continued fraction expansion of $\sqrt{D}$? I am attempting to expand for $D=4097280036$ and have tried up to 3500 loops but no luck. Does the repetitive cycle have even longer length? Or might I have made a calculation error? Note that I am using bigint-like calculations so that should be OK and indeed for other values for $D$ it all works fine so I guess I just bumped into an extraordinary long cycle. Anyway - is there a formula in D stating what the (theoretical) upper bound for the cycle length is? And how often one lands up in these very long cycles?

There are no easy lower bounds as the length is very small for numbers such as $\sqrt{n^2+1}$ or $\sqrt{n^2+2}$. There is an upper bound mentioned by Will Jagy, which is $\sqrt D \log D$.

However, Will Jagy is wrong; you did not do a mistake. The period length of the continued fraction of $\sqrt{4097280036}$ is astonishing $13032$, much more than what you tried!

Sage code:


def continued_fraction_complete(x) :
iteratives = dict()
coefficients = list()
while x not in iteratives :
iteratives[x] = len(coefficients)
a = floor(x)
coefficients.append(a)
x = 1/(x-a)
return tuple(coefficients[:iteratives[x]]), tuple(coefficients[iteratives[x]:])

D = 4097280036
K. = QuadraticField(4097280036)
p0,p1 = continued_fraction_complete(b)
print len(p0), len(p1)


Output: `1 13032` (pre-period and period)