Carson Baker

Big-Stack Developer + Designer
about | contact | cv | instagram insta | github | facebook fb


Project Euler Code

February 19th, 2010

My 2010 New Year's resolution was to solve the first 25 problems on Project Euler. I chose to code mainly in Scala for a few reasons: (1) Its functional abilities should lend itself to concise code; (2) It's fast, portable, and easy to execute; and (3) I wanted to build familiarity with a new language. For a few problems I used Python or Ruby, just to mix it up.

Problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5. 
0 until 1000 filter(i => {
  (i % 3 == 0) || (i % 5 == 0)
}) reduceLeft { _ + _ }
Reveal code

Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. 
def fib_list(upto:Int) : List[Int] = {
  var l = List(0) 
  var a = 0
  var b = 1
  var c = 0

  for(i <- (0 until upto)) {
    c = a + b
    a = b
    b = c

    l = l ++ List(c)
  }
  l
}

fib_list(32).filter { _ % 2 == 0 } reduceLeft { _ + _ }
Reveal code

Problem 3

Find the largest prime factor of a composite number. 
var biggy = BigInt("600851475143")

// would use Math.sqrt, but not avail for BigInt
def cap_search = { biggy / 2 }

def find_next_factor(i:BigInt) : Option[BigInt] = {
  if(i > cap_search) None
  else if(biggy % i == 0) Some(i)
  else find_next_factor(i + 2)  
}

def find_biggest_factor(i:BigInt) : BigInt = {
  find_next_factor(i+2) match {
    case None => biggy
    case Some(x) => {
      biggy /= x
      find_biggest_factor(x)
    }
  }
}

// beginning the search with 3 because
// 1 is a trivial factor and 2 is trivially not
println(find_biggest_factor(3))
Reveal code

Problem 4

Find the largest palindrome made from the product of two 3-digit numbers. 
def is_palindrome(x:Int) = {
  // reverse won't return a RichString in scala 2.8 :-)
  x.toString.reverse.toString == x.toString
}

var biggest = 0

for(a <- (100 to 999)) {
  for(b <- (a to 999)) {
    val prod = a * b
    if(is_palindrome(prod))
      biggest = Math.max(biggest, prod)
  }
}

println(biggest)
Reveal code

Problem 5

What is the smallest number divisible by each of the numbers 1 to 20? 
var guess:BigInt = 380
var continue = true

def div_by_all(guess:BigInt, r: Range) = r map { guess % _ == 0 } reduceLeft { _ && _ }

while(continue) {
  if(div_by_all(guess, 1 to 20))
    continue = false
  else
    guess += 380
}

println(guess)
Reveal code

Problem 6

What is the difference between the sum of the squares and the square of the sums? 
def sq_of_sum(n: Int) { (n*n*n*n + 2*n*n*n + n*n) / 4 }
def sum_of_sq(n: Int) { (0 to n) map { i => i*i } reduceLeft { _+_ } }
println(sq_of_sum(100) - sum_of_sq(100))
Reveal code

Problem 7

Find the 10001st prime. 
// Using Sieve of Eratosthenes
// From prior experiment, 250000 is enough room
val length = 250000;
val candidates = Array.fill[Boolean](length)(true);
var found_count = 0;

for(i <- (2 until length/2)) {
  if(candidates(i)) {
    for(j <- (i*2 until length by i))
      candidates(j) = false;
    found_count += 1;
    if(found_count == 10001) println(i);
  }  
}
Reveal code

Problem 8

Discover the largest product of five consecutive digits in the 1000-digit number. 
val str =  """73167176531330624919225119674426574742355349194934
              96983520312774506326239578318016984801869478851843
              85861560789112949495459501737958331952853208805511
              12540698747158523863050715693290963295227443043557
              66896648950445244523161731856403098711121722383113
              62229893423380308135336276614282806444486645238749
              30358907296290491560440772390713810515859307960866
              70172427121883998797908792274921901699720888093776
              65727333001053367881220235421809751254540594752243
              52584907711670556013604839586446706324415722155397
              53697817977846174064955149290862569321978468622482
              83972241375657056057490261407972968652414535100474
              82166370484403199890008895243450658541227588666881
              16427171479924442928230863465674813919123162824586
              17866458359124566529476545682848912883142607690042
              24219022671055626321111109370544217506941658960408
              07198403850962455444362981230987879927244284909188
              84580156166097919133875499200524063689912560717606
              05886116467109405077541002256983155200055935729725
              71636269561882670428252483600823257530420752963450""".replaceAll("\\s","")

def five_at_a_time(s:String)(block: String => Unit) = {
  for(i <- (0 to str.length - 5))
    block(str.substring(i, i + 5))
}

var biggest = 0

five_at_a_time(str) { substr =>
  val prod = substr.toList.map[Int](x => x.toString.toInt).reduceLeft { _ * _ }
  biggest = Math.max(biggest, prod)
}

println(biggest)
Reveal code

