↑ Up

Project Euler

Table of contents


Problem 1: Multiples of 3 and 5

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

s = (1..999).filter(|x| x%3==0 or x%5==0).sum()
print(s)

# 233168

Problem 2: Even Fibonacci numbers

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

fib = || (|[x,y]| [y,x+y]).orbit([1,2]).map(|[x,y]| x)
s = fib().until(|x| x>4000000).filter(|x| x%2==0).sum()
print(s)

# 4613732

Problem 3: Largest prime factor

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143?

isprime = |n| n>1 and (2..).until(|i| i*i>n).all(|i| n%i!=0)

function factor(n)
   primes = (2..).filter(isprime)
   a = []
   for p in primes
      e = (1..).until(|k| n%(p^k)!=0).count()
      if e!=0
         a.push([p,e])
         n = n//p^e
      end
      if p>n then break end
   end
   return a
end

a = factor(600851475143)
print(a)
print(a[-1][0])

# [[71, 1], [839, 1], [1471, 1], [6857, 1]]
# 6857

Problem 4: Largest palindrome product

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

function palindromic(x)
   s = str(x); m = len(s)//2
   return s[..m-1] == s[..m:-1]
end

function largest(n)
   a = 10^(n-1)+1..10^n-1
   for x in (10^(2*n)..:-1).filter(palindromic)
      for d in a
         if x%d==0 and x//d in a
            return [x,d,x//d]
         end
      end
   end
end

print(largest(3))

# [906609, 913, 993]

Problem 5: Smallest multiple

# 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?

gcd = |a,b| a if b==0 else gcd(b,a%b)
lcm = |a| a.reduce(|x,y| x*y//gcd(x,y))
print(lcm(1..20))

# 232792560

Problem 6: Sum square difference

# 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.
# Find the difference between the sum of the squares of the first one
# hundred natural numbers and the square of the sum.

d = |n| (1..n).sum()^2-(1..n).sum(|x| x^2)
print(d(100))

# 25164150

Problem 7: 10001st prime

# 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 10001st prime
# number?

prime = |n| n>1 and (2..).until(|i| i*i>n).all(|i| n%i!=0)
p = |m| (1..).filter(prime).skip(m-1)()
print(p(10001))

# 104743

Problem 8: Largest product in a series

# The four adjacent digits in the 1000-digit number that have the
# greatest product are 9 × 9 × 8 × 9 = 5832.
# Find the thirteen adjacent digits in the 1000-digit number that
# have the greatest product. What is the value of this product?

digits = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""

function adjacent_prod_max(n,digits)
   a = list(digits).filter(|c| c.isdigit()).map(int)
   return list(0..len(a)-n).map(|k| a[k..k+n-1]).max(|t| t.prod())
end

a = adjacent_prod_max(13,digits)
print(a)
print(a.prod())

# [5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5]
# 23514624000

Problem 9: Special Pythagorean triplet

# A Pythagorean triplet is a set of three natural numbers,
# a < b < c, for which,
#   a^2 + b^2 = c^2.
# For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
# There exists exactly one Pythagorean triplet for which
# a + b + c = 1000. Find the product a*b*c.

function partitions(n,k,max)
   if n==0
      return [[]]
   elif n>k*max
      return []
   elif n==k*max
      return [[max]*k]
   elif k==1
      return [[n]]
   else
      a = []
      for x in 1..min(max,n-1)
         for t in partitions(n-x,k-1,x)
            a.push(t+[x])
         end
      end
      return a
   end
end

function triplets(n)
   partitions(n,3,n).filter(|[x,y,z]| x^2+y^2==z^2)
end

triplets(1000).each(print)

# [200, 375, 425]

Problem 10: Summation of primes

# The sum of the primes below 10 is 2+3+5+7 = 17.
# Find the sum of all the primes below two million.

use math.nt: isprime
s = (1..2000000).filter(isprime).sum()
print(s)

# 142913828922