Project Euler problem 37: truncatable primes

I am working on Project Euler problem 37 and I have the following program:

#!/usr/bin/ruby -w

require 'prime'
h=11
y=0
x=0
while x < 11
if h.prime? == true
boo = true
f=0
n=h
c=0
while n > 0
f += (n%10) * 10**(10-c)
n/=10
boo = false if n.prime? == false && n != 0
c+=1
end
n=h
c=10
while c > 0
n = n % (10**c)
boo = false if n.prime? == false && n != 0
c-=1
end
f /= 10 while f % 10 == 0
if boo == true
y+=h
x+=1
p h
end
end
h+=2
end
p y


It's designed to catch all of the eleven truncatable primes and does a good job of it, it catches the first ten is under one second, but it takes forty-nine seconds to find the last one, which happens to be, admittedly, a much larger number than the rest, is there any way to speed this up so that the eleventh one does not take so much time?

• i dont know any ruby, but i was reading about Truncatable primes and found this post that have 2 different approaches to solver it, maybe it can help you. mathblog.dk/project-euler-37-truncatable-primes May 3, 2013 at 20:35

Some small notes on style:

• if h.prime? == true should be if h.prime?; never use method? == true or method? == false, use if and unless.

• I would replace your if h.prime? with next unless h.prime? and unindent the entire inner block; I hate having the entire body of your loop wrapped in a single if statement.

• You should really, really choose better variable names. Single character names are a terrible practice. This is borderline obfuscated, who wants to figure out what a blob of uncommented difficult to read code does, in order to help you improve its performance?

Here's a simple refactor which is (on my system) 4x faster than your code, mostly because I'm aborting the outer loop early if the first inner while fails:

#!/usr/bin/ruby -w

require 'prime'

h, y, x = 9, 0, 0

while x < 11
h += 2
next unless h.prime?

boo, f, n, c = true, 0, h, 0

while n > 0
f += (n % 10) * 10 ** (10 - c)
n /= 10
boo = false if !n.prime? && n != 0
c += 1
end

# Don't keep checking if we already know this number fails
next unless boo

n = h
c = 10

while c > 0
n %= (10 ** c)
boo = false if !n.prime? && n != 0
c-=1
end

f /= 10 while f % 10 == 0

if boo
y += h
x += 1
p h
end
end

p y

• Thanks for the tips, I'll improve my use of variable names in the future. You helped me cut down my run time by 75% May 3, 2013 at 20:30

When dealing with mathematical/logical problems, you should consider ditching imperative style altogether and use functional programming instead. Ruby is not a functional language, but you can apply a lot of its principles. The point is: describe what you are doing, what values are, not how you get them.

Let's start coding taking the description of the problem, isn't that what you'd like to write?

solution = primes.select { |n| truncatable_prime?(n) }.take(11).sum


Well, so write it and just fill the blanks. I'd write (Ruby 2.x):

require 'prime'

def truncatable_prime?(n)
if n >= 11
s = n.to_s # using strings for simplicity
truncated_left = (0...s.length-1).map { |i| s[0..i] }.map(&:to_i)
truncated_right = (1...s.length).map { |i| s[i..-1] }.map(&:to_i)
(truncated_left + truncated_right + [n]).all?(&:prime?)
else
false
end
end

module Array
def sum
reduce(0, :+)
end
end

primes = Prime.instance.lazy
solution = primes.select { |n| truncatable_prime?(n) }.take(11).sum
#=> 7....7 (in 3.7s)


Instead of testing for prime-nes of odd numbers you can just generate primes:

require 'prime'
prime_generator = Prime.instance
prime_generator.each do |prime|
break if prime > 1000
puts prime #well, do testing for truncatability here
end