This site contains all problems from Project Euler at 20. April 2015. It was initially generated by using the following command:
curl https://projecteuler.net/show=all | pandoc -f html -t org -o project-euler.orgBefore starting this project I had about 50 solutions to Project Euler problems. None of these solutions will appear here.
I have no ambition to solve them all, not even past the 50 I’ve already solved. It is just as much a project in multilingual literate programming.
The document is written in Emacs, using Org mode, and it’s Babel feature for executing and extracting source code.
The language I’ll be using the most is Clojure. We need a project.clj
file in order to use Leiningen. This is it’s content:
I’ll use a number of Clojure libraries, and they are required here.
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.
Find the sum of all the multiples of 3 or 5 below 1000.
This is easily solved in almost any programming language; we’ll do it in Clojure. We start by generating a list of the 1000 first natural numbers, filter the list so that it only contains multiples of 3 and 5, and finally add them all together.
(->> (range 1000)
(filter #(or (zero? (mod % 3))
(zero? (mod % 5))))
(apply +))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, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
The first expression generates all Fibonacci numbers given a vector
containing [1 2]. The function given to iterate will produce vectors on
the form ([1 2] [2 3] [3 5] ...). We grab the first element of each
vector (giving the Fibonacci sequence) and filter the sequence so that it
only contains even numbers. By using take-while we terminate the
sequence when a
(->> (iterate (fn [[a b]] [b (+ a b)]) [1 2])
(map first)
(filter even?)
(take-while #(< % 4000000))
(apply +))The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
From the problem description we can see that
\[ \frac{13195}{13195} = \frac{13195}{5 ⋅ 2639} = \frac{13195}{5 ⋅ 7 ⋅ 377} = \frac{13195}{5 ⋅ 7 ⋅ 13 ⋅ 29} = 1 \]
These numbers are retrievable by dividing with 2 as long as the number is even, then 3 for however long the result is divisible by 3, and so on. Most numbers won’t divide, so we’ll quickly discard them.
This recursive function gives us the larges prime factor of a given
number n. If we were to do recursive calls to largest-prime-factor we
would eat up the stack space, but we avoid this by using the keyword
recur (which results in a loop).
Now we apply it to 600851475143.
(largest-prime-factor 600851475143)A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
First, we need to be able to tell if a number is a palindrome or not.
Now we just need to brute-force. Using for, a sequence of products are
generated, this sequence is then sorted (in descending order). Then we
can pull out the first palindrome. One would think it would be faster to
maximize than to sort the entire collection, but in Clojure it turns out
not to be the case.
(->> (for [n (range 999 100 -1)
m (range n 100 -1)] (* m n))
(sort #(- %2 %))
(filter palindrome?)
(first))2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
A brute-force solution is to check divisibility from 1 to 20 for all natural numbers until we find one that has this property.
But, as we can see, this is not really a good solution (it took almost two minutes).
"Elapsed time: 90901.989396 msecs" 232792560
I have to admit, I have no idea why this next one works. I remember learning Common Lisp and tackling this problem. I thought I’d just found the first non-brutable Project Euler problem, but I probably just had some faulty code. So I worked intensely with the problem, reading articles about prime factorization, and understanding this could be used to solve the problem.
This is a rewrite of the code I wrote in Common Lisp, which contained some truly horrible stuff, in about a fourth of it’s size. It’s wicked fast!
"Elapsed time: 0.333856 msecs" 232792560
To give an idea of how much more efficient this is, we can solve the
problem for 20000 instead of 20. We have to change the 2 to 2N, so
that we get a BigInt, in order to handle the ridiculous size of the
result.
"Elapsed time: 580.887896 msecs" 57933396702876429686922708791662400986348602979985188253931383511489793001457731823088325981761829221665744176794023407056559491402467891577328326763021299466843118474637852656831938521549472347971073068161679301705472685236926463387338495220571064420250677315000599457941340849496227227628926493771018264821842230370349640102573492881424317306189569467101495834601991270039918780924506495405797923762205360790652073159333382795670426041033566699342449050309786673681670483369155689567554239898879039744147333971988258061042090970476729293484513072443614795766878726325795854855394491290821167148355514749149683707585283381546153703014210442470318180511906691108325146494219343498899382918018246586609827667470329166012110874981104800415741527586280026737848182673635645872230905234515169611121042867043956727839314198728626274066655467846183343599194761590368608472578398169740111485924046986870714883894285841394964627408094161019230662749101230783008668676907211199488107523306410531772045452853957706873238466829988649822157557103503283563398281775464911904789159515900987401574678885942493907604740891878907698622679570965569483682456042918236444719794534411171907606336090534029349351300276141892529795448751826394399153216183270385737795748770508612096374765333578237973395907265484337502903901947799663388329849198045756207969590055686607678195206367273600632909417024224754750428711236917913663419215925830944035539848749163178489614227546656090790164108195741048033614368495827231281392190063051315248070192263400801315095608512139510731469732311313898995746040563433121427776071482655904346538281010668476731132415829844984600414136781404774213539507859790229205890271721600309169926806121871750008163738773911610009508609149665332579632767397078877996926581337419351834754370411008686136818501030862345505385357198060894463821342298717851567836562984344806469613768024764967372979655179066074398198246805104576134474823016488842818077041661676098399378809713894284994865370648616800689225595431967181072865363430005250840767890912164530705704936837915584856606960687347372391339254432119085932175541392954343684716695162629271229789289404752104218596977036941910521266321726821940533986384237994403780618301379099347975260122724194454275088825587044488208965690373706904056926509324696308810974331790119456438147168585552011926921912167450509941646104076818762060881903969616431646384985895944231218505620547093874241169759205450145478746112796898626711966320965057212219958567338851356631739947125096250452942497473309299907612330435197454392788637359253116308685007014249605492659524429134513344137517101872279428202285951652856354827230765931502805341696470148698002737700823078904634554776750169178259216255903968865588749827789888950172452455448248833712309835657561369233157977405579365293671943131412034109901944892819245001657496671822581274180596255340507054499934060282320458240722454209933569735940032859109934686878274110864394924463573852015338428881961843292083566034669814619612606638283615766521897504566616272305253931938372830446073384019299355320864342734019517633662346790422915951954822645137091494126100390104510987373366328615363056042137440808225973600809566845718073791616927784260557845021823094999326904373592319407516660896764388092262510369182153559285446074990941863516247226532653142198551840063631989428776799533286215464660644129411503287306838551341184739976807097763115368031748646043780549055143428297230678053738453010234949008253769355207208167999203353157524666017029803679612131824740794652592875662818479980117505768541194835524231818203552256426752730455115752280837099763237606348192867936457993970866446264015812819179994138642295108872381709181937092290392544335464025324661284746003660247161196698209062164637264114930766444473471083408200329662059064201896721165015687487728300854501780810155844837489798144309942999091774466406270065305461848242329380636274754660519867343112275861821293501112101434868225378041813836808745417606289159904294165941408692922250601127804971962342807927743390030395048263275616935165347620718001157478088456439083590834464409622781693790883289597024043982584220069224170235863458745344365684082114430362867446193601075569803650773018026700003812298460527976219100308016537538008597751565631582745643139434508332515569645426771932483266712323523039014220800000N
This is a 4349 digit integer, that is divisible by every integer from 1 to 10000, calculated in half a second.
The sum of the squares of the first ten natural numbers is,
12 + 22 + … + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)2 = 552 = 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.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
This is quite straight forward to brute force.
(let [nums (range 1 101)
sumsqr (apply + (map #(* % %) nums))
sqrsum (#(* % %) (apply + nums))]
(- sqrsum sumsqr))By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
A sieve function takes a sequence of primes and an integer, and checks whether or not it is divisible by any of the primes. If not, let the primes remain untouched, else add it to the sequence of primes.
A neat function Clojure’s library is reductions, which gives you each
step of an reduction. So (reductions conj [] [1 2 3]) evaluates to
([] [1] [1 2] [1 2 3]). So by looking at each reduction, and looking at
the last element in the sequence, we see the largest prime calculated so
far. Making this reduction sequence distinct allows us to search for the
nth prime.
Sadly, but not unexpectedly, it’s quite slow.
"Elapsed time: 4533.628391 msecs" 104009
Let’s do better. By looking at the all the numbers from 2 to
prime? predicate that does just this, and find the 10001st
prime.
"Elapsed time: 1113.549649 msecs" 104743
Here we’ve lost the benefit of only looking at other primes. Let’s remedy this by writing a function that lazily generates all primes.
(-> (primes) (nth 10000) time)The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450\
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
partition is a super-sweet function that takes one argument to indicate
the size of each partition, and an optional second integer argument that
indicates the step (the default is the same of the partition-size). By
partitioning the sequence of numbers to sequences of length 13, and only
make a single step, we can simply take the product of each partition, and
maximize.
(->> [7 3 1 6 7 1 7 6 5 3 1 3 3 0 6 2 4 9 1 9 2 2 5 1 1 9 6 7 4 4 2 6 5 7 4 7 4 2 3 5 5 3 4 9 1 9 4 9 3 4 9 6 9 8 3 5 2 0 3 1 2 7 7 4 5 0 6 3 2 6 2 3 9 5 7 8 3 1 8 0 1 6 9 8 4 8 0 1 8 6 9 4 7 8 8 5 1 8 4 3 8 5 8 6 1 5 6 0 7 8 9 1 1 2 9 4 9 4 9 5 4 5 9 5 0 1 7 3 7 9 5 8 3 3 1 9 5 2 8 5 3 2 0 8 8 0 5 5 1 1 1 2 5 4 0 6 9 8 7 4 7 1 5 8 5 2 3 8 6 3 0 5 0 7 1 5 6 9 3 2 9 0 9 6 3 2 9 5 2 2 7 4 4 3 0 4 3 5 5 7 6 6 8 9 6 6 4 8 9 5 0 4 4 5 2 4 4 5 2 3 1 6 1 7 3 1 8 5 6 4 0 3 0 9 8 7 1 1 1 2 1 7 2 2 3 8 3 1 1 3 6 2 2 2 9 8 9 3 4 2 3 3 8 0 3 0 8 1 3 5 3 3 6 2 7 6 6 1 4 2 8 2 8 0 6 4 4 4 4 8 6 6 4 5 2 3 8 7 4 9 3 0 3 5 8 9 0 7 2 9 6 2 9 0 4 9 1 5 6 0 4 4 0 7 7 2 3 9 0 7 1 3 8 1 0 5 1 5 8 5 9 3 0 7 9 6 0 8 6 6 7 0 1 7 2 4 2 7 1 2 1 8 8 3 9 9 8 7 9 7 9 0 8 7 9 2 2 7 4 9 2 1 9 0 1 6 9 9 7 2 0 8 8 8 0 9 3 7 7 6 6 5 7 2 7 3 3 3 0 0 1 0 5 3 3 6 7 8 8 1 2 2 0 2 3 5 4 2 1 8 0 9 7 5 1 2 5 4 5 4 0 5 9 4 7 5 2 2 4 3 5 2 5 8 4 9 0 7 7 1 1 6 7 0 5 5 6 0 1 3 6 0 4 8 3 9 5 8 6 4 4 6 7 0 6 3 2 4 4 1 5 7 2 2 1 5 5 3 9 7 5 3 6 9 7 8 1 7 9 7 7 8 4 6 1 7 4 0 6 4 9 5 5 1 4 9 2 9 0 8 6 2 5 6 9 3 2 1 9 7 8 4 6 8 6 2 2 4 8 2 8 3 9 7 2 2 4 1 3 7 5 6 5 7 0 5 6 0 5 7 4 9 0 2 6 1 4 0 7 9 7 2 9 6 8 6 5 2 4 1 4 5 3 5 1 0 0 4 7 4 8 2 1 6 6 3 7 0 4 8 4 4 0 3 1 9 9 8 9 0 0 0 8 8 9 5 2 4 3 4 5 0 6 5 8 5 4 1 2 2 7 5 8 8 6 6 6 8 8 1 1 6 4 2 7 1 7 1 4 7 9 9 2 4 4 4 2 9 2 8 2 3 0 8 6 3 4 6 5 6 7 4 8 1 3 9 1 9 1 2 3 1 6 2 8 2 4 5 8 6 1 7 8 6 6 4 5 8 3 5 9 1 2 4 5 6 6 5 2 9 4 7 6 5 4 5 6 8 2 8 4 8 9 1 2 8 8 3 1 4 2 6 0 7 6 9 0 0 4 2 2 4 2 1 9 0 2 2 6 7 1 0 5 5 6 2 6 3 2 1 1 1 1 1 0 9 3 7 0 5 4 4 2 1 7 5 0 6 9 4 1 6 5 8 9 6 0 4 0 8 0 7 1 9 8 4 0 3 8 5 0 9 6 2 4 5 5 4 4 4 3 6 2 9 8 1 2 3 0 9 8 7 8 7 9 9 2 7 2 4 4 2 8 4 9 0 9 1 8 8 8 4 5 8 0 1 5 6 1 6 6 0 9 7 9 1 9 1 3 3 8 7 5 4 9 9 2 0 0 5 2 4 0 6 3 6 8 9 9 1 2 5 6 0 7 1 7 6 0 6 0 5 8 8 6 1 1 6 4 6 7 1 0 9 4 0 5 0 7 7 5 4 1 0 0 2 2 5 6 9 8 3 1 5 5 2 0 0 0 5 5 9 3 5 7 2 9 7 2 5 7 1 6 3 6 2 6 9 5 6 1 8 8 2 6 7 0 4 2 8 2 5 2 4 8 3 6 0 0 8 2 3 2 5 7 5 3 0 4 2 0 7 5 2 9 6 3 4 5 0]
(partition 13 1)
(map #(apply * %))
(apply max))A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
A naive solution would be to loop for 0 < a < 1000, 0 < b < 1000 and 0 < c < 1000, and check that the equations hold. This has a worst case of testing 1000^3 = 10^9 different values for a, b and c. Looping through 10^9 numbers takes a little less than two minutes on my machine, so we’d probably have to wait a while for an answer. By using the assumption that a < b < c, we get it down to 10^8, which takes about 15 seconds to loop through on my machine.
An approach like this could look like so.
But we have two equations and three unknowns, so we should get by knowing two of the unknowns. From the two equations we can derive that
This means we can loop through 1 < a < 1000 and a < b < 1000, which takes us down to less than 10^6 operations, which can be looped through in less than 100 milliseconds.
(->> (for [a (range 1 1000)
b (range a 1000)
:when (= (+ a b (Math/sqrt (+ (* a a) (* b b))))
1000.0)]
(* a b (Math/sqrt (+ (* a a) (* b b)))))
(first)
(int))The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Knowing that the prime can’t exceed two million makes our sieve function
more useful, seeing that we can use reduce over the natural numbers
between two and two million. Leaving the sieve function untouched, we
can calculate the sum in about 10 seconds.
"Elapsed time: 11168.613766 msecs" 142913828922
We could also use the primes function, which has pretty much the same
performance.
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
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\
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
The first solution I was able to hack out was this fairly ugly one.
(let [nums [8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3 49 13 36 65 52 70 95 23 4 60 11 42 69 24 68 56 1 32 56 71 37 2 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 3 45 2 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 2 62 12 20 95 63 94 39 63 8 40 91 66 49 94 21 24 55 58 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 9 75 0 76 44 20 45 35 14 0 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 3 80 4 62 16 14 9 53 56 92 16 39 5 42 96 35 31 47 55 58 88 24 0 17 54 24 36 29 85 57 86 56 0 48 35 71 89 7 5 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 5 94 47 69 28 73 92 13 86 52 17 77 4 89 55 40 4 52 8 83 97 35 99 16 7 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 3 46 33 67 46 55 12 32 63 93 53 69 4 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 4 36 16 20 73 35 29 78 31 90 1 74 31 49 71 48 86 81 16 23 57 5 54 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48]
adj 4
row 20
matrix (partition row nums)
horizontals matrix
verticals (->> (for [i (range row)]
(map #(nth % i) matrix)))
ltr-diagonals (concat (->> (for [i (range (- row (dec adj)))]
(->> (drop i nums)
(take-nth (inc row))
(take (- row i)))))
(->> (for [i (range row (* row (- row (dec adj))) row)]
(->> (drop i nums)
(take-nth (inc row))))))
rtl-diagonals (concat (->> (for [i (range (dec adj) row)]
(->> (drop i nums)
(take-nth (dec row))
(take (- row (- (dec row) i))))))
(->> (for [i (range (dec row) (* row (- row (dec adj))) row)]
(->> (drop i nums)
(take-nth (dec row))))))]
(->> [horizontals verticals ltr-diagonals rtl-diagonals]
(map #(mapcat (partial partition adj 1) %))
(map #(map (partial apply *) %))
(flatten)
(apply max)))This is a more verbose variant, that does essentially the same.
(defn horizontal-within-bound? [idx n dim]
(<= (mod idx dim) (- dim n)))
(defn vertical-within-bound? [idx n dim]
(<= (int (/ idx dim)) (- dim n)))
(defn diagonal-within-bound? [idx n dim]
(and (horizontal-within-bound? idx n dim)
(vertical-within-bound? idx n dim)))
(defn horizontals [idx n matrix]
(->> matrix (drop idx) (take n)))
(defn verticals [idx n dim matrix]
(->> matrix (drop idx) (take-nth dim) (take n)))
(defn ltr-diagonals [idx n dim matrix]
(->> matrix (drop idx) (take-nth (inc dim)) (take n)))
(defn rtl-diagonals [idx n dim matrix]
(->> matrix (drop (+ idx (dec n))) (take-nth (dec dim)) (take n)))
(let [matrix [8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3 49 13 36 65 52 70 95 23 4 60 11 42 69 24 68 56 1 32 56 71 37 2 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 3 45 2 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 2 62 12 20 95 63 94 39 63 8 40 91 66 49 94 21 24 55 58 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 9 75 0 76 44 20 45 35 14 0 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 3 80 4 62 16 14 9 53 56 92 16 39 5 42 96 35 31 47 55 58 88 24 0 17 54 24 36 29 85 57 86 56 0 48 35 71 89 7 5 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 5 94 47 69 28 73 92 13 86 52 17 77 4 89 55 40 4 52 8 83 97 35 99 16 7 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 3 46 33 67 46 55 12 32 63 93 53 69 4 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 4 36 16 20 73 35 29 78 31 90 1 74 31 49 71 48 86 81 16 23 57 5 54 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48]
n 4
dim 20
hs (for [i (range (* dim dim))
:when (horizontal-within-bound? i n dim)]
(horizontals i n matrix))
vs (for [i (range (* dim dim))
:when (vertical-within-bound? i n dim)]
(verticals i n dim matrix))
ltrs (for [i (range (* dim dim))
:when (diagonal-within-bound? i n dim)]
(ltr-diagonals i n dim matrix))
rtls (for [i (range (* dim dim))
:when (diagonal-within-bound? i n dim)]
(rtl-diagonals i n dim matrix))]
(->> [hs vs ltrs rtls]
(apply concat)
(map #(reduce * %))
(reduce max)))The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten 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.
What is the value of the first triangle number to have over five hundred divisors?
We can represent all the triangular numbers in a lazy list, by defining the recursively.
We don’t necessarily want to look at every triangular number, so we can use the fact that
\[ 1 + 2 + 3 +… + n = \frac{n (n + 1)}{2} \]
to be able to get every triangular from a given number
We need a function that can tell how many times a number divides another.
To count the divisors of a number
This is a general, but not very fast solution (about 3 seconds). The main bottleneck is checking a lot of primes, which are not generated all that fast (due to the non-optimal solution of problems 7 and 10).
76576500
We can greatly increase it’s performance by looking at fewer primes. Say we assume that the largest prime-factor is no more than 100, it runs very quickly and produces the correct answer.
The problem with the code above is that we’ve assumed something that we can’t (or at least I can’t) know before knowing the answer.
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
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\
This one is done in no time at all when you’re language has arbitrary-precision arithmetic!
(let [nums [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 ]]
(-> (apply + nums) (str) (subs 0 10) (read-string)))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 13, 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.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
First we implement a function that give us the next number in the Collatz sequence.
To get the sequence we just need to iterate collatz, but stop once we’ve
reached 1 (to ensure termination).
(defn collatz-seq [n]
(concat (take-while #(> % 1) (iterate collatz n)) [1]))Using the functions above, we end up with a very slow solution and takes about 3 minutes to run.
There is no reason to actually generate the sequences, so this is an obvious
optimization. In this problem there are a lot of duplicate function calls,
seeing that the function converges towards 1 (for instance will 3, 5, 6, 7
and 9 share the last five numbers of their Collatz sequence). So cashing
results should provide better performance; we can use memoize to achieve
this.
Running it once takes about 5 seconds, but after everything is cashed it runs in less than 2 seconds.
837799
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.
How many such routes are there through a 20×20 grid?
We could write a recursive function that calculates this, using memoization like above. Without memoization this takes an unreasonable amount of time (meaning I haven’t bother waiting for it to terminate).
Calling it takes about two milliseconds.
(lattice 20 20)But for this problem, we don’t really need a recursive function, we can
solve it analytically. Every lattice path of a
\[ \binom{40}{20} = \frac{40!}{20!(40-20)!} = \frac{40!}{20!20!} = \frac{40 ⋅ 39 \cdots 21} {20 ⋅ 19 \cdots 1} \]
(/ (apply *' (range 21 41))
(apply *' (range 1 21)))215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
As far as I can tell, Clojure has no built in exp function that returns a
bigint, so I wrote my own.
The easiest way I know to make a sequence out of a number is to convert it to a string, which is a sequence, and getting the numeric value of each character. After doing so we can simply sum the digits.
Now we can apply the functions to retrieve the answer.
(sum-digits (exp 2N 1000))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 in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
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.
Luckily, clojure.pprint has an implementation of Common Lisp’s excellent
function format, called cl-format. It allows us to get a number written
out in words using the format directive "~r". It, sadly, does not make use
of the word “and”, so we have to compensate for the ones missing.
Number between 1 and 99 will not contain the word “and”, and neither will
every hundredth word. So given
(let [n 1000
nums (range 1 (inc n))
format (s/join (repeat n "~r" ))
ands (* 3 (- n 99 (int (/ n 100))))]
(-> (apply (partial cl-format nil format) nums)
(s/replace #"[\W]" "")
(count)
(+ ands)))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 23.
3
7 4\
2 4 6\
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
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
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)
First we need to make a triangle, preferably from a sequence. What we want to do is to take one number, then two, but dropping the previous, then three but dropping the three previous and so forth. The number of numbers we need to drop happens to be the triangular numbers (which we examined in problem 12).
We can write a recursive function that, given a triangle, that traverses the triangle, and maximizes the path sum.
As indicated in the problem description, this is not a viable solution for a bigger triangle, but we’ll save the optimization for problem 67.
(let [rows 15
nums [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 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23]
triangle (seq->triangle rows nums)]
(maximum-path-sum triangle))You are given the following information, but you may prefer to do some research for yourself.
- 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.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
Instead of thinking even the slightest about this problem, we can use the clj-time library.
(->> (periodic-seq (date-time 1901 1 1)
(date-time 2000 12 31)
(months 1))
(filter sunday?)
(count))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.
Find the sum of the digits in the number 100!
The factorial function can easily be defined using reduce. Note that *'
is used in favor of * for arbitrary precision.
Now we can just reuse the sum-digits from problem 16.
(sum-digits (factorial 100))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.
Evaluate the sum of all the amicable numbers under 10000.
First we need to sum the proper divisors of a number
(Note that this is buggy, but it works here; it’s updated in problem 23)
It’s important to notice that we don’t really care about amicable pairs,
just amicable numbers. So checking all pairs is not at all necessary. Given
a number
Then we just need to gather up amicable numbers under 10000, and take the sum.
(apply + (for [a (range 1 10000) :when (amicable? a)] a))Using names.txt (right click and ‘Save Link/Target As…’), 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?
If we take a character and subtract the value we get from (dec \A), we
retrieve the alphabetical value. We can simply map over the string and sum
the values to get the string score.
Seeing that Clojure treats commas and newlines as white space, and every
name is a string, we can just place brackets around the content of the file
and read it to get a vector. After sorting this, we can use map-indexed
and multiply with the index (incremented by one) to get the name
score. Summing this gives us the correct answer!
(let [file (io/file (io/resource "names.txt"))]
(->> (str "[" (slurp file) "]")
(read-string) (sort)
(map-indexed (fn [i s] (* (inc i) (str-score s))))
(apply +)))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.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
This one gave me a lot of headache, mostly because I couldn’t make it
fast. The first problem was that the sum-divisors from problem 21 was
buggy. It did not handle square numbers, but this went unnoticed (because we
got the correct answer anyways). Here it’s rewritten, using reduce (which
doesn’t affect performance much), where the main difference lies in adding
the root, if the number is a perfect square.
Now, writing an abundant predicate is a piece of cake.
Now we can gather up the abundant sums and add these together, and subtract it from the sum we get from summing 1 to 28123 (which happens to be the 28123th triangular number).
4179871
This takes about 4 seconds to execute, which isn’t half bad (comparing with other Clojure solutions I’ve found after solving this), but it seems like there is room for optimization.
The main area I want to explore further is to avoid generating duplicate
sums, or at least make removing them less costly. sum-of-abundants has
12148815 elements, but only 26667 distinct ones, and this should not be
necessary.
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
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
First I found an algorithm for generating the next lexicographic permutation of a sequence on Wikipedia which is stated here.
- Find the largest index
ksuch thata[k]<a[k + 1]. If no such index exists, the permutation is the last permutation. - Find the largest index
lgreater thanksuch thata[k]<a[l]. - Swap the value of
a[k]with that ofa[l]. - Reverse the sequence from
a[k + 1]up to and including the final elementa[n].
This is a pretty direct translation of the description above. Note that it
crashes if you try to fetch the
We can simply iterate this function, feed it the sequence, and grab the 999999th permutation (because the original vector is not included in the result of iterate). It runs in a couple of seconds.
2783915460
But we can do better. We know that a sequence of size
Knowing this, we can place the 2 at the front of the sequence, and recursively apply this rule to the rest of the sequence.
Getting the millionth permutation runs in less that a millisecond!
(apply str (nth-permutation 1e6 [0 1 2 3 4 5 6 7 8 9]))The Fibonacci sequence is defined by the recurrence relation:
Fn = F/n/−1 + F/n/−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1\ F3 = 2\ F4 = 3\ F5 = 5\ F6 = 8\ F7 = 13\ F8 = 21\ F9 = 34\ F10 = 55\ F11 = 89\ F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
This is very similar to problem 2. We need to keep track of what term it is, so we should keep an index. For readability a map is used (to get named parameters), in favor of a vector.
To count the digits, my first thought was to use Math/log10, but it could
not handle number with more than 200 digits. So instead str is applied to
the large fibonacci number, and the characters are counted.
(->> (iterate (fn [{a :a b :b i :i}] {:a b :b (+ a b) :i (inc i)})
{:a 1N :b 2 :i 0})
(filter (fn [{a :a}] (-> a str count (> 1000)))) first :i)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/3 = 0.(3) \ 1/4 = 0.25 \ 1/5 = 0.2 \ 1/6 = 0.1(6) \ 1/7 = 0.(142857) \ 1/8 = 0.125 \ 1/9 = 0.(1) \ 1/10 = 0.1 \
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 value of
This is a function that counts the number of repeating decimals.
Primes produce the longest repeating cycles, so we can narrow the search down to only look at primes.
(->> (reduce sieve [2] (range 3 1001))
(map (fn [n] [n (repeating-decimals n)]))
(apply max-key second) first)Euler discovered the remarkable quadratic formula:
\[n^2 + 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^2 + 41 + 41 is clearly divisible by 41.
The incredible formula n^2 − 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^2 + an + b where |a| < 1000 and |b| < 1000
- where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4.
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.
This function takes coefficients a and b as arguments, and returns a
function that when given an n computes n^2 + an + b.
We’ll only look at primes (and their negatives), and maximize by the number
of consecutive primes a given a and b generates.
(let [candidates (take-while #(< % 1000) (primes))
candidates (concat candidates (map - candidates))
coefficients (for [a candidates b candidates] [a b])]
(->> coefficients
(map (fn [[a b]]
{:product (* a b)
:primes (->> (map (quadratic-f a b) (range))
(take-while prime?) count)}))
(apply max-key :primes)
:product))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.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
We should first represent diagonals. We can see that the first four diagonals are all incremented by two (following the spiral), then the next four are incremented by four, then six and so on.
If we start by generating a sequence of steps, that should look something
like 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, … and then look at the reductions we
get by reducing + over this sequence, starting with 1, we should get the
sequence 1, 3, 5, 7, 9, 13, 17, … The last thing we need to figure out is
when to stop reducing, which is when we’ve looked at
(let [n 1001]
(->> (range 1 (int (/ (inc n) 2)))
(mapcat (comp (partial repeat 4) (partial * 2)))
(reductions + 1) (reduce +)))Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243\ 42=16, 43=64, 44=256, 45=1024\ 52=25, 53=125, 54=625, 55=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
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
Since we’re dealing with relatively small numbers, this can easily be brute forced, by collecting all powers a^b into a set, and count them.
(let [n 100
nums (range 2N (inc n))
terms (for [a nums b nums] (Math/pow a b))]
(->> terms (into #{}) count))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 23.
3
7 4\
2 4 6\
8 5 9 3
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)
We need to optimize out solution from problem 18 to be a able to find the maximum path of this triangle. The trick is simply to memoize the function from problem 18.
Also we have to read the triangle.txt file. If transform numbers like 03
to 3 and enclose the text with brackets, we can simply use read-string
to get a vector that we can pass to seq->triangle.
(let [text (-> (io/file (io/resource "triangle.txt"))
(slurp) (s/replace #"0(\d)" "$1"))
rows (count (s/split-lines text))
nums (read-string (str "[" text "]"))
triangle (seq->triangle rows nums)]
(maximum-path-sum triangle))