dependencies

org.clojure/clojure		1.11.1
org.clojure/test.check		0.9.0

(this space intentionally left almost blank)

namespaces

euler.euler001
euler.euler011
euler.euler021
euler.euler031
euler.euler041
euler.euler051
euler.helper

euler.euler001

toc

(ns euler.euler001
  (:require [euler.helper :as helper]))

Problem 1 - Multiples of 3 and 5.

Description: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Task: Find the sum of all the multiples of 3 or 5 below 1000.

(defn p001
  ;; for the range 0 to (limit - 1)
  [limit] (->> (range limit)
                ;; filter the multiples (at least one divisor)
               (filter #(or (helper/factor? % 3)
                            (helper/factor? % 5)))
                ;; and sum up the resulting list
               (reduce +)))

Problem 2 - Even Fibonacci numbers

Description: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: (1), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Task: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

(defn p002
  [n] (->> helper/fibs
           (take-while #(< % n))
           (filter even?)
           (reduce +)))

Problem 3 - Largest prime factor

Description: The prime factors of 13195 are 5, 7, 13 and 29.

Task: What is the largest prime factor of the number 600851475143 ?

(defn p003
  [n] (helper/max-prime n helper/primes))

Problem 4 - Largest palindrome product

Description: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Task: Find the largest palindrome made from the product of two three-digit numbers.

(defn p004
  [n] (reduce
       ;; get the largest result of
       max (for [num1 (range n 0 -1)
                 ;; all numbers from 100 to 1000
                 num2 (range n 0 -1)
                 ;; compute the product of the two
                 :let [pal (* num1 num2)]
                 ;; and filter those who are palindromes
                 :when (helper/palindrome? pal)]
             pal)))

Problem 5 - Smallest multiple

Description: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

Task: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

(defn p005
  [n] (helper/least-common-multiple (range (inc n))))

Problem 6 - Sum square difference

Description: The sum of the squares of the first ten natural numbers is 1^2 + 2^2 + .. + 10^2 = 385. The square of the sum of the first ten natural numbers is (1 + 2 + .. + 10)^2 = 55^2 = 3025. Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Task: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

(defn p006
  [n] (let [nums (range (inc n))]
        (int (- (Math/pow (reduce + nums) 2)
                (reduce + (map #(Math/pow % 2) nums))))))

Problem 7 - 10001st prime

Description: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

Task: What is the 10 001st prime number?

(defn p007
  [n] (last (take n helper/primes)))

Problem 8 - Largest product in a series

Task: Find the greatest product of five consecutive digits in the 1000-digit number.

(defn p008
  [n series]
  (->> (helper/digits series)
       ;; partition into lists of 5
       (partition n 1)
       ;; calculate the product
       (map #(reduce * %))
       ;; get the highest product
       (reduce max)))

Problem 9 - Special Pythagorean triplet

Description: A Pythagorean triplet is a set of three natural numbers, a < b < c, where a^2 + b^2 = c^2 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

Task: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

(defn p009
  [n] (first (for [a (range n)
                   b (range (- n a))
                   :let [c (- n (+ a b))]
                   :when (and (< a b c)
                              (= (+ (Math/pow a 2) (Math/pow b 2))
                                 (Math/pow c 2)))]
               (* a b c))))

Problem 10 - Summation of primes

Description: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Task: Find the sum of all the primes below two million.

(defn p010
  [n] (->> helper/primes
           (take-while #(< % n))
           (reduce +)))

euler.euler011

toc

(ns euler.euler011
  (:require [euler.helper :as helper])
  (:import [java.util GregorianCalendar]))

Problem 11 - Largest product in a grid

Description: In the 20x20 grid, four numbers along a diagonal line have the product of 26 x 63 x 78 x 14 = 1788696.

Task: What is the greatest product of four adjacent numbers in the same direction - up, down, left, right, or diagonally - in the 20x20 grid?

(defn p011
  ([] (p011 20 4 (slurp "resources/p011_matrix.txt")))
  ([size len input-str]
   (helper/product size len (helper/parse-grid input-str size))))

Problem 12 - Highly divisible triangular number

Description The sequence of triangle numbers is generated by adding the natural numbers. The 7th triangle number is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

Task: What is the value of the first triangle number to have over five hundred divisors?

(defn p012
  ([] (p012 500))
  ([n] (->> helper/triangles
            (drop-while #(< (helper/count-divisors %) n))
            first)))

Problem 13 - Large sum

Task: Work out the first ten digits of the sum of the given one-hundred 50-digit number.

(defn p013
  ([] (p013 10 "resources/p013_numbers.txt"))
  ([n input] (->> input
                  (slurp)
                  (re-seq #"\d+")
                  (map bigdec)
                  (map #(helper/truncate % n))
                  (reduce +)
                  (long))))

Problem 14 - Longest Collatz sequence

Description: The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even), n → 3n + 1 (n is odd).

Using the rule above and starting with thirteen, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Task: Which number under one million produces the longest chain?

(defn p014
  ([] (p014 (Math/pow 10 6)))
  ([limit]
   (let [cache (atom {1 1})]
     (doseq [n (range 1 limit)] (helper/memo-collatz cache n))
     (key (apply max-key val @cache)))))

Problem 15 - Lattice paths

Description: Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

Reference: http://www.robertdickau.com/manhattan.html The number of paths are the central binomial coefficients, Binomial[2n, n] or (2n)!/(n!)^2, central meaning they fall along the center line of Pascal’s triangle.

Task: How many lattice routes are there through a 20×20 grid?

(defn p015
  ([] (p015 20))
  ([n] (helper/lattice-paths n)))

Problem 16 - Power digit sum

Description: 2^15 = 32768, the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

Task: What is the sum of the digits of the number 2^1000?

(defn p016
  ([] (p016 (.pow (BigInteger. "2") 1000)))
  ([n] (reduce + (helper/digits n))))

Problem 17 - Number letter counts

Description: 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 in total.

NOTE: 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 use of "and" when writing out numbers is in compliance with British usage.

Task: If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

(defn p017
  ([] (p017 1000))
  ([n] (->> (range 1 (inc n))
          ;; map to corresponding string
            (map helper/to-words)
          ;; concatenate
            (apply str)
          ;; count the number of chars
            (count))))

Problem 18 - Maximum path sum I

Description:

   3      By starting at the top of the triangle left
  7 4     and moving to adjacent numbers on the row below,
 2 4 6    the maximum total from top to bottom is 23.
8 5 9 3   That is, 3 + 7 + 4 + 9 = 23.

Task: Find the maximum total from top to bottom of the triangle below.

(defn p018
  []
  (let
   [triangle
    [[75]
     [95 64]
     [17 47 82]
     [18 35 87 10]
     [20 4 82 47 65]
     [19 1 23 75 3 34]
     [88 2 77 73 7 63 67]
     [99 65 4 28 6 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 4 68 89 53 67 30 73 16 69 87 40 31]
     [04 62 98 27 23 9 70 98 73 93 38 53 60 4 23]]
    merge-rows
    (fn [a b]
       ;; look at the two elements in the row below it,
       ;; take the max of those two elements,
       ;; and sum them to the original element.
      (map + (map #(reduce max %) (partition 2 1 a)) b))]
    (first (reduce merge-rows (reverse triangle)))))

Problem 19 - Counting Sundays

Description: 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, saving February alone, which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

Task: How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

(defn p019
  []
  ;; solution by hroi: http://clojure-euler.wikispaces.com/Problem+019
  (reduce +
          (for [year (range 1901 (inc 2000)) month (range 1 (inc 12))
                :let [cal (doto (GregorianCalendar.)
                            (.set GregorianCalendar/YEAR year)
                            (.set GregorianCalendar/MONTH month)
                            (.set GregorianCalendar/DAY_OF_MONTH 1))
                      day (.get cal GregorianCalendar/DAY_OF_WEEK)]
                :when (= GregorianCalendar/SUNDAY day)] 1)))

Problem 20 - Factorial digit sum

Description: n! means n × (n − 1) × ... × 3 × 2 × 1. For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Task: Find the sum of the digits in the number 100!

(defn p020
;; analogous to Problem 16
  ([] (p020 100))
  ([n] (reduce + (helper/digits (helper/factorial n)))))

euler.euler021

toc

(ns euler.euler021
  (:require [euler.helper :as helper]))

Problem 21 - Amicable numbers

Description: Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Task: Evaluate the sum of all the amicable numbers under 10000.

(defn p021
  ([] (p021 10000))
  ([n] (->> (range 1 (inc n))
            (map helper/amicable?)
            (flatten)
            (distinct)
            (reduce +))))

Problem 22 - Names scores

Description: Using 'http://projecteuler.net/project/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, worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

Task: What is the total of all the name scores in the file?

(defn p022
  ([] (p022 (re-seq #"\w+" (slurp "resources/p022_names.txt"))))
  ([names]
   (let
    [input (sort names)
     ;; sum of the numerical representation of each character
     get-value (fn [name] (reduce + (map #(- (int %) 64) name)))
     ;; get the position
     get-index (fn [name] (inc (.indexOf input name)))]
      ;; compute the product of value and position
     (reduce + (map #(* (get-index %) (get-value %)) input)))))

Problem 23 - Non-abundant sums

Description: A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number. A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Task: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

(defn p023
  ([] (p023 (range 1 (inc 28123))))
  ([input] (->> input
                (remove helper/abundant-sum?)
                (reduce +))))

Problem 24 - Lexicographic permutations

Description: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210.

Background: http://clojure-euler.wikispaces.com/Problem+024 With n elements, there are n! permutations; grouping based on the first element in the permutation, there are n permutation groups, each of size (n-1)!. To find the first element of the ith permutation is therefore to find its first element (quotient of (i-1) and n), and then to recur to find the ((i-1) mod n)th permutation of the remaining elements. To avoid having to subtract by 1 each time, the recursive loop uses 0-based indexing, and is initialized with i-1.

Return permutation pos of the list of digits.

(defn permute-nth
  [s pos] (let [n (count s)
                m (reduce * (range 1 n))
                r (rem pos m)
                e (nth s (quot pos m))]
            (if (= n 1) s
                (cons e (permute-nth (remove #(= % e) s) r)))))

Task: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

(defn p024
  [] (permute-nth (range 10) (dec 1000000)))

Problem 25 - 1000-digit Fibonacci number

Task: What is the first term in the Fibonacci sequence to contain 1000 digits?

(defn p025
  ([] (p025 1000))
  ;; Fibonacci terms converge to (n)*Phi=(n+1),
  ;; where Phi is the Golden Ratio (1+sqrt5)/2.
  ([n] (int (Math/ceil
             (/ (+ (dec n) (Math/log10 (Math/sqrt 5)))
                (Math/log10 helper/phi))))))

Problem 26 - Reciprocal cycles

Description: A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5 1/7 = 0.(142857) 1/3 = 0.(3) 1/8 = 0.125 1/4 = 0.25 1/9 = 0.(1) 1/5 = 0.2 1/10 = 0.1 1/6 = 0.1(6)

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the longest recurring cycle in a fraction.

(defn rec-cycle
  [n d] (loop [n n d d acc [] rems #{}]
          (let [div (int (/ n d)) rem (mod n d)]
            (if (zero? rem) ()
                (if (contains? rems rem)
                  (drop-while #(not= % (int (/ (* rem 10) d)))
                              (drop 1 (conj acc div)))
                  (recur (* rem 10) d
                         (conj acc div)
                         (conj rems rem)))))))

Recurring cycles of numbers under 1000.

(def kvs
  (map #(vector % (count (rec-cycle 1 %)))
       (take 1000 (iterate dec 1000))))

Task: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

(defn p026
  [] (first (apply max-key second kvs)))

Problem 27 - Quadratic primes

Description: Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479. Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n e.g. |11| = 11 and |−4| = 4

Returns a generator function of the form: n² + an + b.

(defn quadratic
  [a b] (fn [n] (+ (* (+ n a) n) b)))

given a generator function, returns the amount of consecutive prime numbers generated

(defn consec-primes
  [a b] (->>
         (iterate inc 0) ;; for Integers starting from zero
         (map (quadratic a b)) ;; apply the generator of the form: n² + an + b
         (take-while #(and (pos? %) (helper/prime? %))) ;; get all the primes
         (count))) ;; count # of primes

count # of primes

All quadratic prime generators between a and b.

(defn quads
  [nums]
  (for [a nums b nums]
    [(consec-primes a b) a b]))

Retrieve the product of the maximum

(defn find-max
  [nums]
  (let [[n a b] (first (sort-by first > (quads nums)))]
    (* a b)))

Task: Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

(defn p027
  ([] (p027 (range -999 1000))) ;; max prime generator between -999 and 999
  ([nums] (find-max nums)))

Problem 28 - Number spiral diagonals

Description: Starting with the number 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

It can be verified that the sum of the numbers on the diagonals is 101.

Task: What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

(defn p028
  ([] (p028 1001))
  ([n]
   {:pre [(odd? n)]}      ;; precondition: spirals can only have an odd length
   (if (= n 1) 1          ;; base case: f(1) = 1
       (reduce + (cons
                ;; recursive case: cons it to the recusive call of f(n -2)
                  (p028 (- n 2))
                  (take 4 ;; take four values per 'ring'
                          ;; creating 'ring': from n * n, dec in steps of n- 1
                        (iterate #(- % (dec n)) (* n n))))))))

Problem 29 - Distinct powers

Description: Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^2=4, 2^3=8, 2^4=16, 2^5=32 3^2=9, 3^3=27, 3^4=81, 3^5=243 4^2=16, 4^3=64, 4^4=256, 4^5=1024 5^2=25, 5^3=125, 5^4=625, 5^5=3125 If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

Task: How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

(defn p029
  ([] (p029 100))
  ([n]
   (->>
    ;; typical list comprehension problem
    (for [a (range 2 (inc n))
          ;; for 2 to n
          b (range 2 (inc n))]
      ;; return a^b
      (Math/pow a b))
    ;; distinct elements
    (set)
    ;; count them
    (count))))

Problem 30 - Digit fifth powers

Description: Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included. The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Task: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

(defn p030
  ([] (p030 5))
  ([exp]
    ;; 6*9**5 = 354294 as the upper limit..
   (let [limit (* (inc exp) (Math/pow 9 exp))]
      ;; predicate checking for being a sum of powers
     (reduce + (filter #(helper/narcissistic? % exp)
        ;; TODO only insert permutations of digits
                       (range 2 limit))))))

euler.euler031

toc

(ns euler.euler031
  (:require [euler.helper :as helper]))

Problem 31 - Coin sums

Description: In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

Task: How many different ways can £2 be made using any number of coins?

(defn p031
  ([] (p031 200 [200 100 50 20 10 5 2 1]))
  ([n coins] (helper/combinations n coins)))

Problem 32 - Pandigital products

Description: We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital. The product 7254 is unusual, as 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. HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

There are only two patterns of multiplications that produce 9 digits: 1. A 1 digit number times a 4 digit number can be 4 digits long. 2. A 2 digit number times a 3 digit number can be 4 digits long.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

(defn p032
  [] (reduce + (distinct (for [a (range 2 5000)
                               b (range a (/ 9999 a))
                               :let [prod (* a b)]
                               :when (helper/pandigital? (str a b prod))]
                           prod))))

Problem 33 - Digit cancelling fractions

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples. There are exactly four non-trivial examples of this type of fraction, less than one in value, with two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Find the denominator of the four non-trivial examples.

(defn p033
  [] (denominator (reduce * (for [a (range 1 10)
                                  b (range 1 10)
                                  c (range 1 10)
                                  :let [num (+ (* 10 a) b)
                                        den (+ (* 10 b) c)
                                        divisor (/ num den)]
                                  :when (and (< divisor 1)
                                             (= divisor (/ a c)))]
                              (/ num den)))))

Problem 34 - Digit factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Caching the factorials of the digits 0 to 9

A number that is equal to the sum of the factorial of its digits.

(def ^:private fact
  (apply hash-map (interleave (seq "0123456789")
                              (map helper/factorial
                                   (range 10)))))
(defn- curious?
  [n] (->> n
           (str)
           (map fact)
           (reduce +)
           (= n)))

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

(defn p034
  [] (->> (range 10 (* 7 (helper/factorial 9)))
          (filter curious?)
          (reduce +)))

Problem 35 - Circular primes

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. How many circular primes are there below one million?

A prime is circular if all rotations of the digits are themselves prime.

(defn- circular-prime?
  [n] (->> (str n)
           (helper/rotations)
           (map #(clojure.string/join %))
           (map #(Integer/parseInt %))
           (every? helper/prime?)))

How many circular primes are there below one million?

(defn p035
  [] (->> helper/primes
          (take-while #(< % (Math/pow 10 6)))
          (filter circular-prime?)
          (count)))

Problem 36 - Double-base palindromes

The decimal number, 585 = 1001001001 (bin), is palindromic in both bases. Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. (Please note that the palindromic number, in either base, may not include leading zeros.)

Convert decimal Integers into binary representation.

(defn- dec->bin
  [n] (if (<= 0 n 1) n
          (+' (*' 10 (dec->bin (quot n 2))) (mod n 2))))

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(defn p036
  [] (->> (range 1 (Math/pow 10 6))
          (filter helper/palindrome?)
          (filter (comp helper/palindrome? dec->bin))
          (reduce +)))

Problem 37 - Truncatable primes

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7.

Similarly we can work from right to left: 3797, 379, 37, and 3. Find the sum of the only eleven primes that are both truncatable from left to right and right to left. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

'rest' for Integers.

(defn- remove-first-digit
  [n] (->> n Math/log10 int (Math/pow 10) int (mod n)))

'butlast' for Integers.

(defn- remove-last-digit
  [n] (int (/ n 10)))

Being prime itself, it is possible to continuously remove digits from left to right as well as from right to left, and remain prime at each stage.

(defn- truncatable-prime?
  [n] (let [trunc-prime? (fn [f n] (cond
                                     (< n 10) (helper/prime? n)
                                     (helper/prime? n) (recur f (f n))
                                     true false))]
        (and (trunc-prime? remove-last-digit n)
             (trunc-prime? remove-first-digit n))))

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

(defn p037
  [] (reduce + (take 11 (filter truncatable-prime? (iterate inc 10)))))

Problem 38 - Pandigital multiples

Take the number 192 and multiply it by each of 1, 2, and 3: 192 × 1 = 192, 192 × 2 = 384, 192 × 3 = 576.

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3). The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

(defn concat-product [n upper]
  (->> (range 1 (inc upper))
       (map #(* n %))
       (mapcat str)
       (apply str)
       (read-string)))

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

(defn p038
  [] (apply max
            (for [r (range 1 10)
                  n (range 1 9999)
                  :let [product (concat-product n r)]
                  :when (and (< product 987654321) (helper/pandigital? product))]
              product)))

Problem 39 - Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

(defn integer-right-triangles [n]
  (for [a (range 1 500)
        b (range a 500)
        :let [c (- n a b)]
        :when (and (every? pos? [a b c])
                   (= (+ (* a a) (* b b)) (* c c)))]
    [a b c]))

For which value of p ≤ 1000, is the number of solutions maximised?

(defn p039
  [n] (->> (range 1 (inc n))
           (map integer-right-triangles)
           (map #(vector (apply + (first %)) (count %) %))
           (sort-by second >)
           first))

Problem 40 - Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers: 0.123456789101112131415161718192021... ^ It can be seen that the 12th digit of the fractional part is 1. If dn represents the nth digit of the fractional part, find the value of the following expression. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

(defn digit-of-decimal-fraction [n]
  (read-string (str (nth (mapcat str (range)) n))))

Find the value of the expression d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000.

(defn p040
  [] (->> (range 7) ; [1 10 100 1000 10000 100000 1000000]
          (map #(digit-of-decimal-fraction (Math/pow 10 %)))
          (reduce *)))

euler.euler041

toc

(ns euler.euler041
  (:require [euler.helper :as helper]))

Problem 41 - Pandigital prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime. What is the largest n-digit pandigital prime that exists?

What is the largest n-digit pandigital prime that exists?

(defn p041
  [] (->> (for [x (range 1 10)] (apply str (range 1 (inc x))))
          (mapcat helper/permutations)
          (map #(read-string (apply str %)))
          (filter helper/prime?)
          (apply max)))

Problem 42 - Coded triangle numbers

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55.

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt, a 16K text file containing nearly two-thousand common English words, how many are triangle words?

(defn word-value
  [s] (->> s
           seq
           (map #(- (int %) 64))
           (reduce +)))

How many are triangle words?

(defn p042
  [] (->> "resources/p042_words.txt"
          slurp
          (re-seq #"\w+")
          (map word-value)
          (filter helper/triangle?)
          count))

Problem 43 - Sub-string divisibility

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property. Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

d2d3d4=406 is divisible by 2 d3d4d5=063 is divisible by 3 d4d5d6=635 is divisible by 5 d5d6d7=357 is divisible by 7 d6d7d8=572 is divisible by 11 d7d8d9=728 is divisible by 13 d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

(defn substrings
  [ds] (map #(Integer/parseInt (apply str %)) (partition 3 1 ds)))

(defn prime-divisible? [xs]
  (->> (take 7 helper/primes)
       (map helper/factor? (rest xs))
       (every? true?)))

(defn p043
  [] (->> (range 10)
          helper/permutations
          (filter #(prime-divisible? (substrings %)))
          (map #(Long/parseLong (apply str %)))
          (reduce +)))

Problem 44 - Pentagon numbers

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal. Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

Pn=n(3n−1)/2 = (3n^2-n)/2

(defn nth-pentagonal [n]
  (/ (* n (dec (* 3 n))) 2))

inverse the quadratic formula: https://www.educative.io/answers/project-euler-44-pentagonal-numbers

(defn pentagonal? [n]
  (zero? (mod (+ 1 (Math/sqrt (+ 1 (* 24 n)))) 6)))

(defn p044 []
  (first (for [k (range)
               j (range 1 k)
               :let [x (nth-pentagonal k)
                     y (nth-pentagonal j)]
               :when (and (< y x) (pentagonal? (+ x y)) (pentagonal? (- x y)))]
           (- x y))))

Problem 45 - Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ... Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ... Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755. Find the next triangle number that is also pentagonal and hexagonal.

(defn triangle? [n]
  (zero? (mod (- (Math/sqrt (+ 1 (* 8 n))) 1) 2)))

Hn=n(2n−1) = 2n^2 - n

(defn hexagonal [n]
  (* n (- (* 2 n) 1)))

(defn p045 []
  (second (for [n (drop 2 (range))
                :let [hex (hexagonal n)]
                :when (and (pentagonal? hex) (triangle? hex))]
            hex)))

Problem 46 - Goldbach's other conjecture

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2 15 = 7 + 2×2^2 21 = 3 + 2×3^2 25 = 7 + 2×3^2 27 = 19 + 2×2^2 33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

composite numbers are those that are not prime and not 1.

(def odd-composites
  (filter #(and (odd? %) (not (helper/prime? %))) (drop 2 (range))))

(defn conjecture? [n]
  (let [ps (take-while #(<= % n) helper/primes)
        is-int? (fn [n] (== (int n) n))
        conjs (filter #(is-int? (Math/sqrt (/ (- n %) 2))) ps)]
    (first conjs)))

(defn p046 []
  (first (filter (complement conjecture?) odd-composites)))

Problem 47 - Distinct primes factors

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7 15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

(defn distinct-factors [n]
  (if (= 0 n) 0
      (count (set (helper/get-primes n)))))

(defn has-primes? [x ns]
  (every? (partial = x) (map distinct-factors ns)))

(defn p047 []
  (->> (range)
       (partition 4 1)
       (filter (partial has-primes? 4))
       first))

Problem 48 - Self powers

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

(defn p048 []
  (->> (range 1 1001)
       (map #(helper/exp-by-square % %))
       (reduce +)
       helper/digits
       reverse
       (take 10)
       reverse
       (apply str)))

Problem 49 - Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

(defn combinations [ns]
  (for [x ns y ns
        :when (< x y)]
    [x y]))

(defn map-increase [sequence]
  (reduce (fn [a b] (when (= (last a) (first b)) (concat a [(second b)]))) sequence))

(defn distances [ns]
  (->> ns
       combinations
       (group-by #(abs (- (second %) (first %))))
       (reduce (fn [m [k v]] (assoc m k (map-increase v))) {})))

(def get-increments
  (->> helper/primes
       (drop-while #(< % 1000))
       (take-while #(< % 10000))
       (group-by #(vec (sort (helper/digits %))))
       (reduce (fn [m [k v]] (assoc m k (distances v))) {})
       (mapcat (fn [[_ v]] (filter #(= 3 (count (second %))) v)))))

(defn p049 []
  (->> get-increments
       first
       second
       (apply str)))

Problem 50 - Consecutive prime sum

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

(defn conseq-primes [below]
  (let [p-range (take-while #(< % below) helper/primes)
        cands (for [from p-range
                    to (drop-while #(<= % from) p-range)
              :let [span (->> p-range
                              (drop-while #(< % from))
                              (take-while #(<= % to)))
                    cand (reduce + span)]
              :while (< cand below)
              :when (helper/prime-fast? cand)]
          [cand span])]
    (apply max-key #(count (second %)) cands)))

(defn p050 []
  (first (conseq-primes 10e6)))

euler.euler051

toc

(ns euler.euler051
  (:require [clojure.string :as str]
            [euler.helper :as helper]))

Problem 51 - Prime Digit Replacements

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

euler.helper

toc

(ns euler.helper
    (:require [clojure.string :as str]))

function composition

== point-free notation ===================================================== shortcuts

partial application

(def &  comp)
(def p  partial)

== benchmarking ============================================================ taken from https://adambard.com/blog/clojure-reducers-for-mortals/

Map f over the range of N x times.

(defn benchmark
  [f N x] (let [nums (vec (range N))
                start (System/currentTimeMillis)]
            (dotimes [n x]
              (f nums))
            (- (System/currentTimeMillis) start)))

== factorisation ===========================================================

factor? :: dividend:Int, divisor:Int -> Bool: Predicate that tests whether the divisor evenly divides the dividend.

(def factor?
  (& zero? (p mod)))

factor-any :: [Int] -> Int -> Bool: Predicate that tests whether its argument can be evenly divided by any of the divisors.

(defn factor-any
  [divisors argument]
  (boolean (some #(factor? argument %) divisors)))

factors :: Int -> [Int] Returns all numbers that evenly divide n.

(defn factors
  ([n] (factors n 1))
  ([n start]
   (lazy-seq (let [lower (filter #(factor? n %)
                                  ;; iterate up to sqrt(n)
                                 (range start (inc (Math/sqrt n))))
                    ;; add the coresponding divisor pairs
                   upper (map #(/ n %) lower)]
               (set (concat lower upper))))))

facts :: [Int] Lazy, infinite sequence of all factorial numbers.

(def factorials
  ;; *' supports arbitrary precision
  (lazy-cat [1] (map *' factorials (iterate inc 2))))

Int -> [Int] Multiplies all natural numbers from 1 to n+1.

(defn factorial
  [n] (nth factorials (if (< n 1) 0 (dec n))))

lattice-paths :: Int -> Int The central binomial coefficients, Binomial[2n, n] or (2n)!/(n!)^2.

(defn lattice-paths
  [n]
  ;; divide the factorial of 2n
  (long (/ (factorial (* 2 n))
           ;; by (fac(n))^2
           (Math/pow (factorial n) 2))))

triangle :: [Int] Lazy seq of all triangle numbers. A triangle number is generated by adding the natural numbers up to n.

(def triangles
  (lazy-cat [1] (map + triangles (iterate inc 2))))

triangle? :: Int -> Bool Checks whether a given number n is a triangle number.

(defn triangle?
  [n] (some #{n} (take-while #(<= % n) triangles)))

== Fibonacci Sequence ======================================================

fibs :: [Int] Lazy sequence of all Fibonacci numbers. Using BigIntegers.

Background: A Fibonacci number (exept 0 and 1) is recursively defined as the sum of its two predecessing Fibonacci numbers:

base case: fib(n <= 1) = n
rec case: fib(n > 1) = fib(n - 1) + fib(n - 2)

(def fibs
  (map first (iterate (fn [[a b]] [b, (+ a b)]) [0N, 1N])))

next-collatz :: Int -> Int Computes the next number of the collatz sequence.

(defn next-collatz
  [n] (if (even? n) (bit-shift-right n 1) (inc (* 3 n))))

collatz :: [Int] Lazy seq of Collatz sequence of n.

(defn collatz
  [n] (cons n
            (if (= n 1) '()
                (collatz (next-collatz n)))))

memo-collatz :: [Int] Memoized collatz sequence using an atom.

(defn memo-collatz
  [c n] ;; TODO not sure this works efficiently..
  (if-let [entry (@c n)] entry ;; already present - return the count
          ((swap! c assoc n  ;; new entry - store in cache
                  (inc (memo-collatz c (next-collatz n))))
           n)))

parse-grid :: String -> [[Int]] Converts a string into a dimension x dimension vector of integers.

(defn parse-grid
  [grid-str dimension] (->> (.split grid-str "\\s+")
                            (map #(Integer. %))
                            (partition dimension)
                            (map vec)
                            (vec)))

Inspired by Chouser

(defn product
  [size len grid]
  ;; only works for quadratic matrices
  {:pre [(= size (count grid) (count (first grid)))]}
  ;; get the highest value
  (reduce max
          (for [sx (range 0 size)
                sy (range 0 size)
                ;;          \/    \     ->     /
                delta-yx [[1 0] [1 1] [0 1] [-1 1]]]
            ;; compute the product
            (reduce *
                    ;; partition into sequences of four
                    (for [yx (take len (iterate #(map + delta-yx %) [sy sx]))
                          :while (every? #(< -1 % size) yx)]
                      (reduce nth grid yx))))))

Update the sieve with the given composite number.

(defn- next-comp
  [x step sieve]
  (if (sieve x)
    ;; the composite number has already been found previously
    (recur (+ x step) step sieve)
    ;; brand new composite number
    (assoc sieve x step)))

Retrieve the next prime number using the given sieve.

(defn- next-prime
  [x sieve]
  (let [step (sieve x)]
    (if (sieve x)
      ;; found a composite
      (recur (+ x 2) (next-comp (+ x step) step (dissoc sieve x)))
      ;; found a prime
      (cons x (lazy-seq (next-prime (+ x 2) (assoc sieve (* x x) (* x 2))))))))

primes :: [Int] Lazy stream of prime numbers, generated by the sieve of Eratosthenes algorithm. Internally stores in a hastable the next composite number corresponding to the prime number. Taken from http://voidmainargs.blogspot.de/2010/12/ lazy-sieve-eratosthenes-in-scala-and.html

(def primes
  (cons 2 (lazy-seq (next-prime 3 {}))))

prime? :: Int -> Bool Checks whether a given number n is a prime number.

(defn prime?
  [n] (and (< 1 n)
           (not-any? #(factor? n %)
                     (take-while #(<= (* % %) n) primes))))

(defn prime-fast? [n]
  (.isProbablePrime (BigInteger/valueOf n) 5))

get-primes :: Int -> [Int] Get the prime divisors of n.

iterative approach

(defn get-primes
  ;; entry point - start with the list of primes and [] as accumulator
  ([n] (get-primes n primes []))
  ([n [car & cdr :as ps] acc]
   (cond
    ;; no more factors - stop iteration
     (< n car) acc
    ;; if factor - add to set of prime factors
     (factor? n car) (recur (/ n car) ps (conj acc car))
    ;; no match - next iteration
     :else (recur n cdr acc))))

max-prime :: Int, [Int] -> Int Given a number n and a list of prime numbers ps, returns the largest prime factor of n.

(defn max-prime
  [n [car & cdr :as ps]]
  (cond
   ; termination - found max prime
    (= n car) car
   ; shrinking
    (factor? n car) (recur (/ n car) ps)
   ; list eater
    :else (recur n cdr)))

* prime-factors :: Int -> [Int]* Given a number, returns the list of prime factors of n. Example: (prime-factors 12) => (2 2 3)

(defn prime-factors
  ([n] (prime-factors n [] primes))
  ([number factors ps]
   (cond
     (= 1 number) factors
     (factor? number (first ps)) (prime-factors (/ number (first ps))
                                                (conj factors (first ps)) ps)
     :else (prime-factors number factors (rest ps)))))

count-divisors :: Int -> Int Calculates the number of divisors of n (including 1 and n itself).

(defn count-divisors
  [n] (if (zero? n) 0
          (->> (prime-factors n)
               (partition-by identity)
               (map count)
               (map inc)
               (reduce *))))

palindrome? :: Int -> Bool Checks whether the given number n is a palindrome. Uses reversed string comparison

(defn palindrome?
  [n] (= (str n) (str/reverse (str n))))

least-common-multiple :: [Int] -> Int Computes the smallest number divisible by all of the given input numbers. See http://en.wikipedia.org/wiki/Leastcommonmultiple.

(defn least-common-multiple
  [input]
  (->> input
       (map #(frequencies (get-primes %)))
       (apply merge-with max)
       (map #(Math/pow (first %) (second %)))
       (reduce *)
       (int)))

sum-of-factors :: Int -> Int The sum of all proper divisors, excluding n.

(defn sum-of-factors
  [n] (reduce + 1 (factors n 2))) ; include 1, but ignore n

amicable? :: Int -> Bool Is a an amicable number?

(defn amicable?
  [a]
  (let [b (sum-of-factors a)]
    (if (and (not= a b) (= a (sum-of-factors b)))
      [a b] ())))

abundant? :: Int -> Bool Checks whether the sum of the factors of n (excluding n) is greater than n.

(defn abundant?
  [n] (< (* 2 n) (reduce + (factors n))))

abundants :: [Int] All abundant numbers.

(def abundants
  (into (sorted-set) (filter abundant? (range 12 28124))))

abundant-sum? :: Int -> Boolean Can n be expressed as the sum of two abundant numbers?

(defn abundant-sum?
  [n] (boolean (some #(abundants (- n %)) (take-while #(< % n) abundants))))

truncate :: Int, Int -> Int Truncates the given number up to the first n digits.

(defn truncate
  [number digits]
  (->> digits
       (inc)
       (- (count (str number)))
       (Math/pow 10)
       (/ number)
       (Math/floor)))

phi :: Double The Golden Ratio - (1+sqrt5)/2.

(def phi
  (/ (inc (Math/sqrt 5)) 2))

digits :: Int -> [Int] Converts a number n into a list of its digits.

(defn digits
  [n] (map #(Character/getNumericValue %) (str n)))

narcissistic? :: Int, Int -> Bool Valid numbers can be written as the sum of its nth powers. Exp.: 1634 = 1^4 + 6^4 + 3^4 + 4^4.

(defn narcissistic?
  [n exp]
  (->> (digits n)
       (map #(Math/pow % exp))
       (reduce +)
       (== n)))

singles :: [Int] The literals of the numbers 1,2,..19

(def singles
  ["one" "two" "three" "four" "five" "six" "seven" "eight" "nine" "ten"
   "eleven" "twelve" "thirteen" "fourteen" "fifteen" "sixteen" "seventeen"
   "eighteen" "nineteen"])

tens :: [Int] The literals of the numbers 20,30,...90

(def tens
  ["twenty" "thirty" "forty" "fifty"
   "sixty" "seventy" "eighty" "ninety"])

Converts a number (up to 1000) into its string representation, omitting spaces. Example: (to-words 115) => 'onehundredandfifteen'.

(defn to-words
  [n]
  (cond
    (< n 20) (nth singles (dec n))
    (< n 100) (if (factor? n 10)
                (nth tens (/ (- n 20) 10))
                (str (nth tens (/ (- n 20) 10))
                     (nth singles (dec (mod n 10)))))
    (< n 1000) (if (factor? n 100)
                 (str (to-words (/ n 100)) "hundred")
                 (str (to-words (/ n 100)) "hundredand"
                      (to-words (rem n 100))))
    (= n 1000) "onethousand"))

combinations :: Int, [Int] -> Int Returns the number of combinations that can be computed from the list of numbers.

(defn combinations
  [amount [car & cdr :as coins]]
  (cond
    (zero? amount) 1
    (or (neg? amount) (empty? coins)) 0
    :else (+ (combinations amount cdr)
             (combinations (- amount car) coins))))

Returns a lazy seq of all rotations of a seq. Taken from clojure.contrib

(defn rotations
  [x] (if (seq x)
        (map (fn [n _]
               (lazy-cat (drop n x) (take n x)))
             (iterate inc 0) x)
        (list nil)))

Makes use of all the digits 1 to n exactly once.

(defn pandigital?
  [n] (= "123456789"
         (str/join (sort (.split (str n) "")))))

(defn permutations [s]
  (lazy-seq
   (if (seq (rest s))
     (apply concat
            (for [x s] (map #(cons x %) (permutations (remove #{x} s)))))
     [s])))

(defn exp-by-square [x n]
  (loop [y 1N x (bigint x) n (bigint n)]
    (cond (< n 0) (recur y (/ 1 x) (- n))
          (= n 0) y
          (even? n) (recur y (* x x) (/ n 2))
          (odd? n) (recur (* x y) (* x x) (/ (- n 1) 2)))))

euler

0.1.0-SNAPSHOT