Re: Odd behavior of an iteration

From: Philippe 92 (nospam_at_free.invalid)
Date: 03/23/05 

Date: Wed, 23 Mar 2005 12:04:32 +0100

Hi,

G. A. Edgar wrote :
> In article <1111515349.348048.10720@o13g2000cwo.googlegroups.com>,
> <luiroto@yahoo.com> wrote:
>
>> Dear folks.
>> I was iterating the following process:
>> X(n) = p/q ; X(n+1) = (2*p^2 -1) / 2*p*q
>> That is p(n+1) = 2*p^2-1 ; q(n+1) = 2*p*q
>>
>> If X(o) = 3/2 then Lim X(n) = sqr(2)
>> If X(o) = 7/4 "" "" = sqr(3)
>> if X(o) = 9/4 "" "" = sqr(5)
>> if X(o) = 5/2 "" "" = sqr(6)
>> -------- ------------ ------
>> if X(o) = 15/4 "" "" = sqr(14)
>>
>> Which is the fracction corresponding to sqr(13), sqr(15)?
>> Thanks. Ludovicus
>>
>
> Well, if you start with a/b, the limit is sqrt(a^2-1)/b .
>
> So to get sqrt(13), you could start for example with 649/180 .

And there is no smaller value for p,q !
(fundamental solution of Pell equation a^2 - 13b^2 = 1)

for sqrt(15), a^2 - 15b^2 = 1 has fundamental solution 4/1(obvious)
the next is 31/8 if you need b > 1.

Some horrible values, worse than sqrt(13) :
sqrt(61) ? 1766319049 / 226153980 is the smallest value !

next huge values are for sqrt(109)
158070671986249 / 15140424455100

These values were asked by Fermat to Frenicle in 1657 saying :
"[61 and 109] being not too big numbers so you don't have too much work"
;-)

For general method look for Pell equation and PQa algorithm.

Regards. 

-- 
philippe
(chephip at free dot fr)