# Project Euler, Problems 1-10

``````

In [34]:

using TimeIt
using BenchmarkTools

``````
``````

INFO: Precompiling module JLD.
WARNING: could not import Base.lastidx into LegacyStrings

``````

## Problem 1

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.

``````

In [11]:

@time sum([x for x in 1:999 if ((x%3 ==0) || (x%5 == 0))])

``````
``````

0.056626 seconds (28.83 k allocations: 1.264 MB)

Out[11]:

233168

``````
``````

In [12]:

@time sum(x for x in 1:999 if ((x%3 == 0) || (x%5 ==0)))

``````
``````

0.058550 seconds (30.46 k allocations: 1.302 MB)

Out[12]:

233168

``````

## Problem 2

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.

``````

In [1]:

immutable Fibonacci
end

``````
``````

In [2]:

Base.start(f::Fibonacci) = (0,1)
Base.next(f::Fibonacci, state) = (state[2], (state[2], state[1] + state[2]))
Base.done(f::Fibonacci, state) = false
Base.iteratorsize(f::Fibonacci) = Base.IsInfinite()

``````
``````

In [13]:

sum(collect(filter(x -> iseven(x) && x < Int(4e6), take(Fibonacci(), 50))))

``````
``````

Out[13]:

4613732

``````
``````

In [35]:

using Lazy

``````
``````

In [18]:

@timeit sum(filter(iseven, takewhile(x->x<4e6,Fibonacci())))

``````
``````

1000 loops, best of 3: 1.08 ms per loop

Out[18]:

0.00107524478

``````

## Problem 3

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

What is the largest prime factor of the number 600851475143 ?

``````

In [49]:

#sieve of Erasthosenes
function PrimeSieve(N::Int64)
isprime = trues(N)
for i = 2:Int64(trunc(sqrt(N)))
if isprime[i]
for j in (i*i):i:N
isprime[j] = false
end
end
end
return filter(x -> isprime[x], 2:N)
end

``````
``````

Out[49]:

PrimeSieve (generic function with 1 method)

``````
``````

In [20]:

function LargestPrimeFactor(N::Int64)
for x in reverse(Primes(10000))
if N % x == 0
return x
end
end
return N
end

``````
``````

WARNING: Method definition LargestPrimeFactor(Int64) in module Main at In[2]:2 overwritten

Out[20]:

LargestPrimeFactor (generic function with 1 method)

at In[20]:2.

``````
``````

In [23]:

@timeit LargestPrimeFactor(600851475143)

``````
``````

1000 loops, best of 3: 182.20 µs per loop

Out[23]:

0.000182200056

``````

## Problem 4

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.

``````

In [24]:

@timeit maximum(filter(x -> reverse("\$x") == "\$x", [x*y for x in 100:999 for y in x:999]))

``````
``````

1 loops, best of 3: 75.79 ms per loop

Out[24]:

0.075786782

``````
``````

In [27]:

@timeit maximum(filter(x -> reverse("\$x") == "\$x", (x*y for x in 999:-1:100 for y in 999:-1:x)))

``````
``````

1 loops, best of 3: 85.85 ms per loop

Out[27]:

0.085848368

``````
``````

In [35]:

@timeit maximum(unique([x*y for x in 100:999 for y in x:999 if reverse("\$(x*y)") == "\$(x*y)"]))

``````
``````

1 loops, best of 3: 83.40 ms per loop

Out[35]:

0.083397317

``````

## Problem 5

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?

``````

In [2]:

#Euclid's algorithm for GCD
function GCD(a::Int64, b::Int64)
if b == 0
return a
else
return GCD(b, a % b)
end
end
LCM(a::Int64, b::Int64) = div(abs(a), GCD(a,b)) * abs(b)

``````
``````

Out[2]:

LCM (generic function with 1 method)

``````
``````

In [64]:

@timeit reduce(LCM, 1, 1:20)

``````
``````

1000000 loops, best of 3: 948.38 ns per loop

Out[64]:

9.48378315e-7

``````

## Problem 6

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

``````

In [71]:

sum(1:100)^2 - sum(map(x -> x^2, 1:100))

``````
``````

Out[71]:

25164150

``````

## Problem 7

What is the 10001st prime number?

``````

In [1]:

immutable PrimeIt
end

``````
``````

In [30]:

Base.start(::PrimeIt) = (2, Dict{Int64, Int64}())
function Base.next(::PrimeIt, state)
q = state[1]
D = state[2]
while true
if q not in keys(D)
D[q * q] = q
return q, (q+1, D)
else
for p in D[q]
if !(p+q in keys(D))
D[p+q] = []
end
push!(D[p+q], p)
end
delete!(D, q)
end
end
end
Base.done(::PrimeIt, q) = false
Base.iteratorsize(::PrimeIt) = Base.IsInfinite()

``````
``````

WARNING: Method definition start(Main.PrimeIt) in module Main at In[9]:2 overwritten at In[30]:1.
WARNING: Method definition next(Main.PrimeIt, Any) in module Main at In[9]:4 overwritten at In[30]:3.
WARNING: Method definition done(Main.PrimeIt, Any) in module Main at In[9]:12 overwritten at In[30]:20.
WARNING: Method definition iteratorsize(Main.PrimeIt) in module Main at In[9]:13 overwritten at In[30]:21.

``````
``````

In [41]:

@timeit last(collect(take(PrimeIt(), 10001)))

``````
``````

10 loops, best of 3: 17.51 ms per loop

Out[41]:

0.017505281

``````

## Problem 8

``````

In [8]:

bigString = replace("""73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450""", '\n', "")

``````
``````

Out[8]:

"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

``````
``````

In [35]:

@benchmark maximum([mapreduce(x->parse(Int64,x), *, 1, y) for y in [bigString[i:i+12] for i in 1:length(bigString)-12] if !('0' in y)])

``````
``````

Out[35]:

BenchmarkTools.Trial:
memory estimate:  172.06 KiB
allocs estimate:  3514
--------------
minimum time:     228.361 μs (0.00% GC)
median time:      239.769 μs (0.00% GC)
mean time:        271.703 μs (7.85% GC)
maximum time:     4.371 ms (88.65% GC)
--------------
samples:          10000
evals/sample:     1
time tolerance:   5.00%
memory tolerance: 1.00%

``````

## Problem 9

``````

In [48]:

[a*b*c for a in 1:1000 for b in a:1000 for c in b:1000 if (a^2 + b^2 == c^2 && a+b+c == 1000)]

``````
``````

Out[48]:

1-element Array{Int64,1}:
31875000

``````

## Problem 10

``````

In [51]:

@benchmark sum(PrimeSieve(2000000))

``````
``````

Out[51]:

BenchmarkTools.Trial:
memory estimate:  3.28 MiB
allocs estimate:  18
--------------
minimum time:     30.390 ms (0.00% GC)
median time:      31.466 ms (0.00% GC)
mean time:        32.183 ms (1.03% GC)
maximum time:     42.452 ms (5.69% GC)
--------------
samples:          156
evals/sample:     1
time tolerance:   5.00%
memory tolerance: 1.00%

``````
``````

In [52]:

``````
``````

Out[52]:

66666.66666666667

``````
``````

In [ ]:

``````