prog.sf

#!/usr/bin/ruby

# a(n) is the least prime p such that the concatenation p|n has exactly n prime factors with multiplicity.
# https://oeis.org/A358596

# Known terms:
#   3, 2, 83, 2, 67, 41, 947, 4519, 15659081, 2843, 337957, 389, 1616171, 6132829, 422116888343, 24850181, 377519743, 194486417892947, 533348873, 324403, 980825013273164555563, 25691144027, 273933405157, 1238831928746353181, 311195507789, 129917586781, 2159120477658983490299

func almost_prime_numbers(a, b, k, callback) {

    a = max(2**k, a)

    var mod = 10**k.len

    func (m, lo, j) {

        var hi = idiv(b,m).iroot(j)

        if (lo > hi) {
            return nil
        }

        if (j == 1) {

            lo = max(lo, idiv_ceil(a, m))

            each_prime(lo, hi, {|p|
                var n = m*p
                var (q,r) = divmod(n, mod)
                if ((r == k) && (q.is_prime)) {
                    callback(q)
                }
            })

            return nil
        }

        each_prime(lo, hi, {|p|
            __FUNC__(m*p, p, j-1)
        })
    }(1, 2, k)

    return callback
}

func a(n) {

    var x = 2**n
    var y = 2*x

    loop {
        var arr = gather {
            almost_prime_numbers(x, y, n, { take(_) })
        }.sort
        arr && return arr[0]
        x = y+1
        y = 2*x
    }
}

for n in (1..100) {
    say "#{n} #{a(n)}"
}

__END__
1 3
2 2
3 83
4 2
5 67
6 41
7 947
8 4519
9 15659081
10 2843
11 337957
12 389
13 1616171
14 6132829