Path: ...!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: Thu, 01 Aug 2024 23:41:47 +0530
Organization: Motzarella
Lines: 153
Message-ID: <m3o76cru3g.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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 01 Aug 2024 20:11:58 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="279c53cc96f6474a1c520e3f53e85bee";
	logging-data="2417945"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+4qntwQkmVgdAEO2UWrIGWa0VRYi4Q2Yw="
Cancel-Lock: sha1:bc3o+KcBv/jPC1FSljUrSLgfmXI=
	sha1:zpovIaHHlVG+FG6+OKUUk3bnM74=
Bytes: 5876

* W J  <v8fkps$23nr5$1@dont-email.me> :
Wrote on Thu, 1 Aug 2024 09:33:53 -0000 (UTC):

> HenHanna wrote:
>> > > e.g. -------- For the (street)? Numbers (1,2,3,4,5,6,7,8)
>> > >
>> > > ?????? (1,2,3,4,5)? and? (7,8)? both add up to 15.
>> > >
>> > >
>> > >
>> > > "In a given street of houses with consecutive numbers between
>> > > 50 and 500, find the house number, for which, the sum of
>> > > numbers on the left is equal to the sum of numbers on the
>> > > right"

No, You did not comprehend the problem correctly.  The house numbers
(one ons side of the street) start from 1. there were at least 50 houses
and not more than 500 houses in that row. see below:

From the portion which WJ snipped out:

* In <6f90c2b4abed28c153dea46de3af408d@www.novabbs.com>
On 7/26/2024 5:37 AM, IlanMayer wrote:
> Solution found at:
> https://ubpdqnmathematica.wordpress.com/2021/12/05/ramanujan-and-strand-puzzle/


```
tesseract <(ls
ubpdqnmathematica.wordpress.com/wp-content/uploads/2021/12/puzzle.jpg)
- --dpi 150 txt
```


```
"I was talking the other day," said William Rogers
to the other villagers gathered round the inn fire,
"to a gentleman about that place called Louvain, what
the Germans have burnt down. He said he knowed it
well—used to visit a Belgian friend there. He said the
house of his friend was in a long street, numbered on
his side one, two, three, and so on, and that all the
numbers on one side of him added up exactly the same
as all the numbers on the other side of him. Funny
thing that! He said he knew there was more than
fifty houses on that side of the street, but not so many
as five hundred. I made mention of the matter to our
[parson]
and he took a pencil and worked out the number
Belgian lived. I don't know
[how he done it."]

Perhaps the reader may like to discover the number
‘of that house
```

English (ESL) Usage:  Is "he knowed it" French?

> Gauche Scheme (define (strand lst) (let go ((left-sum 0) (tail lst))
> (if (null? tail) #f (let ((right-sum (fold + 0 (cdr tail)))) (cond ((<
> left-sum right-sum) (go (+ left-sum (car tail)) (cdr tail))) ((=
> left-sum right-sum) (car tail)) (#t #f))))))

> (strand '(1 2 3 4 5 6 7 8)) ===> 6
> (lrange 2 5) ===> (2 3 4)
> (any (lambda (n) (if (strand (lrange 50 n)) n #f)) (lrange 500 50 -1))
> ===> 352
> (strand (lrange 50 352)) ===> 251


No to answer the question you need to do (strand (lrange 1 500))

I'll go back to understand the mathematica solution a little later,
but in lisp using JMsiskind's screamer constraint solver

(require 'screamer)

(defun sum (a b)
  "(loop for i from a to b sum i)"
  (/ (- (+ (* b b) b) (- (* a a)  a)) 2))


(defun balance (a b &key (constrain-left t) (constrain-right nil))
  (screamer:all-values
    (let* ((n (screamer:an-integer-between a b))
	   (l (if constrain-left a (screamer:an-integer-between a (1- n))))
	   (r (if constrain-right b (screamer:an-integer-between (1+ n) b))))
      (screamer:assert! (= (sum l (1- n)) (sum (1+ n) r)))
      (screamer:solution
       (list l n r)
       (screamer:static-ordering #'screamer:linear-force)))))

  ;; a list of (1st-house-number solution-house-number
  ;; last-house-number)

(balance 1 500)
;; => ((1 6 8) (1 35 49) (1 204 288))

This matches the numbers in the ubpdqnmathematica generated table.


The solution from ubpdqnmathematica equates:

(sum (- n l) (- l 1)) == (sum (+ l 1) r)

l = 1
r = number of houses
n = position of the required house

and expanding and substituting x = 2n + 1, y = 2r

eventually reduces that to the solutions of x^2 - 2y^ = 1 (a "Pell
equation"), for which apparently the solutions are to be found in the
convergents (num/den) of sqrt(2), I'm not sure how.

num = 2 * r + 1
den = 2 * n

;; sqrt(2) = 1 +    1
;;              ============== 
;;              2 +   1
;;                 =========== 
;;                 2 +  1
;;                    ========
;;                    2 +  1
;;                       ======
;;                       2 + ...


(defun nth-convergent-of-sqrt-2 (n)
  (assert (>= n 0))
  (let ((den 2))
    (loop repeat n do (setq den (+ 2 (/ 1 den))))
    (+ 1 (/ 1 den))))

(setq $a (loop for i below 10 collect (nth-convergent-of-sqrt-2 i)))

(loop for a in $a
      when (let ((num (numerator a))
		 (den (denominator a)))
	     (when (= 1 (- (* num num) (* 2 den den)))
	       (list 1 ;house #1
		     (/ den 2); the house# in the middle
		     (/ (- num 1) 2); the last house no.
		     )))
      collect it)

=> ((1 1 1) (1 8 6) (1 49 35) (1 288 204) (1 1681 1189))

Which reproduces the result but I've forgotten the maths behind the
continued fractions which I'm sure I was taught in either highschool or
1st year of college.