prog.sf

#!/usr/bin/ruby

# a(n) = k is the smallest number such that k^2 + 1 has n distinct prime factors.
# https://oeis.org/A180278

# Known terms:
#   0, 1, 3, 13, 47, 447, 2163, 24263, 241727, 2923783, 16485763, 169053487, 4535472963

# New terms:
#   a(13) = 36316463227
#   a(14) = 879728844873
#   a(15) = 4476534430363
#   a(16) = 119919330795347
#   a(17) = 1374445897718223

# Upper-bounds:
#   a(14) < 904648856077 < 1032304663967

#`(

# PARI/GP program:

generate(A, B, n) = A=max(A, vecprod(primes(n))); (f(m, p, j) = my(list=List()); forprime(q=p, sqrtnint(B\m, j), if(q%4 == 3, next); my(v=m*q); while(v <= B, if(j==1, if(v>=A && issquare(v-1), listput(list, sqrtint(v-1))), list=concat(list, f(v, q+1, j-1))); v *= q)); list); vecsort(Vec(f(1, 2, n)));
a(n) = if(n==0, return(1)); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=generate(x, y, n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ ~~~~

)