Period length in the continued fraction expansio of sqrt(n)

[Thomas Baruchel]

Hi,

thanks to my assembly code http://baruchel.free.fr/~thomas/wp/?p=10
I could compute the length of the period for the continued fraction
expansion of integer numbers up to 1,000,000,000. Of course I didn't
keep them, but made partial sums of them in several arrays:
   * for each integer k (in fact I mainly cared about primes) < 100,
     compute the k partial sums of periods for n%k (n modulo k).
     As you can see, my partial sums where put in a kind of triangle:
       2: (sum for n even) (sum for n odd)
       3: (sum for n=3m) (sum for n=3m+1) (sum for n=3m+2)
       etc.
     This can be done in Fortran or C by using the "double type",
     in which the exact integer value will fit during the whole
     computation (8 bytes floating point is OK; don't waste your
     CPU time with a 10 byte "long double" type which will not bring
     anything more).
This allows to use a very small amount of memory for what follows:
   * Every minute, hour or whatever, use the partial sums for computing
     the Fourier transform for rational frequencies:
       1/2, 1/3, 2/3, 1/5, 2/5, etc.
     (computing a DFT for a very large set of datas will show that only
     rational frequencies are involved)
     and immediately make the inverse transform (backwards) for computing
     the "contribution" of these frequencies; immediately then add
     all the k "contributions" for a given denominator.
     Now, for each k and each n%k, you have a real value, such that your
     period is the sum (running over the different values of k) of these
     real values. This is a little more complicated when the denominator
     is not a prime; for that reason, I mainly studied primes.
OK. Now, what can you notice?
   * Take a value like k=7, and print the 7 different real "cumulated
     contributions of frequencies with denominator 7" according to
     the 7 values of n%7. You see that there are only three really
     different values: one (negative) for n%7=0, and two other
     appearing exactly three times each. Take k=11; you will see the
     same. What is the rule? You quickly will notice that (for k prime)
     the three cases are the following:
       n%k = 0
       (n/k) = -1  (with the Legendre symbol)
       (n/k) = 1   (with the Legendre symbol)
Then you probably immediately think to something like formula (2) at
   http://mathworld.wolfram.com/ClassNumber.html
where you can see the Kronecker symbol appear.

Conclusions: a formula for the period is hidden in the Fourier transform
of these successive periods; probably a sum over the primes or rather
a sum over all the integers < n (as in the formula above). Except for
the Legendre or Jacobi or Kronecker symbol, all the "stuff" in that formula
should be made from analytical functions as seems to be when looking as
the real values described above.

OK. Then I got tired trying to understand the way it works. Someone?
My C + assembly, to be compiled with GCC on a x86 is available for
anyone who wants it.

Regards,

-- 
Thomas Baruchel