prog.sf

#!/usr/bin/ruby

# a(n) is the smallest number k > 0 such that bigomega(k^n + 1) = n.
# https://oeis.org/A368162

# Known terms:
#   1, 3, 3, 43, 7, 32, 23, 643, 17, 207, 251, 3255, 255, 1568, 107

# a(16) <= 206874667; a(17) = 4095; a(18) = 6272; a(19) = 29951; a(21) = 1151.

# Conjectured lower-bounds:
#   a(16) > 947362
#   a(20) > 538362

# Lower-bounds:
#   a(22) > 79012
#   a(23) > 173610
#   a(24) > 119472

# Upper-bounds:
#   a(19) <= 48383

# New terms:
#   a(19) = 29951

Num!VERBOSE=true
Num!USE_FACTORDB=true
Num!USE_CONJECTURES=true

func a(n, from=1) {
    for k in (from..Inf) {
        #is_prob_squarefree(k**n + 1, 1e3) && next
        say "[#{n}] Testing: #{k}"
        if (is_almost_prime(k**n + 1, n)) {
            say "a(#{n}) = #{k}"
            return k
        }
    }
}

say a(20)

__END__
[19] Testing: 29951
pbrent_factor(r, 200): 191
ecm_factor(r, 1629, 10): 24473
ecm_factor(r, 1629, 10): 100207
ecm_factor(r, 1629, 10): 186049
ecm_factor(r, 1629, 10): 604733
ecm_factor(r, 1629, 10): 17422963
ecm_factor(r, 1629, 10): 1064486310867809
a(19) = 29951
29951
sidef -N  prog.sf  43.61s user 1.39s system 77% cpu 57.929 total