Re: The "Strand" puzzle --- ( Continued Fractions using Lisp orPython? )

* 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)