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

%I #60 Jul 25 2024 11:18:31

%S 0,1,3,13,47,447,2163,24263,241727,2923783,16485763,169053487,

%T 4535472963,36316463227,879728844873,4476534430363,119919330795347,

%U 1374445897718223,106298577886531087

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

%F a(n) >= sqrt(A185952(n)-1). - _Charles R Greathouse IV_, Feb 17 2015

%F a(n) <= A164511(n). - _Daniel Suteu_, Feb 20 2023

%e a(2) = 3 because the 2 distinct prime factors of 3^2 + 1 are {2, 5};

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

%t 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 *)

%o (Python)

%o from itertools import count

%o from sympy import factorint

%o def A180278(n):

%o return next(k for k in count() if len(factorint(k**2+1)) == n) # _Pontus von Brömssen_, Sep 12 2023

%o (PARI) a(n)=for(k=0, oo, if(omega(k^2+1) == n, return(k))) \\ _Andrew Howroyd_, Sep 12 2023

%Y Cf. A001221, A002144, A002522, A128428, A164511, A185952, A219017, A219108, A257366.

%K nonn,hard,more

%O 0,3

%A _Michel Lagneau_, Jan 17 2011

%E a(9), a(10) and example corrected; a(11) added by _Donovan Johnson_, Aug 27 2012

%E a(12) from _Giovanni Resta_, May 10 2017

%E a(13)-a(17) from _Daniel Suteu_, Feb 20 2023

%E Name clarified and incorrect programs removed by _Pontus von Brömssen_, Sep 12 2023

%E a(18) from _Max Alekseyev_, Feb 24 2024