prog.sf

#!/usr/bin/ruby

# Smallest number k such that k^n + 1 contains n distinct prime divisors.
# https://oeis.org/A219018

# Known terms:
#   1, 3, 5, 43, 17, 47, 51, 1697, 59, 512, 521, 3255

# New terms (a(13)-a(15)):
#   1, 3, 5, 43, 17, 47, 51, 1697, 59, 512, 521, 3255, 8189, 18951, 656

# Lower-bounds:
#   a(16) > 1296846

include("../../../factordb/auto.sf")

Num!VERBOSE = true

func check_partial_factors(f,n) {

    f.uniq.sum {|p| p.is_prime ? 1 : 2 } > n && return false

    if (f.all_prime) {
        if (f.uniq.len == n) {
            return true
        }
        return false
    }

    return true
}

func a(n, from=2) {
    for k in (from .. Inf) {

        var v = (k**n + 1)

        say "[#{n}] Checking: #{k}"

        var tf = v.trial_factor(1e6)
        check_partial_factors(tf, n) || next
        tf.uniq.len.dec + tf.last.ilog(1e6) + 1 >= n || next

        tf = v.trial_factor(1e7)
        check_partial_factors(tf, n) || next
        tf.uniq.len.dec + tf.last.ilog(1e7) + 1 >= n || next

        if (tf.last > 1e65) {
            tf = v.trial_factor(1e8)
            check_partial_factors(tf, n) || next
            tf.uniq.len.dec + tf.last.ilog(1e8) + 1 >= n || next
        }

        say "Many factors (at least #{tf.uniq.len-1 + (tf.last.is_prime ? 1 : 2)} with C#{tf.last.len}): #{v}"

        var ff = v.special_factor
        check_partial_factors(ff, n) || next

        var f = factordb(v)
        check_partial_factors(f, n) || next

        var f3 = gcd_factors(v, tf + ff + f)
        check_partial_factors(f3, n) || next

        if ((f3.last > 1e70) && f3.last.is_composite) {
            tf = v.trial_factor(1e9)
            check_partial_factors(tf, n) || next
            tf.uniq.len.dec + tf.last.ilog(1e9) + 1 >= n || next

            say "Strong candidate..."

            f3 = gcd_factors(v, tf + ff + f)
            check_partial_factors(f3, n) || next

            var pf = f3.grep{.is_prime}
            var c = (v / pf.prod)
            pf.uniq.len + c.ilog(1e9) + 1 >= n || next

            say "Factoring C#{c.len}: #{c}"
        }

        f3 = f3.map{ .is_prime ? _ : factordb(_) }.flat
        check_partial_factors(f3, n) || next

        f3 = f3.map{ .factor }.flat
        check_partial_factors(f3, n) || next

        if (f3.uniq.len == n) {
            return k
        }
    }
}

var n = 16
var from = 1296892

say "a(#{n}) = #{a(n, from)}"