Problem 9

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000. 
(1..250).each do |a|
  (a..500).each do |b|
    c = Math.sqrt( a**2 + b**2 )
    if a + b + c == 1000
      puts (a * b * c).to_int
    end
  end
end
Reveal code

Problem 10

Find the sum of all the primes below 2 million 
val length = 2000000;
val candidates = Array.fill[Boolean](length)(true);

for(i <- (2 until length/2)) {
  if(candidates(i)) {
    for(j <- (i*2 until length by i))
      candidates(j) = false;
  }  
}

var sum = BigInt(0);
for(i <- (2 until length)) {
  if(candidates(i)) {
    sum += i;
  }
}

println(sum)
Reveal code

Problem 12

What is the value of the first triangle number to have over five hundred divisors? 
def prime_fac(n, i = 2)
  while(i < n)
    n_over_i = n / i
    if(n % i == 0)
      return [i] + prime_fac(n_over_i, i)
    end
    i += 1
  end
  # base case
  return [i]
end

def count_divisors(n)
  primes = prime_fac(n)
  primes.uniq.inject(1) do |sum, n|
    sum * (primes.count(n) + 1)
  end
end

triangle_number = 0
i = 1
while(true)
  triangle_number += i
  break if(count_divisors(triangle_number) > 500)
  i += 1
end

puts triangle_number
Reveal code

Problem 14

Find the longest sequence using a starting number under one million. 
val tops = 1000000
val start = 500000
var biggest = 0

for(i <- start to tops) {

  var last:BigInt = i
  var len = 1

  while(last != 1) {
    last =  if(last % 2 == 0) last / 2 else last*3 + 1
    len += 1
  }

  if(len > biggest) {
    biggest = len
    println(i + " results in length " + len)
  }

  len = 0

}
Reveal code

Problem 16

What is the sum of the digits of the number 2^1000? 
var two_exp_k:BigInt = 2
for(i <- 1 until 1000) { two_exp_k = two_exp_k * 2 }
val digit_chars = two_exp_k.toString.toCharArray
val digit_ints = digit_chars.map { _.toString.toInt }
println(digit_ints.reduceLeft{_+_})
Reveal code

Problem 20

Find the sum of digits in 100! 
def factorial(n: BigInt): BigInt = { if (n == 0) 1 else n * factorial(n-1) }
val digit_chars = factorial(100).toString.toCharArray
val digit_ints = digit_chars.map { _.toString.toInt }
println(digit_ints.reduceLeft{_+_})
Reveal code

Problem 21

Find the joint sum of the pairs of amicable numbers between 0 and 10000. 
val sum_of_proper_divisors = (0 until 10000)
  .map(n => ((1 to n/2) filter(i => n % i == 0)) sum)

def is_amicable_pair(a:Int,b:Int) = {
  (sum_of_proper_divisors(a) == b) && 
  (sum_of_proper_divisors(b) == a)
}

var sum = 0
for(i <- 1 until 10000; j <- 1 until i) {
  if(is_amicable_pair(i,j)) {
    sum += i + j
  }
}

println(sum)
Reveal code

Problem 35

How many circular primes are there below 1 million? 
length = 1000000
candidates = Array.new(length, true)

2.upto(length/2).each do |i|
  (i*2).step(length, i) do |j|
    candidates[j] = false
  end
end

count = 0
candidates.each_with_index do |e, i|
  if e
    digits = i.to_s.split('')
    count += 1 if digits.length.times.map { candidates[digits.rotate!.join.to_i] }.all?
    end
  end
end

puts count - 2
Reveal code

Problem 43

Find the sum of all pandigital numbers with an unusual substring divisibility property. 
pan_dig = "0123456789".split('')
ans = 0
primes = [2,3,5,7,11,13,17]

pan_dig.permutation do |n|

  meets_primes_divisibility = true
  for i in 0..6
    if not n.slice(i, 3).join("").to_i % primes[i] == 0
      meets_primes_divisibility = false
      break
    end
  end

  if meets_primes_divisibility
    ans += n.join("").to_i
  end

end

puts ans
Reveal code

Problem 51

Find the smallest prime which, by changing the same part of the number, can form eight different primes. 
def sieve_of_eratosthenes(length)
  candidates = Array.new(length, true)
  2.upto(length/2).each do |i|
    (i*2).step(length, i) do |j|
      candidates[j] = false
    end
  end
  return candidates
end

# from experimentation i know the answer is 6 digits
primes                = sieve_of_eratosthenes(1_000_000)
compacted_primes      = primes.each_with_index.map { |x, i| i if x }.compact
desired_family_size   = 8

