;; (debug (parse-integer (apply str (reverse (format "%d" x)))))

(parse-integer (apply str (reverse (format "%d" x)))))

+;; (debug (format "%d" x))

+;; (debug (reverse (format "%d" x)))

+;; (debug (apply str (reverse (format "%d" x))))

+;; (debug (parse-integer (apply str (reverse (format "%d" x)))))

+ (parse-big-integer (apply str (reverse (format "%d" x)))))

(63 66 4 68 89 53 67 30 73 16 69 87 40 31)

( 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23)

-;; NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

+;; NOTE: As there are only 16384 routes, it is possible to solve this

+;; problem by trying every route. However, Problem 67, is the same

+;; challenge with a triangle containing one-hundred rows; it cannot be

+;; solved by brute force, and requires a clever method! ;o)

(defn path-helper [accum triangle]

;; Euler published the remarkable quadratic formula:

;; 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.

-;; Using computers, the incredible formula n� - 79n + 1601 was discovered

+;; 41² + 41 + 41 is clearly divisible by 41.

+;; Using computers, 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

+;; 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

;{{{ problem 31 -- currency

-;; In England the currency is made up of pound, ~~�~~, and pence, p, and

+;; 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).

+;; 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

(def denominations '(200 100 50 20 10 5 2 1))

-;; It is possible to make �2 in the following way:

-;; 1�1 + 150p + 220p + 15p + 12p + 31p

-;; How many different ways can �2 be made using any number of coins?

+;; It is possible to make £2 in the following way:

+;; 1£1 + 150p + 220p + 15p + 12p + 31p

+;; How many different ways can £2 be made using any number of coins?

(defn coins [value denominations]

;; (println value denominations (range (inc (/ value (first denominations)))))

;{{{ problem 42 -- triangle words

;; The nth term of the sequence of triangle numbers is given by, tn =

-;; ~~�~~n(n+1); so the first ten triangle numbers are:

+;; ½n(n+1); so the first ten triangle numbers are:

;; 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

(let [digits (to-digits n)]

- (rem (~~big-~~parse-integer (apply str (take 3 (nthrest digits x)))) p))

+ (rem (parse-big-integer (apply str (take 3 (nthrest digits x)))) p))

(filter substring-divisible?

- (map #(~~big-~~parse-integer (apply str %))

+ (map #(parse-big-integer (apply str %))

(drop (factorial 9) ;The first 9! are too small

(permutations "0123456789"))))))

(and (not (zero? (first seq)))

-;; (prn x p (big-parse-integer (apply str (take 3 (nthrest seq x)))) (rem (big-parse-integer (apply str (take 3 (nthrest seq x)))) p))

- (rem (big-parse-integer (apply str (take 3 (nthrest seq x)))) p))

+;; (prn x p (parse-big-integer (apply str (take 3 (nthrest seq x)))) (rem (parse-big-integer (apply str (take 3 (nthrest seq x)))) p))

+ (rem (parse-big-integer (apply str (take 3 (nthrest seq x)))) p))

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

-;{{{ problem 51 -- prime replace gives prime

+;{{{ problem 51 -- prime replace gives prime *

;; By replacing the 1st digit of *57, it turns out that six of the

;; possible values: 157, 257, 457, 557, 757, and 857, are all prime.

;; Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x

;; and 6x, contain the same digits.

+(defn have-same-digits? [n]

+ (apply = (map #(sort (to-digits (* n %))) (range 2 7))))

+(defn find-same-digits []

+ (filter have-same-digits? (iterate inc 1))))

;{{{ problem 52 -- n Choose r > 1 M

;; How many, not necessarily distinct, values of nCr, for 1 n 100, are

;; greater than one-million?

+(defn big-chooses [x min]

+ (count (filter #(> % min)

+ (for [n (range 1 (inc x))

+;; (big-chooses 100 1000000)

;{{{ problem 54 -- poker hands

;; Straight Flush: All cards are consecutive values of same suit.

;; Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

+(defn high-card-compare [p1 p2]

+ (. (high-card p1) (compareTo (high-card p2))))

+ (= 1 (count (distinct (map frest hand)))))

+ (let [h (high-card hand)]

+ (= (reverse (map first hand))

+ (range (- h 4) (inc h)))))

+(defn straight-flush? [hand]

+(defn royal-flush? [hand]

+ (and (straight-flush? hand)

+ (= 14 (high-card hand))))

+ (reverse (sort-by frest ;; TODO: ensure this is a stable sort

+ (reverse (run-length-encode (map first hand))))))

+ (map frest (get-tuples hand))))

+(defn high-tuple-card-compare [p1 p2]

+ (let [h1 (map first (get-tuples p1))

+ h2 (map first (get-tuples p2))]

+ (first (filter (complement zero?)

+ (map (fn [x y] (. x (compareTo y)))

+(defn poker-compare [p1 p2]

+ (cond (royal-flush? p1)

+ (if (royal-flush? p2) 0 1) ;this would be a tie and we are guaranteed none

+ (if (straight-flush? p2) (high-card-compare p1 p2) 1)

+ (if (= '(4) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (= '(3 2) (num-same p1))

+ (if (= '(3 2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (= '(3 2) (num-same p2))

+ (if (flush? p2) (high-card-compare p1 p2) 1)

+ (if (straight? p2) (high-card-compare p1 p2) 1)

+ (if (= '(3) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (= '(2 2) (num-same p1))

+ (if (= '(2 2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (= '(2 2) (num-same p2))

+ (if (= '(3) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (if (= '(2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)

+ (high-card-compare p1 p2)))

;; The cards are valued in the order:

;; 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

;; Consider the following five hands dealt to two players:

-;; Hand Player 1 Player 2 Winner

+;; Hand Player 1 Player 2 Winner

;; The file, poker.txt, contains one-thousand random hands dealt to

;; two players. Each line of the file contains ten cards (separated by

;; How many hands does Player 1 win?

+;; Cards will look like '(num suit)

+ ;; The cards are valued in the order:

+ ;; 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

+ (list (cond (= num \T) 10

+ :else (parse-integer (str num)))

+(defn parse-poker-line [line]

+ (map parse-card (re-seq #"[^ ]+" line)))

+ (count (filter #(= % 1)

+ (for [l (file-lines file)]

+ (let [cards (parse-poker-line l)

+ player1 (reverse (sort-by first (take 5 cards)))

+ player2 (reverse (sort-by first (nthrest cards 5)))]

+;; (list player1 player2 (poker-compare player1 player2))

+ (poker-compare player1 player2)

;{{{ problem 55 -- Lychrel numbers

;; NOTE: Wording was modified slightly on 24 April 2007 to emphasise

;; the theoretical nature of Lychrel numbers.

+ (cond (> iterations 50)

+ (recur (+ n (num-reverse n)) (inc iterations))))

+ (+ n (num-reverse n)) 0))

+(defn how-many-lychrels [n]

+ (count (filter lychrel? (range 0 n))))

+;; (how-many-lychrels 10000)

;{{{ problem 56 -- digital sums of powers

;; Considering natural numbers of the form, a^b, where a, b < 100, what

;; is the maximum digital sum?

+(defn digital-sums-of-powers [n]

+ (reduce max (for [a (range 1 n)

+ (sum-of-digits (big-integer-pow a b)))))

+;; (digital-sums-of-powers 100)

;{{{ problem 57 -- continued fractions

;; In the first one-thousand expansions, how many fractions contain a

;; numerator with more digits than denominator?

+(defn continued-fractions [x limit accum]

+ (let [next-n (inc (/ (inc x)))

+ next-accum (if (> (count (to-digits (. x numerator)))

+ (count (to-digits (. x denominator))))

+ (recur next-n (dec limit) next-accum))))

+;; (continued-fractions 3/2 1000 0)

;{{{ problem 58 -- prime spiral arms

;; continued, what is the side length of the square spiral for which

;; the ratio of primes along both diagonals first falls below 10%?

+;; We have 1, +2,+2,+2,+2, +4,+4,+4,+4, etc.

+ (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]

+ (lazy-cat (map #(+ cur (* amt %)) (range 1 5))

+ (this (nth new-seq 3) (+ 2 amt)))))

+ (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]

+ (lazy-cons (map #(+ cur (* amt %)) (range 1 5))

+ (this (nth new-seq 3) (+ 2 amt)))))

+ (map (fn [diags len cnt]

+ (list (count (filter isprime? (distinct diags))) len cnt)) ;(if (isprime? d) 1 0)

+ (iterate #(+ 4 %) 1))))

+(defn find-spiral-prime-ratio [ratio]

+ ((fn this[diags primes cnt len]

+ (let [cur-primes (+ primes (count (filter isprime? (first diags))))

+ (if (< (/ cur-primes cur-cnt) ratio)

+ (recur (rest diags) cur-primes cur-cnt cur-len))))

+ (drop 1 spiral-diagonals) 0 1 1))

+;; (find-spiral-prime-ratio 1/10)

;{{{ problem 59 -- encryption

;; English words, decrypt the message and find the sum of the ASCII

;; values in the original text.

+ ([a b] (if (< (frest a) (frest b)) b a)))

+ (let [rle (run-length-encode (sort seq))

+ most-popular (first (reduce max-frest rle))]

+ (bit-xor most-popular (int \space )))) ; All too easy -- didn't really solve the problem though...

+(defn map-no-exhaust [f & seqs]

+ (lazy-cons (apply f (map first seqs))

+ (if (every? nil? (map first seqs))

+ (apply map-no-exhaust f (map rest seqs)))))

+(defn decipher-xor [file n]

+ (let [numbers (re-seq #"\d+" (slurp file))]

+ (apply map-no-exhaust str ; This doesn't find all the input since it only uses sequences while they all have data

+ (let [stream (map parse-integer (take-nth n (drop x numbers)))

+ (map #(char (bit-xor key %)) stream)))))))

+;; (reduce + (map int (decipher-xor "cipher1.txt" 3)))

-;{{{ problem 60 -- prime concatenation

+;{{{ problem 60 -- prime concatenation *

;; The primes 3, 7, 109, and 673, are quite remarkable. By taking any

;; two primes and concatenating them in any order the result will

;; Find the lowest sum for a set of five primes for which any two

;; primes concatenate to produce another prime.

+(def primes-concatenated {})

+(defn prime-concatenation [n]

+ (let [primes-concatenated {}]

+ (for [p1 (primes-below n)

+ p2 (primes-below p1) :when (and (isprime? (int-concat p1 p2))

+ (isprime? (int-concat p2 p1)))]

+ (update-in primes-concatenated [p1]

+ (update-in primes-concatenated [p2]

+ (update-in primes-concatenated [p1]

+;{{{ problem 61 -- cyclic figurate numbers *

+;; Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal

+;; numbers are all figurate (polygonal) numbers and are generated by

+;; the following formulae:

+;; Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...

+;; Square P4,n=n^2 1, 4, 9, 16, 25, ...

+;; Pentagonal P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ...

+;; Hexagonal P6,n=n(2n-1) 1, 6, 15, 28, 45, ...

+;; Heptagonal P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ...

+;; Octagonal P8,n=n(3n-2) 1, 8, 21, 40, 65, ...

+;; The ordered set of three 4-digit numbers: 8128, 2882, 8281, has

+;; three interesting properties.

+;; The set is cyclic, in that the last two digits of each number is

+;; the first two digits of the next number (including the last number

+;; Each polygonal type: triangle (P3,127=8128), square (P4,91=8281)

+;; and pentagonal (P5,44=2882), is represented by a different number

+;; This is the only set of 4-digit numbers with this property.

+;; Find the sum of the only ordered set of six cyclic 4-digit numbers

+;; for which each polygonal type: triangle, square, pentagonal

+;; hexagonal, heptagonal, and octagonal, is represented by a different

+;{{{ problem 62 -- permuting cubes

+;; The cube, 41063625 (345^3), can be permuted to produce two other

+;; cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is

+;; the smallest cube which has exactly three permutations of its

+;; digits which are also cube.

+;; Find the smallest cube for which exactly five permutations of its digits are cube.

+(defn permutations-with-repeats [seq]

+ (apply concat (for [x (distinct seq)]

+ (let [tail (filter #(not= x %) seq)

+ repeats (dec (count (filter #(= x %) seq)))

+ real-tail (concat tail (take repeats (repeat x)))]

+;; (prn 'repeats repeats 'real-tail real-tail 'tail tail 'perm (permutations-with-repeats tail))

+ (permutations-with-repeats real-tail))))))))

+(def cubes (map #(* % % %) (iterate inc 1)))

+ (let [x (Math/round (Math/pow n 1/3))]

+(defn num-permuted-cubes [n]

+ (prn 'num-permuted-cubes n)

+ (count (filter #(and (>= % n) (cube? %))

+ (map #(apply int-concat %)

+ (permutations-with-repeats (to-digits n))))))

+(defn smallest-permutable-cube [n]

+ (first (filter #(= n (num-permuted-cubes %))

+(defn smallest-permutable [limit seq]

+ sorted-digits (sort (to-digits n))

+ new-map (update-in m [sorted-digits] #(cons n %))]

+ (if (and (= limit (count (new-map sorted-digits)))

+;; (= 1 (num-permuted-cubes n)) ;; just to make sure it's exactly 5... (because this only counts those >= self)

+ (reduce min (new-map sorted-digits)) ;; This isn't actually the smallest

+ (recur new-map (rest seq)))))

+;; (smallest-permutable 5 cubes)

+;{{{ problem 63 -- n-digit n-th powers

+;; The 5-digit number, 16807=7^5, is also a fifth power. Similarly

+;; the 9-digit number, 134217728=8^9, is a ninth power.

+;; How many n-digit positive integers exist which are also an nth power?

+(defn n-digit-nth-powers-of [n]

+ ((fn this [n power num-digits accum]

+;; (prn n power num-digits (count accum))

+ (cond (= num-digits (count (to-digits power)))

+ (recur n (* n power) (inc num-digits) (cons power accum))

+;; (< num-digits (count (to-digits power)))

+;; (recur n (* n power) (inc num-digits) accum)

+;; TODO: maybe I should make a map from sorted digits of cubes and

+;; check everytime to see if there are 5, etc.

+(defn num-n-digit-nth-powers []

+ (count (distinct (mapcat n-digit-nth-powers-of (range 1 10)))))

+;; (num-n-digit-nth-powers)

+;{{{ problem 64 -- periods of continued fractions *

+;; All square roots are periodic when written as continued fractions

+;; and can be written in the form:

+;; For example, let us consider 23:

+;; 23 = 4 + 23 - 4 = 4 +

+;; If we continue we would get the following expansion:

+;; The process can be summarised as follows:

+;; It can be seen that the sequence is repeating. For conciseness, we

+;; use the notation 23 = [4;(1,3,1,8)], to indicate that the block

+;; (1,3,1,8) repeats indefinitely.

+;; The first ten continued fraction representations of (irrational) square roots are:

+;; 3=[1;(1,2)], period=2

+;; 6=[2;(2,4)], period=2

+;; 7=[2;(1,1,1,4)], period=4

+;; 8=[2;(1,4)], period=2

+;; 11=[3;(3,6)], period=2

+;; 12= [3;(2,6)], period=2

+;; 13=[3;(1,1,1,1,6)], period=5

+;; Exactly four continued fractions, for N 13, have an odd period.

+;; How many continued fractions for N 10000 have an odd period?

+;{{{ problem 65 -- continued fractions for e

+;; The square root of 2 can be written as an infinite continued fraction.

+;; The infinite continued fraction can be written, 2 = [1;(2)], (2)

+;; indicates that 2 repeats ad infinitum. In a similar way, sqrt(23) =

+;; It turns out that the sequence of partial values of continued

+;; fractions for square roots provide the best rational

+;; approximations. Let us consider the convergents for 2.

+;; Hence the sequence of the first ten convergents for sqrt(2) are:

+;; 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

+;; What is most surprising is that the important mathematical constant

+;; e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

+;; The first ten terms in the sequence of convergents for e are:

+;; 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

+;; The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

+;; Find the sum of digits in the numerator of the 100th convergent of

+;; the continued fraction for e.

+(def continued-fraction-e

+(defn continued-fraction-nth-convergent [seq limit]

+ (/ ((fn this[seq accum]

+ (recur (rest seq) (/ (+ (first seq) accum)))

+ (reverse (take limit seq)) 0)))

+(defn nth-e-convergent [n]

+ (sum-of-digits (. (continued-fraction-nth-convergent continued-fraction-e n) numerator)))

+;; (nth-e-convergent 100)

+;{{{ problem 66 -- Diaphontine equations *

+;; Consider quadratic Diophantine equations of the form:

+;; For example, when D=13, the minimal solution in x is 6492 - 131802 = 1.

+;; It can be assumed that there are no solutions in positive integers

+;; By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we

+;; obtain the following:

+;; Hence, by considering minimal solutions in x for D <= 7, the largest x

+;; is obtained when D=5.

+;; Find the value of D <= 1000 in minimal solutions of x for which the

+;; largest value of x is obtained.

+;{{{ problem 67 -- more triangle path maximizing

+;; By starting at the top of the triangle below and moving to adjacent

+;; numbers on the row below, the maximum total from top to bottom is

+;; That is, 3 + 7 + 4 + 9 = 23.

+;; Find the maximum total from top to bottom in triangle.txt (right

+;; click and 'Save Link/Target As...'), a 15K text file containing a

+;; triangle with one-hundred rows.

+;; NOTE: This is a much more difficult version of Problem 18. It is

+;; not possible to try every route to solve this problem, as there are

+;; 299 altogether! If you could check one trillion (1012) routes every

+;; second it would take over twenty billion years to check them

+;; all. There is an efficient algorithm to solve it. ;o)

+(defn path-maximizer [file]

+ (map #(map parse-integer (re-seq #"\d+" %))

+;; (path-maximizer "triangle.txt")

+;{{{ problem 68 -- magic n-gons *

+;; Consider the following "magic" 3-gon ring, filled with the numbers

+;; 1 to 6, and each line adding to nine.

+;; Working clockwise, and starting from the group of three with the

+;; numerically lowest external node (4,3,2 in this example), each

+;; solution can be described uniquely. For example, the above solution

+;; can be described by the set: 4,3,2; 6,2,1; 5,1,3.

+;; It is possible to complete the ring with four different totals: 9

+;; 10, 11, and 12. There are eight solutions in total.

+;; 9 4,2,3; 5,3,1; 6,1,2

+;; 9 4,3,2; 6,2,1; 5,1,3

+;; 10 2,3,5; 4,5,1; 6,1,3

+;; 10 2,5,3; 6,3,1; 4,1,5

+;; 11 1,4,6; 3,6,2; 5,2,4

+;; 11 1,6,4; 5,4,2; 3,2,6

+;; 12 1,5,6; 2,6,4; 3,4,5

+;; 12 1,6,5; 3,5,4; 2,4,6

+;; By concatenating each group it is possible to form 9-digit strings;

+;; the maximum string for a 3-gon ring is 432621513.

+;; Using the numbers 1 to 10, and depending on arrangements, it is

+;; possible to form 16- and 17-digit strings. What is the maximum

+;; 16-digit string for a "magic" 5-gon ring?

+;{{{ problem 69 -- totient *

+;; Euler's Totient function, φ(n) [sometimes called the phi function]

+;; is used to determine the number of numbers less than n which are

+;; relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are

+;; all less than nine and relatively prime to nine, φ(9)=6.

+;; n Relatively Prime φ(n) n/φ(n)

+;; 7 1,2,3,4,5,6 6 1.1666...

+;; It can be seen that n=6 produces a maximum n/φ(n) for n <= 10.

+;; Find the value of n <= 1,000,000 for which n/φ(n) is a maximum.

+(defn totient [n] ; TODO: this isn't quite right... I have to take repeated factors into account

+ (reduce * (map #(- % 1) (factors n))))

+;{{{ problem 70 -- totient *

+;; Euler's Totient function, φ(n) [sometimes called the phi function]

+;; is used to determine the number of positive numbers less than or

+;; equal to n which are relatively prime to n. For example, as 1, 2

+;; 4, 5, 7, and 8, are all less than nine and relatively prime to

+;; The number 1 is considered to be relatively prime to every positive

+;; Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

+;; Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

+;; (map #(list % (totient %))