experimental-projects/oeis-research/Michel Lagneau/Smallest number such that k^n - 1 contains n distinct prime divisors/is_omega_prime.sf

#!/usr/bin/ruby

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

# Known terms:
#   3, 4, 7, 8, 16, 11, 79, 44, 81, 91, 1024, 47, 12769, 389, 256, 413, 46656, 373, 1048576, 1000, 4096, 43541

# New terms found:
#   12769, 389, 256, 413, 46656, 373

# PARI/GP program:
#   a(n) = my(k=2); while (omega(k^n-1) != n, k++); k;

# Lower-bounds:
#   a(19) > 632814
#   a(23) > 446082
#   a(26) > 100948
#   a(27) > 19141

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

# New term:
#   a(19) = 1048576 (confirmed by Jinyuan Wang, Feb 13 2023)

local Num!VERBOSE = true
local Num!USE_FACTORDB = true

func a(n, from=2) {
    for k in (from..Inf) {
        var t = (k**n - 1)
        say "[#{n}] Checking k = #{k}: #{t}"
        if (t.is_omega_prime(n)) {
            return k
        }
    }
}

var n = 23
var from = 446082

say a(n, from)

__END__
a(1) = 3
a(2) = 4
a(3) = 7
a(4) = 8
a(5) = 16
a(6) = 11
a(7) = 79
a(8) = 44
a(9) = 81
a(10) = 91
a(11) = 1024
a(12) = 47
a(13) = 12769
a(14) = 389
a(15) = 256
a(16) = 413
a(17) = 46656
a(18) = 373
a(19) = ?
a(20) = 1000
a(21) = 4096
a(22) = 43541
a(23) = ?
a(24) = 563
a(25) = 4096
a(26) = ?