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

On 8/3/2024 8:49 AM, Madhu wrote:

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

thanks...   (i meant to ask...)
 >> if this Continued-Fraction is written as [2,1] with a bar over 1 (?)
the  Continued-Fraction  for  Sqrt(2)  gives us the  "Strand" puzzle---
Do the  other  simple  Continued-Fractions  give us
                                          other similar problems ???