sidef-scripts/Math/substring_primes_in_base_n.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 05 July 2021
# https://github.com/trizen

# Generate all the primes such that all substrings (in a given base) are also primes.

# See also:
#   https://oeis.org/A085823
#   https://rosettacode.org/wiki/Substring_primes

func split_at_indices(array, indices) {

    var parts = []
    var i = 0

    for j in (indices) {
        parts << array.slice(i, j+1)
        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]

    digits.each {|d|
        var num = (p*base + d)
        if (is_prime(num) && is_substring_prime(num.digits(base), base)) {
            seq << __FUNC__(num, base, digits)...
        }
    }

    return seq
}

func substring_primes(base) {     # finite sequence for each base

    var prime_digits = (base-1 -> primes)   # prime digits < base

    prime_digits.map  {|p| generate_from_prefix(p, base, prime_digits)... }\
                .sort
}

for base in (2..20) {
    say "base = #{base}: #{substring_primes(base)}"
}

__END__
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]
base = 21: [2, 3, 5, 7, 11, 13, 17, 19, 47, 53, 59, 61, 107, 149, 233, 359, 401, 1283]
base = 22: [2, 3, 5, 7, 11, 13, 17, 19, 47, 61, 71, 73, 79, 83, 113, 127, 157, 167, 173, 293, 379, 421, 431, 1039, 1051, 1579, 1609, 1619, 1831, 2503, 3461, 3467, 6449]
base = 23: [2, 3, 5, 7, 11, 13, 17, 19, 53, 59, 71, 163, 439]
base = 24: [2, 3, 5, 7, 11, 13, 17, 19, 23, 53, 59, 61, 67, 71, 79, 83, 89, 127, 131, 137, 139, 173, 179, 181, 191, 269, 271, 277, 281, 283, 317, 331, 419, 421, 431, 461, 463, 467, 479, 557, 563, 569, 571, 1279, 1283, 1289, 1291, 1423, 1429, 1433, 1483, 1613, 1619, 1709, 1721, 1723, 1901, 1907, 1997, 1999, 2011, 3061, 3163, 3299, 3301, 3343, 3347, 3359, 4159, 4349, 4363, 4603, 6473, 6653, 6803, 7949, 7951, 10061, 10069, 11071, 11083, 11117, 11213, 13669, 13679, 13709, 13711, 30949, 34301, 35597, 38861, 41357, 45631, 73483, 79181, 99829, 104717, 110477, 110479, 190783, 190829, 265717, 266003]
base = 25: [2, 3, 5, 7, 11, 13, 17, 19, 23, 53, 61, 67, 73, 127, 277, 577]
base = 26: [2, 3, 5, 7, 11, 13, 17, 19, 23, 59, 71, 83, 89, 97, 101, 137, 149, 193, 199, 293, 349, 449, 461, 499, 601, 617, 15649]
base = 27: [2, 3, 5, 7, 11, 13, 17, 19, 23, 59, 61, 67, 71, 73, 83, 137, 191, 353, 461, 1811]
base = 28: [2, 3, 5, 7, 11, 13, 17, 19, 23, 59, 61, 67, 73, 79, 89, 97, 101, 103, 107, 151, 157, 163, 199, 311, 313, 331, 367, 383, 479, 487, 499, 647, 661, 1657, 1669, 1879, 2503, 2719, 2851, 2999, 4231, 4567, 5591, 8713, 8731, 10289, 13417, 18121, 18133, 244471]
base = 29: [2, 3, 5, 7, 11, 13, 17, 19, 23, 61, 71, 89, 379]
base = 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 157, 163, 167, 173, 179, 223, 227, 229, 233, 239, 337, 347, 349, 353, 359, 397, 401, 409, 419, 521, 523, 577, 587, 593, 599, 701, 709, 719, 877, 881, 883, 887, 2027, 2029, 2039, 2137, 2153, 2377, 2393, 2399, 2677, 2683, 2687, 2927, 2939, 3037, 3049, 3109, 3119, 3221, 3299, 4723, 4729, 4733, 4909, 4919, 5021, 5023, 5209, 5381, 5387, 6701, 6709, 6719, 6823, 6899, 7001, 7019, 7177, 7187, 10133, 10139, 10477, 10487, 10499, 10601, 10781, 11923, 11927, 11933, 11939, 12037, 12049, 12277, 12577, 12583, 15647, 15649, 17327, 17333, 17623, 17977, 17981, 17987, 21059, 21277, 21577, 21587, 26339, 26437, 26449, 26459, 26497, 26501, 60899, 64601, 71327, 71333, 71987, 88177, 91139, 91499, 98981, 141709, 141719, 142019, 147583, 150649, 161459, 201037, 201049, 201577, 314623, 357823, 361499, 368327, 377339, 469487, 520019, 539339, 539449, 638327, 793139, 793487, 794923, 6031499, 16183487, 23804623, 485504623]
base = 31: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 67, 73, 79, 157]
base = 32: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 67, 71, 83, 101, 103, 107, 109, 113, 127, 163, 167, 173, 179, 191, 227, 229, 241, 359, 383, 419, 421, 433, 439, 547, 557, 563, 613, 619, 631, 739, 743, 941, 947, 997, 1009, 1021, 2161, 3251, 3299, 3301, 3313, 3491, 3511, 4093, 5227, 5233, 5347, 7331, 11491, 13421, 13859, 14051, 17509, 17827, 31907]
base = 33: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 71, 73, 79, 83, 89, 97, 101, 167, 233, 431, 563, 761, 2411, 2609, 2741, 2939]
base = 34: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 71, 73, 79, 97, 107, 109, 113, 131, 173, 181, 193, 199, 241, 251, 257, 269, 379, 397, 449, 461, 601, 607, 653, 659, 677, 787, 811, 991, 997, 1009, 1061, 3709, 3719, 3847, 12889, 15269]
base = 35: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 73, 83, 89, 101, 107, 457, 1087, 2557]
base = 36: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 79, 83, 89, 101, 103, 113, 127, 131, 137, 139, 191, 193, 197, 199, 211, 257, 263, 269, 271, 281, 283, 401, 409, 419, 479, 487, 491, 499, 617, 619, 631, 641, 643, 691, 701, 839, 857, 859, 1049, 1051, 1061, 1063, 1123, 1129, 2861, 3001, 3011, 3209, 3643, 4079, 4099, 4937, 4951, 5011, 6899, 6959, 6967, 6971, 7121, 7603, 9283, 9473, 9491, 9689, 10133, 14447, 14449, 14747, 17257, 17539, 17707, 17971, 17977, 22229, 22303, 23081, 24907, 25243, 30859, 30869, 30871, 30931, 30937, 37781, 37783, 37847, 37853, 38201, 40433, 40459, 103001, 147571, 273739, 341041, 637459, 1111289, 1113521, 22948529]