-
Notifications
You must be signed in to change notification settings - Fork 6
/
051 Prime digit replacements.sf
49 lines (36 loc) · 1.06 KB
/
051 Prime digit replacements.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#!/usr/bin/ruby
# Author: Trizen
# Date: 18 March 2023
# https://github.com/trizen
# Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
# https://projecteuler.net/problem=51
# Runtime: 33.514s
for n in (1..Inf) {
say "Sieving #{n}-digit primes..."
var table = Hash()
each_prime(10**(n-1), 10**n - 1, {|p|
var s = p.to_s
var indices = Hash()
s.chars.each_kv {|k,v|
indices{v} := [] << k
}
indices.each_value {|idx|
for i in (1..idx.len) {
idx.combinations(i, {|*a|
table{a.reduce({|a,b| a.insert('*', b, 1) }, s)} := [] << p
})
}
}
})
var min = Inf
table.each_value {|value|
if ((value.len == 8) && (value.head < min)) {
say "Found prime group: #{value}"
min = value.head
}
}
if (min < Inf) {
say "Least such prime is: #{min}"
break
}
}