Warning: mysqli::__construct(): (HY000/1203): User howardkn already has more than 'max_user_connections' active connections in D:\Inetpub\vhosts\howardknight.net\al.howardknight.net\includes\artfuncs.php on line 21
Failed to connect to MySQL: (1203) User howardkn already has more than 'max_user_connections' active connectionsPath: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Madhu
Newsgroups: comp.lang.lisp
Subject: Re: The "Strand" puzzle --- ( Continued Fractions using Lisp orPython? )
Date: Sat, 03 Aug 2024 21:19:02 +0530
Organization: Motzarella
Lines: 95
Message-ID:
References:
<6f90c2b4abed28c153dea46de3af408d@www.novabbs.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Sat, 03 Aug 2024 17:49:14 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0b78c09d3bc8bf095c30520414183be9";
logging-data="3702780"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ZfFfGjtqDcsAXvcsfdjixMpGPcB1xmFI="
Cancel-Lock: sha1:ARjaMtD+CEGl9LP5PaqmDZhUNtg=
sha1:KlnGrhEVYniecJ23frM06zRDjg8=
Bytes: 3915
* HenHanna :
Wrote on Thu, 1 Aug 2024 12:47:30 -0700:
> i still don't see how the prob is related to the Continued Fraction.
>
>
>
> if this Continued Fraction is written as [2,1] with a bar over 1 (?)
No it is written as [1:(2)], with the bar over 2 replaced by bracketing
the periodic terms.
It is the same as [1;2,2,2,2,2,]
I had found this page which explains the
sqrt (2) as a continued fraction -- when I posted my parallel answer in
https://projecteuler.net/problem=65
and a clojure solution for it
https://raw.githubusercontent.com/rm-hull/project-euler/master/src/euler065.clj
which explains the convergents for sqrt(2)
; What does [3,1] correspond to?
[3;(1)]
another continued fraction with a list of peridoicity 1 consisting of
(1)
Here is a fucntion to compute the nth convergents of continued fractions
speciefied like this (first repeated-numbers)
(defun nth-convergent (n first repeated &aux (l (length repeated)))
(+ first (if (= n 0)
0
(let (den)
(loop for i downfrom n to 1
for k = (- i 1)
for e = (elt repeated (mod k l))
do (setq den (if den (+ e (/ den)) e)))
(if den (/ den) 0)))))
(nth-convergent 0 3 '(1))
(loop for i below 10 collect (nth-convergent i 3 '(1)))
=> (3 4 7/2 11/3 18/5 29/8 47/13 76/21 123/34 199/55)
=> (3.0 4.0 3.5 3.6666667 3.6 3.625 3.6153846 3.6190476 3.6176472 3.6181817)
which seems to converge to 3.618034,
punching the numerators into
https://oeis.org/
brings up this page https://oeis.org/A000032 for "Lucas Numbers
beginning with 2"
I see I can generalize the n-convergent above function to solve
project-euler-65 by letting it accept a "generator" function, (not your
usual generator more of an accessor which does table lookup)
(defun nth-convergent-acc (n acc)
"Produce the nth convergent of a continued fraction specified by
the nth-accessor ACC function."
(let (den)
(loop for i downfrom n to 1
for e = (funcall acc i)
do (setq den (if (not den) e (+ e (/ den)))))
(+ (funcall acc 0) (if den (/ den) 0))))
(defun sqrt2-acc (n) ;;[1;(2)]
(if (= n 0) 1 2))
(loop for i below 10 collect (nth-convergent-acc i #'sqrt2-acc))
;; => (1 3/2 7/5 17/12 41/29 99/70 239/169 577/408 1393/985 3363/2378)
(defun nth-acc-e (n) ;;[2;1,2,1,1,4,1,1,6,1,...] repeating (1,2k,1) A0034157
(if (= n 0)
2
(multiple-value-bind (div rem)
(truncate (1- n) 3)
(ecase rem
(0 1)
(1 (* 2 (1+ div)))
(2 1)))))
(defun nth-convergent-e (n)
(nth-convergent-acc n #'nth-acc-e))
(loop for i below 10 collect (nth-convergent-e i))
;; => (2 3 8/3 11/4 19/7 87/32 106/39 193/71 1264/465 1457/536)