#lang racket

(require math/number-theory)

#|

This is a program to approximate pi using the fact that two "randomly" chosen
integers are coprime with probability 6 / pi^2.

|#

;; Pick an integer n such that 2 <= n < oo.
(define input (list
                1001
                6024
                73
                6
                13
                83
                21
                2221
                14
                10000
                256
                108
                15
                12
                7
                35
                314
                2
                3145
                205
                7
                42
))

#|

Things to note:
- tail recursive
- uses filter
- probably could be more efficient (length called on filter job)

|#
(define (compute-pi lst)
  (letrec ([len (length lst)]
           [pairs (/ (* len (- len 1)) 2)]
           [relatively-prime-pairs
             (lambda (lst orig-lst acc)
               (if (null? lst)
                 (/ acc 2) ; base case: remove duplicates
                 (relatively-prime-pairs ; recursive case
                   (cdr lst)
                   orig-lst
                   (+ acc (length
                            (filter (lambda (x) (coprime? (car lst) x))
                                    orig-lst))))))])
    (sqrt (/ (* 6 pairs) (relatively-prime-pairs lst lst 0)))))

(displayln (compute-pi input))