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
  end
end

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
  end
end

puts solution

Check out all of my solutions on bitbucket!

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.

BAM!

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
end

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
  end
end

puts sum

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