prog2.sf

#!/usr/bin/ruby

# Least positive k such that n*k^k - 1 is a prime, or 0 if no such k exists.
# https://oeis.org/A231735

# Known terms:
#   2, 2, 1, 1, 2, 1, 1128, 1, 0, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 14, 1, 0, 2, 2, 6, 206, 1, 1590, 1, 2, 11, 2, 3

# From Gordon Atkinson, Aug 20 2019:
#   For all odd numbers n>3, a(n) is even.
#   For all odd numbers n>1, a(n^2) = 0.

# ((2*n+1)^2 * (2*k)^(2*k) - 1)     = (2^(k+1) * k^k * n + 2^k * k^k - 1) * (2^(k+1) * k^k * n + 2^k * k^k + 1)
# ((2*n+1)^2 * (2*k+1)^(2*k+1) - 1) = 8*k * (2*k + 1)^(2*k) * n^2 + 4*(2*k + 1)^(2*k) * n^2 + 8*k * (2*k+1)^(2*k)*n + 4*(2*k+1)^(2*k)*n + 2*k*(2*k+1)^(2*k) + (2*k+1)^(2*k) - 1

func a(n) {
    n.is_square && n.isqrt.is_odd && return 0

    1..Inf -> first {|k|
        is_prob_prime(n * k**k - 1)
    }
}

# a(37) >= 9114
# a(43) >= 4704
# a(46) >= 1380

# Terms 38..42:
#   1, 6, 6, 2, 1

# Terms 44..45
#   1, 2

38..42 -> map(a).say
44..45 -> map(a).say

#__END__

func b(n, from = 1) {

    for k in (from .. 1e6 `by` 2) {
        say "Testing: #{k}"
        if (is_prob_prime(k**k * n - 1)) {
            die "Found: #{k}"
        }
    }
}

b(37, 9114)
#b(43, 4704)
#b(46, 1380)