Path: ...!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 <enometh@meer.net>
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: <m3v80hr4i9.fsf@leonis4.robolove.meer.net>
References: <v7u7qd$2dgbs$1@dont-email.me>
	<6f90c2b4abed28c153dea46de3af408d@www.novabbs.com>
	<v88ood$jnp6$1@dont-email.me> <v8fkps$23nr5$1@dont-email.me>
	<v8gook$2bqob$1@dont-email.me>
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 <v8gook$2bqob$1@dont-email.me> :
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
<m3o76cru3g.fsf@leonis4.robolove.meer.net>

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)