|
#!/opt/local/bin/ruby1.9
|
|
|
|
# Problem 60
|
|
# 02 January 2004
|
|
#
|
|
# The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
|
|
#
|
|
# Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
|
|
|
|
require 'prime'
|
|
|
|
# def check_for_result(concat_prime_set, current_prime)
|
|
# n_primes = 5
|
|
# concatable_key_set = Array.new
|
|
# sums = Array.new
|
|
#
|
|
# local_concat_prime_set = concat_prime_set.select {|key, value| value.length >= n_primes}
|
|
# local_concat_prime_set.each do |key, value|
|
|
# new_value = value.dup
|
|
# local_concat_prime_set[key] = new_value.delete_if {|x| x < key}
|
|
# end
|
|
# local_concat_prime_set.keys.each do |key|
|
|
# concatable_key_set.push(key) if local_concat_prime_set[key].length >= n_primes
|
|
# end
|
|
#
|
|
# concatable_key_set.each do |key|
|
|
# prime_sets_to_check1 = local_concat_prime_set[key].combination(n_primes).to_a
|
|
# prime_sets_to_check2 = Array.new
|
|
# prime_sets_to_check1.each {|prime_set| prime_sets_to_check2.push if prime_set.include?(current_prime)}
|
|
# prime_sets_to_check2.each do |key_set|
|
|
# temp_key_set = key_set.dup
|
|
# concatable = true
|
|
# until (temp_key_set == [] || concatable == false) do
|
|
# key = temp_key_set.shift
|
|
# temp_key_set.each do |key2|
|
|
# concatable = false unless concat_prime_set[key].include?(key2)
|
|
# end
|
|
# end
|
|
# sums.push(key_set.inject:+) if concatable
|
|
# end
|
|
# end
|
|
# if sums.length >= 1
|
|
# return sums
|
|
# else
|
|
# return []
|
|
# end
|
|
# end
|
|
|
|
|
|
|
|
#result = Array.new
|
|
concat_prime_sets = Hash.new
|
|
concat_prime_sets[3] = [3]
|
|
n_primes = 5
|
|
sums = Array.new
|
|
|
|
|
|
Prime.each do |prime|
|
|
next if prime <= 5
|
|
concat_prime_sets[prime] = Array.new
|
|
concat_prime_sets.keys.each do |key|
|
|
concat_left_right = prime.to_s + key.to_s
|
|
concat_right_left = key.to_s + prime.to_s
|
|
if concat_left_right.to_i.prime? && concat_right_left.to_i.prime?
|
|
concat_prime_sets[prime].push(key)
|
|
concat_prime_sets[key].push(prime)
|
|
end
|
|
end
|
|
concat_prime_sets[prime].push(prime)
|
|
|
|
concatable_key_set = Array.new
|
|
|
|
local_concat_prime_set = concat_prime_sets.select {|key, value| value.length >= n_primes}
|
|
local_concat_prime_set.each do |key, value|
|
|
new_value = value.dup
|
|
local_concat_prime_set[key] = new_value.delete_if {|x| x < key}
|
|
end
|
|
local_concat_prime_set.keys.each do |key|
|
|
concatable_key_set.push(key) if local_concat_prime_set[key].length >= n_primes
|
|
end
|
|
|
|
concatable_key_set.each do |key|
|
|
prime_sets_to_check1 = local_concat_prime_set[key].combination(n_primes).to_a
|
|
prime_sets_to_check2 = Array.new
|
|
prime_sets_to_check1.each {|prime_set| prime_sets_to_check2.push(prime_set) if prime_set.include?(prime)}
|
|
prime_sets_to_check2.each do |key_set|
|
|
temp_key_set = key_set.dup
|
|
concatable = true
|
|
until (temp_key_set == [] || concatable == false) do
|
|
key = temp_key_set.shift
|
|
temp_key_set.each do |key2|
|
|
concatable = false unless concat_prime_sets[key].include?(key2)
|
|
end
|
|
end
|
|
sums.push(key_set.inject:+) if concatable
|
|
end
|
|
end
|
|
puts "# of primes: #{concat_prime_sets.length} results: #{sums} prime: #{prime} process time: #{Process.times.utime}"
|
|
break if sums.length >= 1
|
|
end
|
|
|
|
puts sums.min
|