Substring primes

Generic solution for any base >= 2.

func split_at_indices(array, indices) {
 
    var parts = []
    var i = 0
 
    for j in (indices) {
        parts << [array[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)}"
}

Output:

PreviousTop and tailNextSubtractive generator

Last updated

Was this helpful?