login
Numbers m such that m^2 + 1 has at most 2 prime factors.
0

%I #43 Apr 07 2020 21:57:17

%S 1,2,3,4,5,6,8,9,10,11,12,14,15,16,19,20,22,24,25,26,28,29,30,34,35,

%T 36,39,40,42,44,45,46,48,49,50,51,52,54,56,58,59,60,61,62,64,65,66,69,

%U 71,74,76,78,79,80,84,85,86,88,90,92,94,95,96,100

%N Numbers m such that m^2 + 1 has at most 2 prime factors.

%C Equivalently, numbers m such that m^2 + 1 is prime or semiprime.

%C Henryk Iwaniec proved in 1978 that this sequence is infinite (see link). By contrast, it is not known whether there are infinitely many primes of the form m^2 + 1 (or infinitely many semiprimes of that form).

%C The integers that have at most 2 prime factors counted with multiplicity are called almost-primes of order 2 and they are in A037143. Here, as m^2 + 1 is not a square for m > 0, all the semiprimes of this form have two distinct prime factors (A144255), and with the primes of the form m^2 + 1 (A002496), they constitute A248742.

%D R. K. Guy, Unsolved Problems in Number Theory, A1.

%H Henryk Iwaniec, <a href="http://dx.doi.org/10.1007/BF01578070">Almost-primes represented by quadratic polynomials</a>, Inventiones Mathematicae 47 (2) (1978), pp. 171-188.

%e 10^2 + 1 = 101, which is prime, so 10 is in the sequence.

%e 11^2 + 1 = 122 = 2 * 61, so 11 is in the sequence.

%e 12^2 + 1 = 145 = 5 * 29, so 12 is in the sequence.

%e 13^2 + 1 = 170 = 2 * 5 * 17, so 13 is not in the sequence.

%t Select[Range[100], PrimeQ[(k = #^2 + 1)] || PrimeOmega[k] == 2 &] (* _Amiram Eldar_, Mar 30 2020 *)

%Y Union of A005574 and A085722.

%Y Cf. A002496 (m^2 + 1 is prime), A005574 (corresponding m).

%Y Cf. A144255 (m^2 + 1 is semiprime), A085722 (corresponding m).

%Y Cf. A248742 (m^2 + 1 is prime or semiprime), this sequence (corresponding m).

%Y Cf. A037143 (numbers with at most 2 prime factors counted with multiplicity).

%K nonn

%O 1,2

%A _Bernard Schott_, Mar 30 2020