Problems & Puzzles: Puzzles

Puzzle 535. The minimal seed Xo/Yo for square roots Luis Rodríguez sent the following puzzle. There is an algorithm for finding square roots of integers in the form of fractions X / Y : X(n+1) = 2 * Xn ^2 - 1 ; Y(n+1) = 2 * Xn * Yn But how to know the minimum seed Xo / Yo needed for the convergence to the square root of a given prime number?. (Minimum = smaller numerator X) By example sqrt(37) must begin with Xo / Yo = 73 / 12 X1 / Y1 = 10657 / 1752 X2 / Y2 = 227143297 / 37342128 I accepted the error of the third convergent < 10^(-12), then I found the following list of minimum seeds for the square roots of primes < 100.   Prime Xo / Yo 2 3/2 3 2/1 5 9/4 11 10/3 7 8/3 13 649/180 17 33/8 19 170/39 23 24/5 29 9801/1820 31 1520/273 37 73/12 41 2049/320 43 ? 47 48/7 53 ? 59 530/69 61 ? 67 ? 71 3480/413 73 ? 79 80/9 83 82/9 89 ? 97 ? Question 1.- Can someone complete the list ? Question 2.- The fractions given above are those with the smaller numerators? Question 3.- It is possible to determine by an analytic procedure the fraction Xo/Yo given the prime?

---

Contributions came from Jan van Delden, Jean Brette, Seiji Tomita, Antoine Verroken & Giovanni Resta.

All of them found the solutions asked in Q1.

43, 3482, 531
53, 66249,9100
61, 6285951340, 807200313
67, 48842, 5967
73, 21238249, 2403000
89, 500001, 53000
97, 282452773, 29364956

(... in http://mathworld.wolfram.com/PellEquation.htlm found a list of the solutions from N = 2 to N = 102)

 All of them confirmed the Rodriguez solutions asked in Q2. And all of them found the solution to Q3 in the Pell equation. I will show only the particular solutions to Q3.

***

Jan wrote:

The key idea is to match the proposed algorithm to Newton Raphson procedure on z^2=p, with z=x/y:

x[n+1]/y[n+1]=1/2.(x[n]/y[n]+p.y[n]/x[n]) which can be split (one method is):
x[n+1]=x[n]^2+p.y[n]^2 and y[n+1]=2.x[n].y[n].

Since Newton Raphson always converges (the graph of z^2-p has only one absolute minimum), the idea is to find x[0],y[0] such that the two match.
This leaves the well known Pell equation: x[0]^2-p.y[0]^2=1.

One merely has to find the smallest y[0] (and therefore smallest x[0]), but one shouldn't use a loop on y[0], but use the solution method described below.

It's solutions can be found by expand sqrt( p) as a simple finite continued fraction:
[a0,a[1],a[2],...,a[r],2a[0]] (a[1],..2a[0] is being repeated. With all 0<a[i]<2.sqrt(p ), since p is not a square.

We have a[0]=trunc(sqrt(p )) and a[i]=trunc(1/(sqrt(p )-a[i-1])).

We then write: p[0]=a[0]; p[1]=1+a[0].a[1]; q[0]=1; q[1]=a[1], and use p[n]=p[n-1]a[n]+p[n-2], q[n]=q[n-1]a[n]+q[n-2].

The fundamental (smallest) solution is then p[r],q[r] if r is odd p[2r+1], q[2r+1] if r is even.

***

Jean wrote:

This puzzle is closely related to the solutions of the Pell equation :

X^2 – p* Y^2 =1 (E)

It is easy to verify that

if (X0, Y0) is a solution of this equation, then (X1,Y1) is also a solution

where X1 = 2*X0^2 – 1 and Y1=2*X0 *Y0


So, Luis Rodriquez is looking for the smallest solution of the equation (E) for a given prime p.

These solutions can be computed with the help of the development of Sqrt(p)
in continued fraction and the parity of the length of his period.

Note : The algorithm used to compute (Xn, Yn), … starting with (X0,Y0) gives only some of the solutions of ( E ).

Example p = 2, the solutions given by the algorithm are successively

(3,2) ; (17,12) ; (577,408) ; (665857, 470832) ….

but the whole solutions begin with

(3,2) ; (17,12) ; (99,70) ; (577,408) ; (3363, 2378) ; (19601,13860) ; (114243, 80782) ; (665857, 470832) …..

and explain why the algorithm is so good to compute Sqrt(p)

About the method I used, with continued farctions and parity of the period, you find explanations and examples (in french) on :

http://fr.wikipedia.org/wiki/Équation_de_Pell-Fermat

...

If one want to use only the algorithm given by Luis Rodriguez, then the seeds were given by LR and me. (and probably many others)

But with a small change, one can find a pre – seed in some cases.


a) If (Xo, Yo) is a solution of Xo^2 – p* Yo^2 = 1 then

X(n+1) = 2*X(n)^2 – 1 ; Y(n+1)=2*X(n)*Y(n) (algorithm L.R.)



b) If (Xo, Yo) is a solution of Xo^2 – p* Yo^2 = -1 then (Xo, Yo) is a pre-seed and (X1,Y1) is a seed,

where X(1) = 2*Xo^2 +1 , Y(1)=2*Xo*Yo

After, one uses the algorithm L.R. to get (X(2), Y(2)) ;…. (Xn, Yn).


This is the case for P = 13 , 41, 53, 61, 73, 89, 97, 109

Pre-seeds :

P = 13 Xo = 18 Yo = 5

P = 41 Xo = 32 Yo = 5

P = 53 Xo = 182 Yo = 25

P = 61 Xo = 29718 Yo = 3805

P = 73 Xo = 1068 Yo = 125

P = 89 Xo = 500 Yo = 53

P = 97 Xo = 5604 Yo = 569

P = 109 Xo= 8890182 Yo = 851525

All the best 

***

Antoine wrote:

1. Dirichlet proved the fact that if x0,y0 is the least solution of x^2 – A * y^2 = 1,

all positive solutions are given by  xn + yn*sqrt(A) = ( x0 + y0*sqrt(A) )^n      n=1,2,3…

f.i.   x(n+1) + y(n+1)*sqrt(A) = ( xn + yn*sqrt(A) )^2= ( xn^2 + yn^2 *A ) + 2*xn*yn*sqrt(A)

Because  x^2 – y^2 * A = 1  à  x(n+1) = 2*xn^2 – 1, y(n+1) = 2*xn*yn

***

Giovanni wrote:

it can probably be shown (not by me, at least for the moment)
that the smallest pair which starts a sequence converging to sqrt(p) is given by the smallest solution of the Pell equation x^2-p*y^2=1.

***