;; From The Mathematical Intelligencer, vol. 3, number 1, p. 45.
;; 
;; Problem is by J. H. Conway.
;; 
;; Problem 2.4:
;; 
;; A Prime Problem for the Ambidextrous.
;; 
;; 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13,
;; 13/11, 15/14, 15/2, 55/1.
;; 
;; Write down 2 (with your right hand).  Look at these fourteen fractions
;; and use them to generate two sequences of natural numbers by iterating
;; the following:
;; 
;; If r is the last number you wrote with your right hand look for the
;; first of the fourteen fractions which, when multiplied with r, gives
;; you an integer.  Write the integer down (with your right hand).  If
;; this integer is a power of 2, say 2^l, write down l (with your left
;; hand).
;; 
;; 1) What is the left-hand sequence?
;; 2) Why?
;; 
;; There's a third question, but I'm going to put a lot of space between
;; it and the other two, since it gives away the answer to 1).  So if you
;; want a hint, look 50 or so lines after I sign my name.  I wouldn't
;; particularly recommend trying to work out 1) by doing it by hand, but
;; it could be fun to write a computer program to grind through it.



(define test-list
  (list (cons 17 91)
        (cons 78 85)
        (cons 19 51)
        (cons 23 38)
        (cons 29 33)
        (cons 77 29)
        (cons 95 23)
        (cons 77 19)
        (cons  1 17)
        (cons 11 13)
        (cons 13 11)
        (cons 15 14)
        (cons 15  2)
        (cons 55  1)))


(define left-hand '(0))
(define right-hand '(2))


(define power-of?
  (lambda (num expt)
    ;; Return #f if NUM is not a power of EXPT.
    ;; Else return the power.
    (let loop
        ((num num)
         (expt expt)
         (pwr 1))
    (cond
     ((< num expt) #f)
     ((= num expt) pwr)
     (else
      (loop (/ num expt) expt (1+ pwr)))))))
        

(define iterate-once 
  (lambda (ratio-list)
    (let ((current-rh (car right-hand)))
      (let loop
          ((tl test-list))
        (if (null? tl)
            (error "huh?")
            (let* ((numerator   (car (car tl)))
                   (denominator (cdr (car tl)))
                   (result (/ (* current-rh numerator) denominator)))
              (if (integer? result)
                  (let ((pwr (power-of? result 2)))
                    (set! right-hand (cons result right-hand))
                    (if pwr
                        (set! left-hand (cons pwr left-hand))))
                  (loop (cdr tl)))))))))

            
(define next-thing
  (lambda ()
    (let ((last-thing (car left-hand)))
      (let loop
          ((this-thing last-thing))
        (iterate-once test-list)
        (if (= this-thing (car left-hand))
            (loop this-thing)
            (car left-hand))))))