## euler## 1.0.0Clojure solutions to the first 33 Project Euler problems. Unit tests are provided to compare the result of each problem's
## dependencies
## dev dependencies
| (this space intentionally left almost blank) | |||||||||||||||

## namespaces- org.drcabana.euler.prequel
- org.drcabana.euler.prob01
- org.drcabana.euler.prob02
- org.drcabana.euler.prob03
- org.drcabana.euler.prob04
- org.drcabana.euler.prob05
- org.drcabana.euler.prob06
- org.drcabana.euler.prob07
- org.drcabana.euler.prob08
- org.drcabana.euler.prob09
- org.drcabana.euler.prob10
- org.drcabana.euler.prob11
- org.drcabana.euler.prob12
- org.drcabana.euler.prob13
- org.drcabana.euler.prob14
- org.drcabana.euler.prob15
- org.drcabana.euler.prob16
- org.drcabana.euler.prob17
- org.drcabana.euler.prob18
- org.drcabana.euler.prob19
- org.drcabana.euler.prob20
- org.drcabana.euler.prob21
- org.drcabana.euler.prob22
- org.drcabana.euler.prob23
- org.drcabana.euler.prob24
- org.drcabana.euler.prob25
- org.drcabana.euler.prob26
- org.drcabana.euler.prob27
- org.drcabana.euler.prob28
- org.drcabana.euler.prob29
- org.drcabana.euler.prob30
- org.drcabana.euler.prob31
- org.drcabana.euler.prob32
- org.drcabana.euler.prob33
| ||||||||||||||||

Before launching into the problems, let's take a quick tour of some useful syntax. | (ns org.drcabana.euler.prequel) | |||||||||||||||

Defining a function is the natural unit of work in functional programming. Clojure offers multiple ways to define functions, so let's look at some examples. This treatment is not exhaustive, it just covers some common cases. | ||||||||||||||||

The classic function of one argument. | (defn square [x] (* x x)) | |||||||||||||||

| ||||||||||||||||

A two argument function. | (defn sum-of-cubes [x y] (+ (* x x x) (* y y y) )) | |||||||||||||||

| ||||||||||||||||

A single required argument, with a variable number of optional
arguments. The | (defn sum-of-squares [x & more-args] (+ (square x) (apply + (map square more-args)))) | |||||||||||||||

| ||||||||||||||||

There are a couple of ways two define anonymous functions. The
first is to use
| ||||||||||||||||

An even terser way to define square is to use the #() form. Here % denotes the single argument to the function .
| ||||||||||||||||

The #() form allows for multiple arguments by numbering them. Here we define a function which divides its first arg by its second, and apply it.
| ||||||||||||||||

You can create functions of multiple arity, defined on a case per case basis. | (defn foo ([] "one meeellion") ([x] (* 2 x)) ([x y] (+ x y)) ([x y z] (max x y z))) | |||||||||||||||

| ||||||||||||||||

Various Clojure data structures can be used both as data structures and as functions. For instance, sets can be used as functions. Let's define a set. | (def digits #{0 1 2 3 4 5 6 7 8 9}) | |||||||||||||||

A slick way way to use a set is to test for membership in the set itself. The way it works is that (digits x) returns x when x is an element of digits, and returns nil otherwise.
| ||||||||||||||||

This becomes problematic if nil is an element of the set in question. When that is not an issue, this way of testing membership can be quite handy. See the solution to problem 24 for an example. | ||||||||||||||||

For more (somewhat densely packed) information, check out the official documentation for Clojure's special forms and for the Clojure reader. | ||||||||||||||||

Clojure is fortunate to have several very good books. To my taste, the best introductory book is Programming Clojure. The Joy of Clojure is a must read, but perhaps not the best place to start for readers who don't already have some lisp in their veins. | ||||||||||||||||

Problem 1 is to sum the positive integers less than 1000 which are divisible by either 3 or 5. The original problem statement is available here. | (ns org.drcabana.euler.prob01) | |||||||||||||||

The | (defn qualifies? [x] {:pre (integer? x)} (or (zero? (rem x 5)) (zero? (rem x 3)))) | |||||||||||||||

The solution illustrates recurring patterns worth watching for in subsequent problems. | ||||||||||||||||

- We begin by generating a sequence of data.
- We then use
*filter*and a predicate to extract a desired subsequence. - We wrap up by using
*reduce*and a selected function to compute a value from the subsequence.
| (defn solution [] (reduce + (filter qualifies? (range 1000)))) | |||||||||||||||

Notes: | ||||||||||||||||

Predicates are functions that return | ||||||||||||||||

Notice that Clojure has some design-by-contract fu. We used a
precondition in the definition of the | ||||||||||||||||

Problem 2 is to sum the even Fibonacci numbers not exceeding four million. The original problem statement is available here. | (ns org.drcabana.euler.prob02) | |||||||||||||||

