Tag Archives: project euler

Project Euler : Problem 39 in Ruby

I had an easy time with this one, which makes me feel a lot better about all the ones I had problems with!

No fancy-pants recursion or math short-cuts here, just a straight forward logic problem. The only “trick” here is to realize that since a <e; b < c, we only need to check values of a and b up to 499.

I’m sure you could whittle that number down by crunching the numbers, but it’s good enough for me!
Continue reading

Project Euler : Problem 38 in Ruby

40 problems down, 10 more till level 2!

The real trick here is to cut down on the numbers you check. Since the problem gives you 918273645 as an example we know the answer must be greater than or equal to it…meaning we only need to check digits that start with 9!

I don’t actually do it because I couldn’t figure out an elegant way to do, but it runs in just a few milliseconds so it’s fast enough in my book.

Another important factor to note is that you only need to check numbers up to 9_876 since this is the first ‘half’ of the largest pandigital possible.

Those two tricks will cut down the calculations you need to run to just a few thousand.

Problem 38

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n 1?

def get_pandigital? n
  nums = []
  (1..9).each do |digit|
    nums += (n * digit).to_s.split ''
    return 0 if nums.size != nums.uniq.size || nums.include?('0')
    return nums.join('').to_i if nums.size == 9

solution = 0

(9..9_876).each do |n|
  # could do better by only looking at 9's!
  result = get_pandigital? n
  if result > solution
    solution = result

puts solution

Check out all of my solutions on bitbucket!

Project Euler: Problem 37 in Ruby

It’s been a while since I’ve done one of these, so I was afraid of being rusty but it worked out alright. I used the generator I made a while back to create the primes (pre-filled to the example given in the project) and used procs to take care of the truncation.


Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

load 'prime_generator.rb'

def prime? n, truncate
  return false if !$primer.is_prime?(n)
  return true if n < 10
  prime? truncate.call(n), truncate

left = Proc.new { |n| n / 10 }
right = Proc.new { |n| n % 10**Math.log10(n).to_i }

$primer = Prime_Generator.new 3_797
n, sum, found = 0, 0, 0

while found < 11 do  
  if (n += 1) > 10 && prime?(n, left) && prime?(n, right)
    found += 1
    sum += n

puts sum

Also, I’ve finally moved my project euler solutions over to bitbucket. Long live Mercurial!

Project Euler: Problem 35 in Ruby

I used my prime generator from Problem 27 for this one. It would have been faster to build the rotation into my generator, but it ran fine without it.

Problem 35

How many circular primes are there below one million?

require 'prime_generator'

primer = Prime_Generator.new 1_000_000

def is_rot_prime? primer, chars
	chars.size.times do |i|
		chars = Array.new(chars.size) { |i| chars[i - 1] }
		return false if !primer.is_prime?(chars.join("").to_i)

count = 0
primer.stack.each do |n|
	count += 1 if is_rot_prime? primer, n.to_s.split("")

# subtract 1 because "1" doesn't count
puts count - 1

Speaking of the rotation, the ruby array initialize methods and negative indexers make it a cinch to rotate. How cool is this?

chars = Array.new(chars.size) { |i| chars[i - 1] }

Project Euler: Problem 34 in Ruby

Practically every Project Euler problem benefits from memoization, however the issues I ran into with #34 had nothing to do with my algorithm.

The first hurdle was figuring out the upper bound. After scratching around in my notebook, I figured any number I would be looking for would have 7 digits or less. That gives us an upper bound of 9! * 7.

The second hurde took me much, much longer to figure out.

Here’s the secret: 0! = 1

I had taken it for granted that 0! would (of course!) be 0, and I had pre-filled my cache with the number 0. I went round, and round, and round, and round, and round, and round before figuring out (quite accidentally) my error.

It doesn’t make any sense to me, but you can’t argue with math!

Problem 34

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

# cache the digit factorials
factorials = [1]
(1..9).each do |i|
	factorials.push(i * factorials.last)

result = 0
(3..2_540_160).each do |n|
	sum = n.to_s.split("").inject(0) do |sum,n|
		sum + factorials[n.to_i]
	result += n if n == sum
puts result

Runs in just under a minute 🙂

Project Euler : Problem 36 in Ruby

I’ve been ill today, but there’s no better medicine than an easy Project Euler problem! I tried doing some bitwise magic, but in the end my simplest solution proved the fastest as well.

Problem 36

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

def palindrome? s
	s == s.reverse

sum = (1..1_000_000).inject(0) do |sum, n|
	sum += palindrome?(n.to_s) && palindrome?(n.to_s 2) ? n : 0

puts sum

Project Euler: Problem 33 in Ruby

It’s fugly, but it works. The hardest part was understanding the question. If the longer description didn’t say that there were exactly 4 fractions, I might have gone crazy.

For reals.

Problem 33

Discover all the fractions with an unorthodox cancelling method.

top, bottom = 1, 1

(10..98).each do |i|
	((i/10)..9).each do |jt|
		jt *= 10
		(1..9).each do |jo|
			j = jt + jo
			next if i >= j
			if i % 10 == j / 10 && i.to_f / j == (i / 10).to_f / (j % 10)
				top *= i
				bottom *= j

puts bottom / bottom.gcd(top)

Project Euler : Problem 32 in Ruby

My solution to this is ugly, but like the tar baby the more I mess with it the worse it gets.

I originally tried to find all the 9 digit pandigitals to cycle through, but was able to cut down the processing by a TON after I figured out that there were only 2 possible digit combinations that could satisfy the problem. (x + xxxx = xxxx and xx + xxx = xxxx)


Problem #32

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

def combo size, current = 0, stack = [], results = {}

  return results[stack.join.to_i] = stack.clone if size == 0

  (1..9).each do |n|
    next if stack.include?(n)
    stack[current] = n
    combo(size - 1, current + 1, stack.clone, results)

  return results

def pandigitals a, b, c
  results = []

  $repo[a].each_pair do |a_num, a_arr|
    $repo[b].each_pair do |b_num, b_arr|
      product = a_num * b_num
      if $repo[c].include?(product)
      	c_arr = $repo[c][product]
        results.push(product) if (a_arr + b_arr + c_arr).uniq.length == 9

  return results

$repo = {
  1 => combo(1),
  2 => combo(2),
  3 => combo(3),
  4 => combo(4)

results = pandigitals(1, 4, 4) + pandigitals(2, 3, 4)

puts results.uniq.inject(:+)

Project Euler : Problem 31 in Ruby

I kept trying to make this problem harder than it actually was, but ultimately a simple greedy solution worked just fine.

I would have saved myself a lot of time by actually solving the problem before attempting to optimize. C’est la vie!

Problem #29

Investigating combinations of English currency denominations.

def count_coins coins, target, last_coin = 0

	return 1 if target == 0
	total = 0

	coins.each do |c|
		next if c < last_coin
		total += count_coins(coins, target - c, c) if (target >= c)


puts count_coins(

Project Euler : Problem 29 in Ruby

I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.

Ruby even minds the big numbers for me, so the solution is quite trivial:

Problem #29

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

MIN, MAX = 2,100
values = []

(MIN..MAX).each do |base|
  (MIN..MAX).each do |power|
    values << base**power

puts values.uniq.length