experimental-projects/oeis-research/Derek Orr/Least number k such that k^n and k^n-1 contain the same number of prime factors (counted with multiplicity) or 0 if no such k exists/prog.sf

#!/usr/bin/ruby

# Least number k such that k^n and k^n-1 contain the same number of prime factors (counted with multiplicity) or 0 if no such k exists.
# https://oeis.org/A241793

# Known terms:
#   3, 34, 5, 15, 17, 55, 79, 5, 53, 23, 337, 13, 601, 79, 241, 41, 18433, 31, 40961, 89, 3313, 1153

# Lower-bounds:
#   a(23) > 206593

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(m, from=2) {
    for k in (from..Inf) {

        var n = bigomega(k)*m
        var v = (k**m - 1)

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

        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 ff = v.special_factor
        check_partial_factors(ff, n) || next

        var sf = []
        if (v % (k-1) == 0) {
            sf = gcd_factors(v, tf + ff + factordb(v/(k-1)))
            check_partial_factors(sf, n) || next
        }

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

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

        if ((f3.last > 1e65) && f3.last.is_composite) {
            tf = v.trial_factor(1e9)
            check_partial_factors(tf, n) || next
            tf.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.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.len == n) {
            return k
        }
    }
}

var from = 206593+1

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