| (defn fibonacci [] (letfn [(fib [[a b]] [b (+' a b)])] (->> [0 1] (iterate fib) (map first)))) | |||||||||||||||

The pattern is pretty much the same as in the previous problem. We generate a sequence, filter it with a predicate, and reduce the result to a single number. | (defn solution [] (->> (fibonacci) ;; generate an infinite lazy sequence (take-while #(< % 4000001)) ;; realize the subseq of interest (filter even?) ;; filter out evens, then reduce (reduce +))) | |||||||||||||||

Notes: | ||||||||||||||||

The overall pattern of the solution is the same as in problem 1, but the code looks a bit different, due to the use of the ->> macro. I like ->> because it allows code to be read from top to bottom. By way of comparision, I could have written the code this way. | (defn solution-alternative [] (reduce + (filter even? (take-while #(< % 4000001) (fibonacci))))) | |||||||||||||||

Problem 3 is to find the largest prime divisor of 600851475143. The original problem statement is available here. | (ns org.drcabana.euler.prob03 (:use [clojure.math.numeric-tower :only (sqrt)])) | |||||||||||||||

Return the least divisor of n in the closed interval [k ... n]. | (defn least-divisor [k n] {:pre [(integer? k) (integer? n) (<= 2 k n)]} (let [limit (inc (int (sqrt n))) candidates (drop-while #(pos? (rem n %)) (range k limit)) ] (if (seq candidates) (first candidates) n))) | |||||||||||||||

Return the prime factorization of n, as a vector of primes. By construction the factors will be in non-decreasing order. For example,
| (defn prime-factors [n] {:pre [(integer? n) (< 0 n)]} (loop [n n factors [] k 2] (if (= 1 n) factors (let [d (least-divisor k n)] (recur (quot n d) (conj factors d) d))))) | |||||||||||||||

(defn solution [] (reduce max (prime-factors 600851475143))) | ||||||||||||||||

Problem 4 is to find the largest palindrome made from the product of two 3-digit numbers. The original problem statement is available here. | (ns org.drcabana.euler.prob04) | |||||||||||||||

Is | (defn palindrome? [word] (let [chars (seq (str word))] (= chars (reverse chars)))) | |||||||||||||||

There are only 900 3-digit numbers, so brute force suffices. It suffices to consider only the cases where a <= b because multiplication is commutative. | (defn solution [] (let [products (for [a (range 100 1000) b (range 100 1000) :when (<= a b)] (* a b))] (reduce max (filter palindrome? products)))) | |||||||||||||||

Notice that once again we constructed a sequence, filtered it, then reduced it. | ||||||||||||||||

Problem 5 is to find the least common multiple of the integers {1,2,...,20}. The original problem statement is available here. The LCM function is well known to be associative: LCM(LCM(a,b),c) = LCM(a, LCM(b,c)). That means the Clojure solution to our problem is immediate: (reduce LCM (range 1 21)). We just need to construct an LCM function. A simple way is to use the greatest common divisor function, GCD. It can be proven that LCM(a b) * GCD(a b) = a * b so we can use GCD to implement LCM. Naturally, we use Euclid's algorithm to implement GCD. | (ns org.drcabana.euler.prob05) | |||||||||||||||

| (defn gcd [a b] {:pre [(integer? a) (integer? b) (pos? a) (pos? b)]} (cond (= a b) a (> a b) (recur (- a b) b) :else (recur (- b a) a))) | |||||||||||||||

| (defn lcm [a b] (/ (* a b) (gcd a b))) | |||||||||||||||

(defn solution [] (reduce lcm (range 1 21))) | ||||||||||||||||

Each of the first five solutions in this problem set has used | ||||||||||||||||

Docs: cond | ||||||||||||||||

Problem 6 is to find the difference between the square of the sum of 1 ... 100 and the sum of the squares of 1 ... 100. The original problem statement is available here. | (ns org.drcabana.euler.prob06) | |||||||||||||||

(defn solution [] (let [square #(* % %) values (range 1 101) square-of-sum (square (reduce + values)) sum-of-squares (reduce + (map square values))] (- square-of-sum sum-of-squares))) | ||||||||||||||||

Problem 7 is to find the 10001-th prime number. The orginal problem statement is available here. | (ns org.drcabana.euler.prob07 (:use [org.drcabana.euler.prob03 :only (least-divisor)])) | |||||||||||||||

We already have a useful bit of number theoretic code from problem 3. We reuse it via the :use statement in the namespace declaration. | ||||||||||||||||

Return the least positive integer greater than 1 which divides n. | (defn least-nontrivial-divisor [n] {:pre [(integer? n) (<= 2 n)]} (least-divisor 2 n)) | |||||||||||||||

Primes are easily defined in
terms of the | (defn prime? [n] {:pre [integer? n]} (if (< n 2) false (== n (least-nontrivial-divisor n)))) | |||||||||||||||

Return the sequence of primes. We test only odd numbers for primality. | (defn primes [] (let [odd-numbers (iterate #(+ 2 %) 3)] (cons 2 (filter prime? odd-numbers)))) | |||||||||||||||

Clojure uses 0-based indexing, but the problem statement uses 1-based indexing, so we have to decrement the index. | (defn solution [] (nth (primes) 10000)) | |||||||||||||||

In problem 8 we are given a string of numeric digits, and asked to find the maximal product of five consecutive digits. The original problem statement is available here. | (ns org.drcabana.euler.prob08) | |||||||||||||||

We will need a way to convert a numeric character into an integer. Notice the idiom used in the precondition: membership in a set is tested by using the set as a function. | (defn char-to-int [char] {:pre [(#{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} char)]} (Integer/parseInt (str char))) | |||||||||||||||

(defn solution [] (let [product (partial reduce *) digits "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"] (->> (map char-to-int digits) (partition 5 1) (map product) (reduce max)))) | ||||||||||||||||

Picasso is alleged to have remarked that "good artists borrow, great artists steal".
The extremely useful | ||||||||||||||||

I quietly used Java, in the call to Integer/parseInt. Java interop in Clojure can be so seamless you may not notice it. | ||||||||||||||||

Problem 9 is to find the Pythagorean triple that sums to 1000, and form the product of its members. That is, return the product of postive integers a,b,c such that a + b + c = 1000 a The original problem statement is available here. | (ns org.drcabana.euler.prob09) | |||||||||||||||

(defn pythagorean? [a b c] (= (* c c) (+ (* a a) (* b b)))) | ||||||||||||||||

We choose c = 1000 - a - b, thus meeting the sum constraint. The :when condition ensures that the Pythagorean constraint is met. | (defn solution [] (let [triples (for [a (range 1 1000) b (range a 1000) c [(- 1000 a b)] :when (pythagorean? a b c)] [a b c])] (reduce * (first triples)))) | |||||||||||||||

Docs: for | ||||||||||||||||

Problem 10 is to find the sum of all the primes less than two million. The original problem statement is available here. | (ns org.drcabana.euler.prob10 (:use [org.drcabana.euler.prob07 :only (primes)])) | |||||||||||||||

The machinery for generating primes is in place from problem 7. The only thing new here is the final reduction step. | (defn solution [] (reduce + (take-while #(< % 2000000) (primes)))) | |||||||||||||||

Problem 11 is to find the maximal product of four consecutive numbers in a 20x20 square grid of numbers. Consecutive here means contiguous in a row, column, or diagonal. The original description is available here. | (ns org.drcabana.euler.prob11 (:use [clojure.math.numeric-tower :only (sqrt)])) | |||||||||||||||

Here are the numbers, or rather a string we'll later convert to a sequence of numbers. | (def digits "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48") | |||||||||||||||

We want to work with a two-dimensional grid, so we define a constructor that turns a sequence (of suitable length) into square matrix. The matrix will be represented as an anonymous function of variable arity. | ||||||||||||||||

The matrix function returns a lookup function. Given two integer indices, the latter performs the expected lookup. Conveniently, the lookup function will return 1 if either index is out of bounds. Given no args, the lookup function will return the row length of the matrix. | (defn matrix [xs] (let [row-length (int (sqrt (count xs)))] (assert (= (count xs) (* row-length row-length))) (letfn [(valid? [j k] (and (integer? j) (integer? k) (< -1 j row-length) (< -1 k row-length))) (idx [j k] (+ j (* row-length k)))] (fn ([] row-length) ([[j k]] (if (valid? j k) (nth xs (idx j k)) 1)))))) | |||||||||||||||

Compute the sequence of the indices of elements contiguous to | (defn contiguous [origin direction] (iterate #(map + direction %) origin)) | |||||||||||||||

Determine the largest contiguous length-four product in matrix M. | (defn score ([M] (reduce max (for [j (range (M)) k (range (M))] (score M [j k])))) ([M [j k]] (let [directions [ [0 1] [0 -1] [1 0] [-1 0] [1 1] [1 -1] [-1 1] [-1 -1] ]] (reduce max (map #(score M [j k] %) directions)))) ([M [j k] dir] (let [segment (take 4 (contiguous [j k] dir))] (reduce * (map M segment))))) | |||||||||||||||

(defn solution [] (let [numbers (->> digits (re-seq #"\d+") (map #(Integer. %)))] (score (matrix numbers)))) | ||||||||||||||||

This was largely an exercise in using closures. I have the nagging feeling I could have done something simpler. But closure-object duality is cool. | ||||||||||||||||

Problem 12 is to find the first triangle number to have over five hundred divisors. Divisors are assumed to be positive. The original problem statement is available here. We break this problem into two parts: how to compute triangle numbers, and how to count the divisors of integer. | (ns org.drcabana.euler.prob12 (:use [org.drcabana.euler.prob03 :only (prime-factors)])) | |||||||||||||||

The nth triangle number is the (inclusive) sum of the integers from 1 to n. The formula is well known, but worth explaining. Write the sum twice, but the second time write it in reverse order.
Summing the n columns, each totals n+1. So twice the sum of 1...n is equal to n(n+1). | (defn tri [n] (/ (* n (inc n)) 2)) | |||||||||||||||

How many divisors does n have? Any divisor of n is the product of one or more prime factors of n. How many distinct such products are possible? | ||||||||||||||||

The simplest way to think about it is to from a
product p | (defn count-divisors [n] (->> (prime-factors n) (partition-by identity) (map count) (map inc) (reduce *))) | |||||||||||||||

The pieces are in place, the only thing left is to put them together. | (defn solution [] (->> (iterate inc 1) (map tri) (drop-while #(< (count-divisors %) 500)) first)) | |||||||||||||||

We determined the number of divisors of | ||||||||||||||||

Problem 13 is to find the first ten digits of the sum of 100 50-digit numbers. Here are the 50-digit numbers, or rather, a string containing them, one per line. The original problem statement is available here | (ns org.drcabana.euler.prob13) | |||||||||||||||

(def num-str "37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 53282654108756828443191190634694037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 34829543829199918180278916522431027392251122869539 40957953066405232632538044100059654939159879593635 29746152185502371307642255121183693803580388584903 41698116222072977186158236678424689157993532961922 62467957194401269043877107275048102390895523597457 23189706772547915061505504953922979530901129967519 86188088225875314529584099251203829009407770775672 11306739708304724483816533873502340845647058077308 82959174767140363198008187129011875491310547126581 97623331044818386269515456334926366572897563400500 42846280183517070527831839425882145521227251250327 55121603546981200581762165212827652751691296897789 32238195734329339946437501907836945765883352399886 75506164965184775180738168837861091527357929701337 62177842752192623401942399639168044983993173312731 32924185707147349566916674687634660915035914677504 99518671430235219628894890102423325116913619626622 73267460800591547471830798392868535206946944540724 76841822524674417161514036427982273348055556214818 97142617910342598647204516893989422179826088076852 87783646182799346313767754307809363333018982642090 10848802521674670883215120185883543223812876952786 71329612474782464538636993009049310363619763878039 62184073572399794223406235393808339651327408011116 66627891981488087797941876876144230030984490851411 60661826293682836764744779239180335110989069790714 85786944089552990653640447425576083659976645795096 66024396409905389607120198219976047599490197230297 64913982680032973156037120041377903785566085089252 16730939319872750275468906903707539413042652315011 94809377245048795150954100921645863754710598436791 78639167021187492431995700641917969777599028300699 15368713711936614952811305876380278410754449733078 40789923115535562561142322423255033685442488917353 44889911501440648020369068063960672322193204149535 41503128880339536053299340368006977710650566631954 81234880673210146739058568557934581403627822703280 82616570773948327592232845941706525094512325230608 22918802058777319719839450180888072429661980811197 77158542502016545090413245809786882778948721859617 72107838435069186155435662884062257473692284509516 20849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690") | ||||||||||||||||

(defn solution [] (->> (re-seq #"\d+" num-str) ;; split the string (map #(bigint %)) ;; convert substrings to integers (reduce +) ;; sum the integers (str) ;; convert the sum to a string (take 10) ;; take the first ten digits (apply str) ;; concat the digits into a string ;; turn final string back into integer (bigint))) | ||||||||||||||||

Problem 14 is to find the positive integer less than one million with the largest Collatz length. The original problem statement is available here. | (ns org.drcabana.euler.prob14) | |||||||||||||||

First let's define the Collatz function: | (defn collatz [n] {:pre [(pos? n) (integer? n)]} (if (even? n) (/ n 2) (+ (* 3 n) 1))) | |||||||||||||||

For any positive integer n, we can form the corresponding Collatz sequence. | (defn C [n] (iterate collatz n)) | |||||||||||||||

It is conjectured that for any positive N, C(N) is eventually 1. According to the Wikipedia, the conjecture has been tested out to N = 20 * 2^58. | ||||||||||||||||

Define the Collatz-length of N to be the number of terms in
C(N) before the first 1. The use of | (def collatz-length (memoize (fn [n] (count (take-while #(< 1 %) (C n)))))) | |||||||||||||||

The question is what value of N less than one million has the largest collatz-length. | (defn solution [] (->> (range 1 1000000) (map #(vector % (collatz-length %))) (sort-by second) (last) ;; grab last pair, then 1st element of that pair (first))) | |||||||||||||||

In problem 15 we consider a 20 by 20 rectangular grid. Starting at the top left corner, on any move we can move down or right. The question is how many distinct paths to the bottom right there are. The original problem statement is available here. There's not much to this one. To get to the bottom right we must make 40 moves: 20 downwards, and 20 to the right. Imagine we have 40 slots numbered 1 to 40. Once you have assigned the 20 downward moves to their slots, there is no choice about where to put the rightward moves. So the question is how many ways can you choose 20 slots from 40. The answer is well known: the number of ways to choose K elements from N is C(N, K) = N!/(K! * (N-K)!) In particular C(40,20) = 40!/(20! * 20!). A bit of cancellation simplifies the expression. In Clojure versions 1.3 and above, multiplication can overflow, though not silently. We avoid the overflow by using the *' operator. | (ns org.drcabana.euler.prob15) | |||||||||||||||

(defn solution [] (/ (reduce *' (range 21 41)) (reduce *' (range 1 21)))) | ||||||||||||||||

Problem 16 is to sum the decimal digits of 2 | (ns org.drcabana.euler.prob16 (:use [clojure.math.numeric-tower :only (expt)])) | |||||||||||||||

Compute the sequence of digits in the base 10 representation of n. | (defn digits [n] {:pre [(integer? n)]} (letfn [(char-to-int [c] (Integer. (str c))) ] (map char-to-int (str n)))) | |||||||||||||||

(defn solution [] (reduce + (digits (expt 2 1000)))) | ||||||||||||||||

Docs: Integer | ||||||||||||||||

Problem 17 is as follows. If the numbers 1 to 5 are written out in words (one, two, three, four, five) then there are 3 + 3 + 5 + 4 + 4 = 19 letters used. If all the numbers from 1 to 1000 were written out in words, how many letters would be used? Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The original problem statement is available here. | (ns org.drcabana.euler.prob17) | |||||||||||||||

Without much ado, here's a solution. | (def word-for {1 "one" 2 "two" 3 "three" 4 "four" 5 "five" 6 "six" 7 "seven" 8 "eight" 9 "nine" 10 "ten" 11 "eleven" 12 "twelve" 13 "thirteen" 14 "fourteen" 15 "fifteen" 16 "sixteen" 17 "seventeen" 18 "eighteen" 19 "nineteen" 20 "twenty" 30 "thirty" 40 "forty" 50 "fifty" 60 "sixty" 70 "seventy" 80 "eighty" 90 "ninety" }) | |||||||||||||||

The functions | (declare name-of) | |||||||||||||||

(defn two-digit-name [n] (let [low (rem n 10) high (- n low) ] (str (word-for high) (word-for low)))) | ||||||||||||||||

(defn three-digit-name [n] (let [high (quot n 100) low (rem n 100)] (if (zero? low) (str (word-for high) "hundred" ) (str (word-for high) "hundredand" (name-of low))))) | ||||||||||||||||

(defn name-of [n] (cond (< n 20) (word-for n) (< n 100) (two-digit-name n) (< n 1000) (three-digit-name n) (= n 1000) "onethousand")) | ||||||||||||||||

(defn solution [] (->> (range 1 1001) (map name-of) (map #(.length %)) (reduce + ))) | ||||||||||||||||

Docs: declare | ||||||||||||||||

Problem 18: Start at the top of the triangle, move to an adjacent number on the row below, continuing this way to construct a path to the bottom. Consider the sum of the integers along the path. What is the maximal sum that can be constructed? The original problem statement is available here. | (ns org.drcabana.euler.prob18 (use [clojure.string :only (split-lines)])) | |||||||||||||||

(def data-string "75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23") | ||||||||||||||||

Our data is given to us as a string, so we'll transform the string into something we can work with. First we'll turn it into a sequence of integers, then we'll turn that sequence into a data structure suited to our algorithmic needs. | ||||||||||||||||

Construct a sequence of integers from a string of whitespace delimited blocks of digits.
| (defn split-into-nums [string] (->> string (re-seq #"\d+") (map #(Integer. %)))) | |||||||||||||||

The data structure we want looks like this: ((75) (95 64) (17 47 82) (18 35 87 10) (20 4 82 47 65) ... ) | (def triangle (map split-into-nums (split-lines data-string))) | |||||||||||||||

The idea here is simple. Imagine the triangle has only three elements, say (a (b c)). Then the maximal path sum is (+ a (max b c)). The trick is to start with the two bottom rows, and work up. | ||||||||||||||||

(defn maximize [row] (letfn [(pair-max [[a b]] (max a b))] (map pair-max (partition 2 1 row)))) | ||||||||||||||||

(defn merge-rows [row1 row2] (map + (maximize row1) row2)) | ||||||||||||||||

(defn solution [] (first (reduce merge-rows (reverse triangle)))) | ||||||||||||||||

Notice that computing the maximal sum across all paths did not require determining the path along which the sum is maximal. | ||||||||||||||||

We resisted the temptation to use naked recursion. We could have tried transforming the numbers into the obvious binary tree, and defined the sum at the root to be the number at the root plus the max of the sums of the root's two subtrees, with appropriate stopping conditions at the leaves. For a small problem (like this one) it would have worked, but that algorithm uses resources exponential wrt to the depth of the tree. The algorithm actually used is quadratic wrt to the the number of elements in the last line of the triangle. | ||||||||||||||||

Docs: split-lines | ||||||||||||||||

Problem 19: how many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? The original problem statement is available here. | (ns org.drcabana.euler.prob19) | |||||||||||||||

(defn solution [] (let [year (mapcat #(range 1 (inc %)) [31 28 31 30 31 30 31 31 30 31 30 31]) leap-year (mapcat #(range 1 (inc %)) [31 29 31 30 31 30 31 31 30 31 30 31]) days-per-century (+ (* 25 366) (* 75 365)) ;; 25 leap years, 75 std years days-of-week (cycle [:tue :wed :thu :fri :sat :sun :mon]) ;; 1/1/1901 was a Tuesday calendar-dates (cycle (concat year year year leap-year)) ;; 1904 was a leap year Sunday? (fn [[day date]] (= :sun day)) first-of-month? (fn [[day date]] (= 1 date))] (->> (map vector days-of-week calendar-dates) (take days-per-century) (filter Sunday?) (filter first-of-month?) (count)))) | ||||||||||||||||

The solution is quite mechanical. We construct two sequences: one of calendar dates, and one of weekdays. Both sequences cycle endlessly. We count off a century's worth of elements from each sequence, pair up corresponding elements, filter out the pairs which satisfy our criteria, and count how many did so. | ||||||||||||||||

Problem 20 is to find the sum of the digits in the number 100!. The original problem statement is available here. | (ns org.drcabana.euler.prob20) | |||||||||||||||

(defn solution [] (->> (reduce *' (range 1 101)) ;; use of *' avoids overflow (str) ;; convert to string (map #(Integer. (str %))) ;; convert each digit to an integer (reduce +))) | ||||||||||||||||

Problem 21: Define d(n) as the sum of the proper divisors of n. If d(a) = b and d(b) = a, where a != b, then a and b are called amicable numbers. Sum the amicable numbers less than 10000. The original problem statement is available here. | (ns org.drcabana.euler.prob21) | |||||||||||||||

Compute the divisors of n. Each divisor is counted only once. | (defn divisors ([n d] (when (zero? (rem n d)) [d (quot n d)] )) ([n] (let [upperlim (inc (int (Math/sqrt n)))] (into #{} (mapcat #(divisors n %) (range 1 upperlim))))) ) | |||||||||||||||

(defn sum-of-divisors [n] (reduce + (divisors n))) | ||||||||||||||||

Predicate: is | (defn amicable? [n] (let [m (- (sum-of-divisors n) n) k (- (sum-of-divisors m) m)] (and (= n k) (not= n m)))) | |||||||||||||||

(defn solution [] (reduce + (filter amicable? (range 1 10000)))) | ||||||||||||||||

Problem 22: Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score. For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file? The original problem statement is available here. | (ns org.drcabana.euler.prob22) | |||||||||||||||

(defn solution [] (let [alpha (seq "ABCDEFGHIJKLMNOPQRSTUVWXYZ") point-values (zipmap alpha (iterate inc 1)) score (fn [name] (reduce + (map point-values name))) names (->> (slurp "data/names.txt") (re-seq #"[A-Z]+" ) (sort))] (reduce + (map * (map score names) (iterate inc 1) )))) | ||||||||||||||||

Problem 23: A positive integer n is called abundant if the sum of its proper divisors exceeds n. It can be proven that every integer greater than 28123 is the sum of two abundant numbers. Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. The original problem statement is available here. | (ns org.drcabana.euler.prob23 (:use [org.drcabana.euler.prob21 :only (divisors)])) | |||||||||||||||

(defn abundant? [n] (let [divs (divisors n) sum-proper-divisors (fn [k] (- (reduce + divs) k))] (> (sum-proper-divisors n) n))) | ||||||||||||||||

The magic constant 28123 is stipulated by the problem. | (def limit (inc 28123)) | |||||||||||||||

There are 6072 elements in | (def abundants (vec (filter abundant? (range 1 limit)))) | |||||||||||||||

Construct the set of numbers below | (defn sums-of-abundants [] (into #{} (for [a abundants b abundants :when (<= a b) :when (< (+ a b) limit)] (+ a b)))) | |||||||||||||||

(defn solution [] (let [total-all (reduce + (range 1 limit)) total-soa (reduce + (sums-of-abundants))] (- total-all total-soa))) | ||||||||||||||||

Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? The original problem statement is available here. | (ns org.drcabana.euler.prob24) | |||||||||||||||

The simple approach is to use brute force. Notice that each :when condition uses a set as a function to test for membership in the set. We simply force a through j to be distinct. | (defn perms [] (let [symbols (range 10)] (for [a symbols b symbols :when (nil? (#{a} b )) c symbols :when (nil? (#{a b} c)) d symbols :when (nil? (#{a b c} d)) e symbols :when (nil? (#{a b c d} e)) f symbols :when (nil? (#{a b c d e} f)) g symbols :when (nil? (#{a b c d e f} g)) h symbols :when (nil? (#{a b c d e f g} h)) i symbols :when (nil? (#{a b c d e f g h} i)) j symbols :when (nil? (#{a b c d e f g h i} j))] [a b c d e f g h i j]))) | |||||||||||||||

The Project Euler problem statement require the permutation to be represented as a 10 digit integer. | (defn perm-to-integer [perm] (bigint (apply str perm))) | |||||||||||||||

We generate permutations in lex order, and just pick the one we want. Clojure uses 0-based indexing, but the problem implicitly uses 1-based indexing. We need to adjust the index to get our answer. | (defn solution [] (perm-to-integer (nth (perms) 999999))) | |||||||||||||||

The brute force approach generated a lot of permutations we did not need. A fancier algorithm can compute the desired permutation directly. The algorithm takes advantage of a relationship between permutations of the digits 0...9 and the representation of integers in a factorial base. The details are beyond the scope of these comments, but the interested reader might look at this Wikipedia article. | ||||||||||||||||

Compute the factorial of n. | (defn fac [n] (reduce * (range 2 (inc n)))) | |||||||||||||||

Compute the sequence of factorials of the positive integers. | (defn factorials [] (map fac (iterate inc 1))) | |||||||||||||||

Express the positive integer
| (defn fbase ([n] (let [basis (reverse (take-while #(<= % n) (factorials)))] (fbase n basis [] ))) ([n basis accumulator] (if (empty? basis) accumulator (let [b (first basis)] (recur (rem n b) (rest basis) (conj accumulator (quot n b))))))) | |||||||||||||||

The nth permutation of the symbols 0-9 in lex order, indexing is 1-based. | (defn nth-perm [n] (loop [symbols (range 10) indices (fbase (dec n)) result []] (if (empty? indices) (concat result symbols) (let [k (first indices) sym (nth symbols k) without-sym (concat (take k symbols) (drop (inc k) symbols))] (recur without-sym (rest indices) (conj result sym)))))) | |||||||||||||||

(defn solution-alternative [] (perm-to-integer (nth-perm 1000000))) | ||||||||||||||||

Problem 25: What is the index of the first Fibonacci number at least 1000 digits long? The original problem statement is available here. | (ns org.drcabana.euler.prob25 (:use [clojure.math.numeric-tower :only (expt)] [org.drcabana.euler.prob02 :only (fibonacci)])) | |||||||||||||||

The problem implicitly uses 1-based indexing, Clojure uses 0-based indexing. So counting the 'too-small' cases gives the expected answer. | (defn solution [] (let [limit (expt 10 999) too-small? #(< % limit)] (->> (fibonacci) (take-while too-small?) (count)))) | |||||||||||||||

Problem 26 is to find the positive integer k < 1000 for which 1/k contains the longest recurring cycle in its decimal expansion. The original problem statement is available here. | (ns org.drcabana.euler.prob26) | |||||||||||||||

This problem centers about the algorithm for long division. Suppose n and d are positive integers. We want to divide n by d. If n > d, as our first step we compute (quot n d) and (rem n d). If not, we multiply n by 10 and then proceed as before. Each step subsequent step in long division is much the same. | (defn div-step [[n d]] (if (>= n d) [(* 10 (rem n d)) d] [(* 10 n) d])) | |||||||||||||||

Lets see the | ||||||||||||||||

| ||||||||||||||||

Hmm, that may not seem entirely clear. It becomes clearer if we actually compute the quotients denoted by each pair. | (defn quotient [[n d]] (quot n d)) | |||||||||||||||

| ||||||||||||||||

At this point we have the machinery needed to compute decimal expansions. Next we focus on finding the recurring block of digits. The following utility function will be useful. | ||||||||||||||||

Find the first repeated element in a sequence. If none is found, return nil. | (defn first-repeated-element ([xs] (first-repeated-element xs #{})) ([xs already-seen] (when-let [f (first xs)] (if (already-seen f) f (recur (next xs) (conj already-seen f)))))) | |||||||||||||||

The | ||||||||||||||||

Compute the recurring digits in the decimal expansion of 1/k for integer k. | (defn recurring-digits [k] (let [steps (iterate div-step [1 k]) fre (first-repeated-element steps)] (->> steps (drop-while #(not= fre %)) ;; lose any noise such as leading 0's next ;; drop the leading fre (take-while #(not= fre %)) ;; grab upto next instance of fre (cons fre) ;; put back the fre we dropped (map quotient)))) | |||||||||||||||

| ||||||||||||||||

Let's wrap this up. | (defn solution [] (let [scores (for [k (range 1 1001)] [k (count (recurring-digits k))])] (->> scores (sort-by second) ;; 2nd element is the number of recurring digits last ;; the last pair has the largest 2nd element first))) | |||||||||||||||

For quadratics of form n² + an + b, where |a| < 1000 and |b| < 1000, find the a and b that produce the longest run of primes for consecutive values of n, starting with n = 0. Return the product of a and b. The original problem statement is available here. | (ns org.drcabana.euler.prob27 (:use [org.drcabana.euler.prob07 :only (prime? primes)])) | |||||||||||||||

We'll need to construct quadratic functions specified by parameters
| (defn quadratic [a b] (let [q (fn [n] (+ (* n n) (* a n) b)) t (* a b)] [t q])) | |||||||||||||||

We score the quadratic function q by counting the length of the run of primes it generates. The returned value is a pair [t n] where t is the tag a*b, and n is the length of the run. | (defn score [[t q]] (->> (map q (range)) (take-while prime?) (count) (vector t))) | |||||||||||||||

A quick glance at the problem statement might suggest that we need to vary both a and b over (range -999 1000), giving nearly four million cases to consider. We can do better by an order of magnitude. | ||||||||||||||||

We are interested in quadratics that generate primes. In particular, for any quadratic q, we require (q 0) to be prime. But (q 0) is equal to b. Instead of testing 1999 values of b, we can restrict b to the 168 primes less than 1000. | (defn solution [] (let [quads (for [a (range -999 1000) b (take-while #(< % 1000) (primes))] (quadratic a b))] (->> (for [q quads] (score q)) (sort-by second) last ;; the last pair contains the high score first))) | |||||||||||||||

Notice the similarity of the | ||||||||||||||||

Starting at 1 and moving to the right in a clockwise direction, a 5 by 5 spiral is formed as follows: 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 The sum of the diagonals is 101. What is the sum of the the diagonals in a 1001 by 1001 spiral formed in the same way? The original problem statement is available here. | (ns org.drcabana.euler.prob28) | |||||||||||||||

Forget the diagonals. Consider the concentric squares centered at 1. Notice that the square with upper right corner 9 contains exactly 9 numbers, and so has a side of length 3. Similarly, the square with upper right corner 25 contains 25 numbers and has side 5. A bit of thought shows that the sides of the concentric squares are the odd numbers, starting from 3. | ||||||||||||||||

Why do we care about the concentric squares? Because it is easy to sum the corners of the squares, and that sum across all the squares differs from the sum of the diagonals by exactly 1. | ||||||||||||||||

Consider a particular square, say the square of side n=5, with corners 25, 21, 17, and
13. Expressed symbolically, the corners are n | ||||||||||||||||

(defn sum-of-corners [n] (+ (* 4 n n ) (* -6 n) 6)) | ||||||||||||||||

The solution is immediate, and uses the standard idioms. | (defn solution [] (let [odds (range 3 1002 2)] (inc (reduce + (map sum-of-corners odds))))) | |||||||||||||||

Problem 29 is to count the distinct terms are in the sequence generated by a*b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100. The original problem statement is available here. | (ns org.drcabana.euler.prob29 (:use [clojure.math.numeric-tower :only (expt)])) | |||||||||||||||

This one is immediate. | (defn solution [] (count (distinct (for [a (range 2 101) b (range 2 101)] (expt a b))))) | |||||||||||||||

Problem 30 is to find the sum of the integers greater than 1 that can be written as the sum of fifth powers of their digits. The original problem statement is available here. | (ns org.drcabana.euler.prob30 (:use [org.drcabana.euler.prob16 :only (digits)] [clojure.math.numeric-tower :only (expt)] )) | |||||||||||||||

We'll need a function to compute the sequence of digits of n.
Fortunately, we already have one of those, | ||||||||||||||||

| ||||||||||||||||

It's hard to come up with a good short name for a function that
computes the sum of the fifth powers of the digits of n. I'll just
call it | (defn phi [n] (reduce + (map #(expt % 5) (digits n)))) | |||||||||||||||

We need a name for integers that satisfy (== n (phi n)). Let's call them guilty numbers, and write a predicate to recognize them. | (defn guilty? [n] (== n (phi n))) | |||||||||||||||

The question is what to do now. We could use
| ||||||||||||||||

The trouble with this approach is that we don't know how many guilty numbers there
are. The problem statement implies that there are only
finitely many, but we don't know exactly how many. So using | ||||||||||||||||

We need an upper bound B on the size of the largest guilty number. Given such a bound, our solution would be (reduce + (filter guilty? (range 2 B))). | ||||||||||||||||

As it turns out, guilty numbers can't get very large. Why? Given any k-digit n, (phi n) is bounded above by (* k (expt 9 5)). Let's look at some concrete numbers. | ||||||||||||||||

| ||||||||||||||||

Notice that 999999 is much larger than (phi 999999), so there can not be any guilty numbers larger than 999999. This upper bound is not very tight, but it's good enough for the purpose at hand. | (defn solution [] (reduce + (filter guilty? (range 2 999999)))) | |||||||||||||||

In British currency there are eight coins: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). How many different ways can one make change for £2? The original problem statement is available here. | (ns org.drcabana.euler.prob31) | |||||||||||||||

Some variation of this problems appears in almost every introduction to combinatorics. Two simple ideas combine to give an elegant solution to the problem. | ||||||||||||||||

The first idea is obvious. When making change for N, either we use coin c, or we don't. So the number of ways to to make change is A+B, where A and B denote the following: | ||||||||||||||||

A : the number of ways to make change using c | ||||||||||||||||

B : the number of ways to make change without using c | ||||||||||||||||

The second idea is that the number of ways to make change for N using c is exactly the same as the number of ways to make change for N-c. Why? Consider any way to make change for N using c. Simply remove one instance of the coin c and you have change for N-c. | ||||||||||||||||

These two insights combine to give a very pretty recursive solution to the problem. | (defn ways-to-make-change [amount coins] {:pre [(apply < coins)]} ;; we require the coins sorted (let [c (first coins)] (cond (nil? c) 0 ;; no coins, no change (< amount c) 0 ;; if c is too big, so are the remaining coins (== amount c) 1 :else (+ (ways-to-make-change amount (rest coins)) (ways-to-make-change (- amount c) coins))))) | |||||||||||||||

(defn solution [] (ways-to-make-change 200 [1 2 5 10 20 50 100 200])) | ||||||||||||||||

This is one of those problems where recursion leads to a very natural solution. Just for grins, try writing a non-recursive solution. | ||||||||||||||||

Docs: apply | ||||||||||||||||

An n-digit number is pandigital if it makes use of each of the digits 1 to n exactly once. For example, the 5-digit number 15234 is pandigital. The product 7254 is unusual because the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital expresssion. Count each product only once. The original problem statement is available here. | (ns org.drcabana.euler.prob32 (:use [clojure.math.combinatorics :only [permutations]])) | |||||||||||||||

The fact that we want to use each of the digits 1 through 9 exactly once immediately suggests that we will want to generate permutations. Way back in problem 24 we generated permutations of the digits 0-9, by brute force. | (defn perms [] (let [symbols (range 10)] (for [a symbols b symbols :when (nil? (#{a} b )) c symbols :when (nil? (#{a b} c)) d symbols :when (nil? (#{a b c} d)) e symbols :when (nil? (#{a b c d} e)) f symbols :when (nil? (#{a b c d e} f)) g symbols :when (nil? (#{a b c d e f} g)) h symbols :when (nil? (#{a b c d e f g} h)) i symbols :when (nil? (#{a b c d e f g h} i)) j symbols :when (nil? (#{a b c d e f g h i} j))] [a b c d e f g h i j]))) | |||||||||||||||

That was fine for a one time thing, and it allowed me to illustrate
both the | ||||||||||||||||

Given a permutation, for example [ 3 9 1 8 6 7 2 5 4], we will split it into three parts, say [[3 9] [1 8 6] [7 2 5 4]], and then turn each of the parts into the number represented by the corresponding digits, here [39 186 7254]. We'll then test to see whether the product of the first two numbers is equal to the third. | ||||||||||||||||

Let's write some code. First we'll handle turning sequences of digits into numbers.
Horner's algorithm is simple, efficient,
and easily expressed using the | (defn horner [& digits] (reduce #(+ (* 10 %1) %2) 0 digits)) | |||||||||||||||

There are only two ways to split the permutations into three numbers such that the product of the first two is equal to the third. For instance, the product of two single digit numbers cannot equal a seven digit number. A bit of thought eliminates the other impossible cases. The feasible splits are either a two digit number and a three digit number producing a four digit number, or a one digit number and a four digit number producing a four digit number. | (defn phi [[a b c d e f g h i]] (let [x (horner a b) y (horner c d e) y1 (horner b c d e) z (horner f g h i)] (cond (== z (* x y)) z (== z (* a y1)) z :else 0))) | |||||||||||||||

I did not even try to give that last function a meaningful name. Mathematicians have very few qualms about meaningless function names, but some programmers find it difficult to let go. To them I say relax, take a walk on the wild side. | ||||||||||||||||

The problem requires that any given product be counted only once. The | (defn solution [] (->> (range 1 10) (permutations) (map phi) (distinct) (reduce +))) | |||||||||||||||

49/98 is a curious fraction, because it allows incorrect cancellation. One can cancel the 9, which is absurd, and still get the right result 49/98 = 4/8. We shall consider fractions like 30/50 = 3/5 as trivial. There are four non-trivial curious fractions less 1, with two digit numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator. The original problem statement is available here. | (ns org.drcabana.euler.prob33) | |||||||||||||||

Here's a better way to think about 'curious' fractions. The fraction 4/8 is curious because there exists a single digit integer n (n=9 as it happens) such that 4/8 = 4n/n8. Here juxtaposition does not denote mulitplication. Instead 4n denotes 4*10+n, and n8 denotes n*10 +8. | ||||||||||||||||

We need a way to turn two digits into a number in the obvious way. | (defn number [a b] (+ (* 10 a) b)) | |||||||||||||||

When the fraction j/k is curious return j/k, otherwise return nil. The numerator and denominator of Clojure ratios are relatively prime, i.e., have no common factors. | (defn curious ([[j k]] (first (keep (partial curious [j k]) (range 1 10)))) ([[j k] n] (let [jn (number j n) kn (number k n) nj (number n j) nk (number n k)] (some #{(/ j k)} [(/ jn kn) (/ jn nk) (/ nj kn) (/ nj nk)] )))) | |||||||||||||||

(defn solution [] (->> (for [a (range 1 10) b (range 1 10)] [a b]) (keep curious) (filter #(< % 1)) (reduce *) (denominator))) | ||||||||||||||||

Something I have neglected to mention so far is that in the | (defn solution-alternate [] (->> (for [a (range 1 10) b (range 1 10)] [a b]) (keep curious) (filter #(< % 1)) (reduce *) denominator)) | |||||||||||||||

Notice that | ||||||||||||||||

Docs: denominator keep partial some | ||||||||||||||||