Project

General

Profile

Bug #1934 ยป euler060a.rb

Ruby program that leads to segmentation fault - jeheine (Julia Heine), 08/13/2009 06:20 AM

 
1
#!/opt/local/bin/ruby1.9 
2

    
3
# Problem 60
4
# 02 January 2004
5
# 
6
# 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.
7
# 
8
# Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
9

    
10
require 'prime'
11

    
12
# def check_for_result(concat_prime_set, current_prime)
13
#   n_primes = 5
14
#   concatable_key_set = Array.new
15
#   sums = Array.new
16
# 
17
#   local_concat_prime_set = concat_prime_set.select {|key, value| value.length >= n_primes}
18
#   local_concat_prime_set.each do |key, value|
19
#     new_value = value.dup
20
#     local_concat_prime_set[key] = new_value.delete_if {|x| x < key}
21
#   end  
22
#   local_concat_prime_set.keys.each do |key|
23
#     concatable_key_set.push(key) if local_concat_prime_set[key].length >= n_primes
24
#   end
25
# 
26
#   concatable_key_set.each do |key|
27
#     prime_sets_to_check1 = local_concat_prime_set[key].combination(n_primes).to_a
28
#     prime_sets_to_check2 = Array.new
29
#     prime_sets_to_check1.each {|prime_set| prime_sets_to_check2.push if prime_set.include?(current_prime)}
30
#     prime_sets_to_check2.each do |key_set|
31
#       temp_key_set = key_set.dup
32
#       concatable = true
33
#       until (temp_key_set == [] || concatable == false) do
34
#         key = temp_key_set.shift
35
#         temp_key_set.each do |key2|
36
#           concatable = false unless concat_prime_set[key].include?(key2)
37
#         end
38
#       end
39
#       sums.push(key_set.inject:+) if concatable
40
#     end
41
#   end
42
#   if sums.length >= 1
43
#     return sums
44
#   else    
45
#     return []
46
#   end
47
# end
48

    
49

    
50

    
51
#result = Array.new
52
concat_prime_sets = Hash.new
53
concat_prime_sets[3] = [3]
54
n_primes = 5
55
sums = Array.new
56

    
57

    
58
Prime.each do |prime|
59
  next if prime <= 5
60
  concat_prime_sets[prime] = Array.new
61
  concat_prime_sets.keys.each do |key|
62
    concat_left_right = prime.to_s + key.to_s
63
    concat_right_left = key.to_s + prime.to_s
64
    if concat_left_right.to_i.prime? && concat_right_left.to_i.prime?
65
      concat_prime_sets[prime].push(key)
66
      concat_prime_sets[key].push(prime)
67
    end
68
  end
69
  concat_prime_sets[prime].push(prime)
70
  
71
  concatable_key_set = Array.new
72

    
73
  local_concat_prime_set = concat_prime_sets.select {|key, value| value.length >= n_primes}
74
  local_concat_prime_set.each do |key, value|
75
    new_value = value.dup
76
    local_concat_prime_set[key] = new_value.delete_if {|x| x < key}
77
  end  
78
  local_concat_prime_set.keys.each do |key|
79
    concatable_key_set.push(key) if local_concat_prime_set[key].length >= n_primes
80
  end
81

    
82
  concatable_key_set.each do |key|
83
    prime_sets_to_check1 = local_concat_prime_set[key].combination(n_primes).to_a
84
    prime_sets_to_check2 = Array.new
85
    prime_sets_to_check1.each {|prime_set| prime_sets_to_check2.push(prime_set) if prime_set.include?(prime)}
86
    prime_sets_to_check2.each do |key_set|
87
      temp_key_set = key_set.dup
88
      concatable = true
89
      until (temp_key_set == [] || concatable == false) do
90
        key = temp_key_set.shift
91
        temp_key_set.each do |key2|
92
          concatable = false unless concat_prime_sets[key].include?(key2)
93
        end
94
      end
95
      sums.push(key_set.inject:+) if concatable
96
    end
97
  end
98
  puts "# of primes: #{concat_prime_sets.length} results: #{sums}  prime: #{prime}  process time: #{Process.times.utime}"
99
  break if sums.length >= 1
100
end
101

    
102
puts sums.min