A180278 Smallest nonnegative integer k such that k^2 + 1 has exactly n distinct prime factors.

0, 1, 3, 13, 47, 447, 2163, 24263, 241727, 2923783, 16485763, 169053487, 4535472963, 36316463227, 879728844873, 4476534430363, 119919330795347, 1374445897718223, 106298577886531087

Offset

0,3

Comments

a(12) <= 5755933903. - Donovan Johnson, Aug 27 2012

Links

Table of n, a(n) for n=0..18.

Formula

a(n) >= sqrt(A185952(n)-1). - Charles R Greathouse IV, Feb 17 2015

a(n) <= A164511(n). - Daniel Suteu, Feb 20 2023

Example

a(2) = 3 because the 2 distinct prime factors of 3^2 + 1 are {2, 5};
a(10) = 16485763 because the 10 distinct prime factors of 16485763^2 + 1 are {2, 5, 13, 17, 29, 37, 41, 73, 149, 257}.

Mathematica

a[n_] := a[n] = Module[{k = 1}, If[n == 0, Return[0]]; Monitor[While[PrimeNu[k^2 + 1] != n, k++]; k, {n, k}]]; Table[a[n], {n, 0, 8}] (* Robert P. P. McKone, Sep 13 2023 *)

Prog

(Python)
from itertools import count
from sympy import factorint
def A180278(n):
    return next(k for k in count() if len(factorint(k**2+1)) == n) # Pontus von Brömssen, Sep 12 2023
(PARI) a(n)=for(k=0, oo, if(omega(k^2+1) == n, return(k))) \\ Andrew Howroyd, Sep 12 2023

Crossrefs

Cf. A001221, A002144, A002522, A128428, A164511, A185952, A219017, A219108.

Sequence in context: A304628 A265920 A262322 * A193164 A122424 A027326

Adjacent sequences: A180275 A180276 A180277 * A180279 A180280 A180281

Keyword

nonn,hard,more

Author

Michel Lagneau, Jan 17 2011

Extensions

a(9), a(10) and example corrected; a(11) added, Donovan Johnson, Aug 27 2012

a(12) from Giovanni Resta, May 10 2017

a(13)-a(17) from Daniel Suteu, Feb 20 2023

Name clarified and incorrect programs removed by Pontus von Brömssen, Sep 12 2023

a(18) from Max Alekseyev, Feb 24 2024

Status

approved