# HG changeset patch # User Steve Losh # Date 1488320391 0 # Node ID 5ece176de1742550e72e3bae8ddd3c5fbff45611 # Parent 0fc16405aff4f4321cebd29c7a384b30731c63c1 Problem 53 diff -r 0fc16405aff4 -r 5ece176de174 src/euler.lisp --- a/src/euler.lisp Tue Feb 28 22:12:26 2017 +0000 +++ b/src/euler.lisp Tue Feb 28 22:19:51 2017 +0000 @@ -1575,6 +1575,32 @@ (orderless-equal digits (digits (* n i)))) '(2 3 4 5 6))))) +(defun problem-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, 5C3 = 10. + ;; + ;; In general, + ;; + ;; nCr = n! / r!(n−r)! + ;; + ;; where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1. + ;; + ;; It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066. + ;; + ;; How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are + ;; greater than one-million? + + (iterate + main + (for n :from 1 :to 100) + (iterate + (for r :from 1 :to n) + (for nCr = (binomial-coefficient n r)) + (in main (counting (> nCr 1000000)))))) + (defun problem-56 () ;; A googol (10^100) is a massive number: one followed by one-hundred zeros; @@ -1682,6 +1708,7 @@ (test p50 (is (= 997651 (problem-50)))) (test p51 (is (= 121313 (problem-51)))) (test p52 (is (= 142857 (problem-52)))) +(test p53 (is (= 4075 (problem-53)))) (test p56 (is (= 972 (problem-56)))) (test p74 (is (= 402 (problem-74))))