cp's OEIS Frontend

A174967 Smallest number of the form k^2 + k + 1 with n distinct prime divisors.

%I A174967 #36 May 25 2023 01:27:58
%S A174967 1,3,21,273,10101,316407,6914271,2424626841,346084535811,
%T A174967 6177672967557,1741866776384007,92264158181274807,
%U A174967 103008522046409631057,22810816825458528984663,2220066397007943013450011,545889722100356705628041121,73293936170018923619553695493
%N A174967 Smallest number of the form k^2 + k + 1 with n distinct prime divisors.
%C A174967 If k == 2 (mod 3), all prime divisors of k^2 + k + 1 are congruent to 1 (mod 3), and if k == 1 (mod 3), the number 3 is divisor, and the other divisors are congruent to 1 (mod 3).
%C A174967 Proof: first case: k == 2 (mod 3): let q divide k^2 + k + 1. Then 4q divides 4*(k^2 + k + 1) = (2k+1)^2 + 3, and (-3/q)=1, where (a/b) is the Legendre symbol. By using the law of quadratic reciprocity, we obtain (-3/q) = (-1/q)(3/q) = (-1/q)(q/3)(-1)^((q-1)/2)(3-1)/2)) = ((-1)^(q-1)/2)((-1)^(q-1)/2)(q/3) = (q/3). Suppose q !== 1 (mod 3). Then k^2 + k + 1 !== 0 (mod 3) => q == 2 (mod 3), and then (q/3) = -1 => (-3/q) = -1, a contradiction. So q == 1 (mod 3).
%C A174967 Second case: k == 1 (mod 3) => 3 is divisor of k^2 + k + 1, and the other divisors q == 1 (mod 3).
%C A174967 a(11) <= 4943071434145592163, a(12) <= 2702887058650660754061, a(13) <= 896265629366361887178273, a(14) <= 72053193593257327979705541. - _Michael S. Branicky_, Mar 21 2021
%C A174967 Is a(n) squarefree? The first 16 terms are. - _David A. Corneth_, Mar 21 2021
%D A174967 L. Poletti, Le serie dei numeri primi appartenente alle due forme quadratiche (A) n^2+n+1 e (B) n^2+n-1 per l'intervallo compreso entro 121 milioni, e cioè per tutti i valori di n fino a 11000, Atti della Reale Accademia Nazionale dei Lincei, Memorie della Classe di Scienze Fisiche, Matematiche e Naturali, s. 6, v. 3 (1929), pages 193-218.
%e A174967 21 = 3*7;
%e A174967 273 = 3*7*13;
%e A174967 10101 = 3*7*13*37;
%e A174967 316407 = 3*7*13*19*61;
%e A174967 6914271 = 3*7*13*19*31*43;
%e A174967 2424626841 = 3*7*13*19*61*79*97;
%e A174967 346084535811 = 3*7*19*37*43*67*79*103;
%e A174967 6177672967557 = 3*7*13*19*31*43*61*97*151;
%e A174967 1741866776384007 = 3*7*13*19*31*37*43*67*151*673.
%p A174967 A174967 := proc(n)
%p A174967         for k from 1 do
%p A174967                 a := k^2+k+1 ;
%p A174967                 if A001221(a) = n then
%p A174967                         return a;
%p A174967                 end if;
%p A174967         end do:
%p A174967 end proc: # _R. J. Mathar_, Jul 06 2012
%o A174967 (Python)
%o A174967 from sympy import primefactors
%o A174967 def a(n):
%o A174967   k = 1
%o A174967   while len(primefactors(k**2 + k + 1)) != n: k += 1
%o A174967   return k**2 + k + 1
%o A174967 print([a(n) for n in range(1, 8)]) # _Michael S. Branicky_, Mar 21 2021
%Y A174967 Cf. A002384, A002383.
%K A174967 nonn
%O A174967 0,2
%A A174967 _Michel Lagneau_, Apr 02 2010
%E A174967 a(10) from _Michael S. Branicky_, Mar 21 2021
%E A174967 a(0), a(11)-a(16) from _David A. Corneth_, Mar 21 2021