Euler Project 53

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ⁵C₃ = 10.

In general,

nCr =

n! r!(nr)!

,where r n, n! = n(n1)...321, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of ⁿC_r, for 1 n 100, are greater than one-million?

My Solution

(defun factorial(n)

(factorial-iter n 1))

(defun factorial-iter(n result)

(if (> n 0)

(factorial-iter (- n 1) (* n result))

result))

(defun Euler53(n)

(let ((a 0))

(loop for i from 2 to n

do(loop for j from 1 to (- i 1)

do(if (> (/ (/ (factorial i) (factorial j))

(factorial (- i j)))

1000000)

(incf a))))

a))

Others' Solution

First Solution

(setq fact-memo (make-hash-table))

(defun factorial (n)
(if (= n 0)
1
(let ((try (gethash n fact-memo)))
(if try
try
(setf (gethash n fact-memo) (* n (factorial (- n 1))))))))

(defun choose (n r)
(/ (factorial n) (factorial r) (factorial (- n r))))

(defun choose-count (lim min)
(loop for n from 1 to lim
sum (loop for r from 0 to n
if (> (choose n r) min)
count r)))

(defun euler53 ()
(choose-count 100 1000000))

Second Solution

(defun euler53 (&optional

(limit 1000000) (lo 23) (hi 100))
(let ((total 0))

(do ((n lo (1+ n))) ((> n hi) total)

(do ((r 1 (1+ r))) ((or () (> r n)))

(when (> (combinatorial n r) limit)

(incf total))))))

(defun combinatorial (n r)

(/ (factorial n) (* (factorial r) (factorial (- n r)))))

(defun factorial (n)

(let ((fact 1))

(do ((i 2 (1+ i)))

((> i n) fact)
(setq fact (* i fact)))))

Third Solution

(let ((memos (make-hash-table)))

(setf (gethash 0 memos) 1)

(setf (gethash 1 memos) 1)

(defun factorial (n)

(or (gethash n memos)
(setf (gethash n memos) (* n (factorial (1- n)))))))

(loop for n from 1 to 100

sum (loop for r from 1 to n

for c = (/ (factorial n)
(* (factorial r)
(factorial (- n r))))

when (< 1000000 c) sum 1))

Forth Solution

(defun euler053 ()
(iterate loop ((n 23) (big-uns 0) (this-row 0) (r 11))
(cond ((> n 100)
big-uns)
((minusp r)
(if (evenp n)
(loop (1+ n) (+ big-uns (1- (* 2 this-row))) 0 (floor (1+ n) 2))
(loop (1+ n) (+ big-uns (* 2 this-row)) 0 (floor (1+ n) 2))))
(:else
(let ((c (choose n r)))
(if (> c 1000000)
(loop n big-uns (1+ this-row) (1- r))
(loop n big-uns this-row (1- r))))))))

(defun choose (n r)
(iterate loop ((nl n) (rl r) (p 1))
(if (plusp rl)
(loop (1- nl) (1- rl) (* p (/ nl rl)))
p)))