upper-bounds.sf

#!/usr/bin/ruby

# Least prime p such that p^n and p^n+1 have the same number of prime factors (counted with multiplicity) or 0 if no such number exists
# https://oeis.org/A242786

# Known terms:
#   2, 3, 3, 43, 7, 41, 23, 643, 17, 557, 251, 13183, 1999, 10007, 107

# Conjectured lower-bounds:
#   a(16) > 3048767

# Upper-bounds:
#   a(16) <= 206874667

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

func check_partial_factors(f,n) {

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

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

    return true
}

func a(n, from=2) {

    assert(from.is_prime)

    for (var p = from; true; p.next_prime!) {

        var v = (p**n + 1)

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

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

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

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

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

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

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

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

        if (f3.len >= 12) {
            return p
        }
    }
}

var from = 3048767.next_prime

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