Substring primes: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
(Added Sidef) |
||
Line 558: | Line 558: | ||
Found 9 numbers in which all substrings are primes |
Found 9 numbers in which all substrings are primes |
||
done... |
done... |
||
</pre> |
|||
=={{header|Sidef}}== |
|||
Generic solution for any base >= 2. |
|||
<lang ruby>func split_at_indices(array, indices) { |
|||
var parts = [] |
|||
var i = 0 |
|||
for j in (indices) { |
|||
parts << array.slice(i, j) |
|||
i = j+1 |
|||
} |
|||
parts |
|||
} |
|||
func consecutive_partitions(array, callback) { |
|||
for k in (0..array.len) { |
|||
combinations(array.len, k, {|*indices| |
|||
var t = split_at_indices(array, indices) |
|||
if (t.sum_by{.len} == array.len) { |
|||
callback(t) |
|||
} |
|||
}) |
|||
} |
|||
} |
|||
func is_substring_prime(digits, base) { |
|||
for k in (^digits) { |
|||
digits.first(k+1).digits2num(base).is_prime || return false |
|||
} |
|||
consecutive_partitions(digits, {|part| |
|||
part.all { .digits2num(base).is_prime } || return false |
|||
}) |
|||
return true |
|||
} |
|||
func generate_from_prefix(p, base, digits) { |
|||
var seq = [p] |
|||
for d in (digits) { |
|||
var t = [d, p...] |
|||
if (is_prime(t.digits2num(base)) && is_substring_prime(t, base)) { |
|||
seq << __FUNC__(t, base, digits)... |
|||
} |
|||
} |
|||
return seq |
|||
} |
|||
func substring_primes(base) { # finite sequence for each base >= 2 |
|||
var prime_digits = (base-1 -> primes) # prime digits < base |
|||
prime_digits.map {|p| generate_from_prefix([p], base, prime_digits)... }\ |
|||
.map {|t| digits2num(t, base) }\ |
|||
.sort |
|||
} |
|||
for base in (2..20) { |
|||
say "base = #{base}: #{substring_primes(base)}" |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
base = 2: [] |
|||
base = 3: [2] |
|||
base = 4: [2, 3, 11] |
|||
base = 5: [2, 3, 13, 17, 67] |
|||
base = 6: [2, 3, 5, 17, 23] |
|||
base = 7: [2, 3, 5, 17, 19, 23, 37] |
|||
base = 8: [2, 3, 5, 7, 19, 23, 29, 31, 43, 47, 59, 61, 157, 239, 251, 349, 379, 479, 491] |
|||
base = 9: [2, 3, 5, 7, 23, 29, 47] |
|||
base = 10: [2, 3, 5, 7, 23, 37, 53, 73, 373] |
|||
base = 11: [2, 3, 5, 7, 29, 79] |
|||
base = 12: [2, 3, 5, 7, 11, 29, 31, 41, 43, 47, 67, 71, 89, 137, 139, 359, 499, 503, 521, 569, 571, 809, 857, 859, 6043] |
|||
base = 13: [2, 3, 5, 7, 11, 29, 31, 37, 41, 67, 379] |
|||
base = 14: [2, 3, 5, 7, 11, 13, 31, 41, 47, 53, 73, 83, 101, 103, 109, 157, 167, 193, 439, 661, 1033, 2203] |
|||
base = 15: [2, 3, 5, 7, 11, 13, 37, 41, 43, 47, 107, 167, 197, 557, 617, 647] |
|||
base = 16: [2, 3, 5, 7, 11, 13, 37, 43, 53, 59, 61, 83, 179, 181, 211, 691, 947, 3389] |
|||
base = 17: [2, 3, 5, 7, 11, 13, 37, 41, 47, 53, 223, 631] |
|||
base = 18: [2, 3, 5, 7, 11, 13, 17, 41, 43, 47, 53, 59, 61, 67, 71, 97, 101, 103, 107, 131, 137, 139, 211, 239, 241, 251, 311, 313, 317, 751, 787, 859, 1069, 1103, 1109, 1213, 1223, 1283, 1289, 1759, 1831, 1861, 1871, 1931, 1933, 2371, 3803, 4349, 4523, 5639, 5647, 15467, 19867, 34807] |
|||
base = 19: [2, 3, 5, 7, 11, 13, 17, 41, 43, 59, 97, 211] |
|||
base = 20: [2, 3, 5, 7, 11, 13, 17, 19, 43, 47, 53, 59, 67, 71, 73, 79, 103, 107, 113, 151, 157, 223, 227, 233, 239, 263, 271, 277, 347, 353, 359, 383, 397, 1063, 1423, 1427, 1433, 1439, 1471, 1583, 1597, 3023, 4663, 4783, 5273, 5279, 7673, 28663] |
|||
</pre> |
</pre> |
||