# loop through the generated primes
for x in compacted_primes

  # from experimentation i know the answer
  # requires mutating three digits.
  # it wouldn't add much time to the execution
  # if we checked 1 and 2 choosings, but for
  # clarity's sake i've omitted this looping
  choose_digits = 3

  # figure out all combinations of a given number of digits that we can mutate
  combo_digit_places = (0...x.to_s.length).to_a.combination(choose_digits).to_a

  # choose the 0,1,2 digit places and then choose the 0,1,3 digit places, etc.
  for chosen_digits in combo_digit_places

    # reset variables
    num_of_primes_in_family = 0
    x_str = x.to_s
    misses = 0

    # continue to next check if the numbers are different in our digit selection
    next if chosen_digits.map { |d| x_str[d] }.uniq.size != 1

    start_digit = chosen_digits.include?(0) ? 1 : 0 # we can't start a number with a zero

    digit_range = (start_digit..9)

    # mutate the chosen digits
    digit_range.each_with_index do |replacement, index|

        for digit_index in chosen_digits
          x_str[digit_index] = replacement.to_s          
        end

        if(primes[x_str.to_i]) # we have a prime
          num_of_primes_in_family += 1
        else
          misses += 1
          # e.g. there's no hope for an 8-family prime if we have two misses
          # so we should just try the next one
          break if misses > digit_range.to_a.length - desired_family_size
        end
    end

    if(num_of_primes_in_family == desired_family_size)
      puts x
      exit
    end

  end
end
Reveal code

Problem 93

Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers. 
longest = 0
best_comb = nil

ops = %w(+ - * /).map { |o| eval("lambda {|m,n| m.to_f %s n.to_f }" % o) }

for comb in (1..9).to_a.combination(4)
  gap_check = Array.new(100, false)

  for (a,b,c,d) in comb.permutation
    for (o1, o2, o3) in ops.repeated_permutation(3)

      p_ords = []

      begin p_ords << o3.call(o2.call(o1.call(a, b), c), d) rescue ZeroDivisionError end
      begin p_ords << o3.call(o1.call(a, b), o2.call(c, d)) rescue ZeroDivisionError end
      begin p_ords << o3.call(o2.call(a, o1.call(b, c)), d) rescue ZeroDivisionError end
      begin p_ords << o3.call(a, o2.call(o1.call(b, c), d)) rescue ZeroDivisionError end
      begin p_ords << o3.call(a, o2.call(b, o1.call(c, d))) rescue ZeroDivisionError end

      for result in p_ords
        index = (result % 1 == 0 and result > 0) ? result - 1 : 0
        gap_check[index] = true
      end

    end    
  end

  length = 0
  for i in gap_check
    break if not i
    length += 1 
  end

  if length > longest
    longest = length
    best_comb = comb
  end

end

puts best_comb.join("")
Reveal code

Problem 104

Find the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital. 
def is_pandigital?(num)
  num = num.to_s
  first = num[0,9].split('')
  first.delete("0")
  return first.uniq.count == 9
end

pre_fib = 0
cur_fib = 1
new_fib = 0

i = 1

puts "Standard fibonacci accumulation"

# use standard fibonacci iteration to
# get a sufficiently big number
# it's known (from prev runs) that there
# are no solutions before 10e40
while(i += 1) do

  new_fib = pre_fib + cur_fib
  pre_fib = cur_fib
  cur_fib = new_fib

  # number is big enough that we have enough
  # separation between upper and lower digits 
  break if((cur_fib / 10e100).round != 0)

end

pre_upper = 0
cur_upper = 0
new_upper = 0

pre_lower = 0
cur_lower = 0
new_lower = 0

# now start summing the upper digits
# and lower digits separately

puts "At i = %s, switching to separate summation of upper and lower 9 digits" % i

def truncate(digits, take_front=true, places=9)
  digi_string = digits.to_s
  if(digi_string.length > places)
    return digi_string.slice(take_front ? 0 : -places, places).to_i
  else
    return digi_string.to_i
  end
end

saved_upper_digits = 15

pre_upper = truncate(pre_fib, true, saved_upper_digits)
cur_upper = truncate(cur_fib, true, saved_upper_digits)

pre_lower = truncate(pre_fib, false, 9)
cur_lower = truncate(cur_fib, false, 9)

overflowed = false

while(i += 1) do

  new_upper = (overflowed ? pre_upper / 10 : pre_upper) + cur_upper
  new_lower = pre_lower + cur_lower

  if new_upper.to_s.length > saved_upper_digits
    overflowed = true
  else
    overflowed = false
  end

  # shorten to 9 digits
  new_upper = truncate(new_upper, true, saved_upper_digits)
  new_lower = truncate(new_lower, false, 9)

  # shift the variables
  pre_upper = cur_upper
  cur_upper = new_upper

  pre_lower = cur_lower
  cur_lower = new_lower

  if(i % 25000 == 0)
    puts "at iteration %s" % i
  end

  if is_pandigital?(cur_upper) and is_pandigital?(cur_lower)
    puts "Upper digits are found to be %s" % cur_upper
    puts "Lower digits are found to be %s" % cur_lower
    puts "Number is at position %s" % i 
    break
  end

end
Reveal code


© 2004–2024 Carson Baker
Some rights reserved.