Project Euler problem 37: truncatable primes

Question

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?

• Luis Tellez: 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

Answer 1

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

• user24658: 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%

Answer 2

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)

Answer 3

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