A002144 - OEIS

%I M3823 N1566 #465 Oct 09 2024 04:32:58

%S 5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193,

%T 197,229,233,241,257,269,277,281,293,313,317,337,349,353,373,389,397,

%U 401,409,421,433,449,457,461,509,521,541,557,569,577,593,601,613,617

%N Pythagorean primes: primes of the form 4*k + 1.

%C Rational primes that decompose in the field Q(sqrt(-1)). - _N. J. A. Sloane_, Dec 25 2017

%C These are the prime terms of A009003.

%C -1 is a quadratic residue mod a prime p if and only if p is in this sequence.

%C Sin(a(n)*Pi/2) = 1 with Pi = 3.1415..., see A070750. - _Reinhard Zumkeller_, May 04 2002

%C If at least one of the odd primes p, q belongs to the sequence, then either both or neither of the congruences x^2 = p (mod q), x^2 = q (mod p) are solvable, according to Gauss reciprocity law. - _Lekraj Beedassy_, Jul 17 2003

%C Odd primes such that binomial(p-1, (p-1)/2) == 1 (mod p). - _Benoit Cloitre_, Feb 07 2004

%C Primes that are the hypotenuse of a right triangle with integer sides. The Pythagorean triple is {A002365(n), A002366(n), a(n)}.

%C Also, primes of the form a^k + b^k, k > 1. - _Amarnath Murthy_, Nov 17 2003

%C The square of a(n) is the average of two other squares. This fact gives rise to a class of monic polynomials x^2 + bx + c with b = a(n) that will factor over the integers regardless of the sign of c. See A114200. - Owen Mertens (owenmertens(AT)missouristate.edu), Nov 16 2005

%C Also such primes p that the last digit is always 1 for the Nexus numbers of form n^p - (n-1)^p. - _Alexander Adamchuk_, Aug 10 2006

%C The set of Pythagorean primes is a proper subset of the set of positive fundamental discriminants (A003658). - _Paul Muljadi_, Mar 28 2008

%C A079260(a(n)) = 1; complement of A137409. - _Reinhard Zumkeller_, Oct 11 2008

%C From _Artur Jasinski_, Dec 10 2008: (Start)

%C If we take 4 numbers: 1, A002314(n), A152676(n), A152680(n) then multiplication table modulo a(n) is isomorphic to the Latin square:

%C    1 2 3 4

%C    2 4 1 3

%C    3 1 4 2

%C    4 3 2 1

%C and isomorphic to the multiplication table of {1, i, -i, -1} where i is sqrt(-1), A152680(n) is isomorphic to -1, A002314(n) with i or -i and A152676(n) vice versa -i or i. 1, A002314(n), A152676(n), A152680(n) are subfield of Galois field [a(n)]. (End)

%C Primes p such that the arithmetic mean of divisors of p^3 is an integer. There are 2 sequences of such primes: this one and A002145. - _Ctibor O. Zizka_, Oct 20 2009

%C Equivalently, the primes p for which the smallest extension of F_p containing the square roots of unity (necessarily F_p) contains the 4th roots of unity. In this respect, the n = 2 case of a family of sequences: see n=3 (A129805) and n=5 (A172469). - _Katherine E. Stange_, Feb 03 2010

%C Subsequence of A007969. - _Reinhard Zumkeller_, Jun 18 2011

%C A151763(a(n)) = 1.

%C k^k - 1 is divisible by 4*k + 1 if 4*k + 1 is a prime (see Dickson reference). - _Gary Detlefs_, May 22 2013

%C Not only are the squares of these primes the sum of two nonzero squares, but the primes themselves are also. 2 is the only prime equal to the sum of two nonzero squares and whose square is not. 2 is therefore not a Pythagorean prime. - _Jean-Christophe Hervé_, Nov 10 2013

%C The statement that these primes are the sum of two nonzero squares follows from Fermat's theorem on the sum of two squares. - _Jerzy R Borysowicz_, Jan 02 2019

%C The decompositions of the prime and its square into two nonzero squares are unique. - _Jean-Christophe Hervé_, Nov 11 2013. See the Dickson reference, Vol. II, (B) on p. 227. - _Wolfdieter Lang_, Jan 13 2015

%C p^e for p prime of the form 4*k+1 and e >= 1 is the sum of 2 nonzero squares. - _Jon Perry_, Nov 23 2014

%C Primes p such that the area of the isosceles triangle of sides (p, p, q) for some integer q is an integer. - _Michel Lagneau_, Dec 31 2014

%C This is the set of all primes that are the average of two squares. - _Richard R. Forberg_, Mar 01 2015

%C Numbers k such that ((k-3)!!)^2 == -1 (mod k). - _Thomas Ordowski_, Jul 28 2016

%C This is a subsequence of primes of A004431 and also of A016813. - _Bernard Schott_, Apr 30 2022

%C In addition to the comment from _Jean-Christophe Hervé_, Nov 10 2013: All powers as well as the products of any of these primes are the sum of two nonzero squares. They are terms of A001481, which is closed under multiplication. - _Klaus Purath_, Nov 19 2023

%D David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.

%D L. E. Dickson, "History of the Theory of Numbers", Chelsea Publishing Company, 1919, Vol I, page 386

%D L. E. Dickson, History of the Theory of Numbers, Carnegie Institution, Publ. No. 256, Vol. II, Washington D.C., 1920, p. 227.

%D M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 76.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 90.

%H Zak Seidov, <a href="/A002144/b002144.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972.

%H Peter R. J. Asveld, <a href="http://doc.utwente.nl/66184/1/1988m20.pdf">On a Post's System of Tag</a>. Bulletin of the EATCS 36 (1988), 96-102.

%H C. Banderier, <a href="https://web.archive.org/web/20060217222242/http://algo.inria.fr/banderier/Recipro/node14.html">Calcul de (-1/p)</a>.

%H J. Butcher, <a href="http://www.math.auckland.ac.nz/~butcher/miniature/miniature8.pdf">Mathematical Miniature 8: The Quadratic Residue Theorem</a>, NZMS Newsletter, No. 75, April 1999.

%H Hing Lun Chan, <a href="https://arxiv.org/abs/2112.02556">Windmills of the minds: an algorithm for Fermat's Two Squares Theorem</a>, arXiv:2112.02556 [cs.LO], 2021.

%H R. Chapman, <a href="http://empslocal.ex.ac.uk/people/staff/rjchapma/courses/nt13/quadrec.pdf">Quadratic reciprocity</a>.

%H A. David Christopher, <a href="https://doi.org/10.1016/j.disc.2015.12.002">A partition-theoretic proof of Fermat's Two Squares Theorem</a>, Discrete Mathematics, Volume 339, Issue 4, 6 April 2016, Pages 1410-1411.

%H J. E. Ewell, <a href="http://www.jstor.org/stable/2323282">A Simple Proof of Fermat's Two-Square Theorem</a>, The American Mathematical Monthly, Vol. 90, No. 9 (Nov., 1983), pp. 635-637.

%H Bernard Frénicle de Bessy, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k62379s/f46.image">Traité des triangles rectangles en nombres : dans lequel plusieurs belles propriétés de ces triangles sont démontrées par de nouveaux principes</a>, Michalet, Paris (1676) pp. 0-116; see p. 44, Consequence II.

%H Bernard Frénicle de Bessy, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k5493994j/f19.image">Méthode pour trouver la solution des problèmes par les exclusions. Abrégé des combinaisons. Des Quarrez magiques</a>, in "Divers ouvrages de mathématiques et de physique, par MM. de l'Académie royale des sciences", (1693) "Troisième exemple", pp. 17-26, see in particular p. 25.

%H A. Granville and G. Martin, <a href="https://arxiv.org/abs/math/0408319">Prime number races</a>, arXiv:math/0408319 [math.NT], 2004.

%H D. & C. Hazzlewood, <a href="http://cgi.di.uoa.gr/~halatsis/Crypto/Bibliografia/Number_theory/reciprocity_theorem_node32.html">Quadratic Reciprocity</a>.

%H Ernest G. Hibbs, <a href="https://www.proquest.com/openview/4012f0286b785cd732c78eb0fc6fce80">Component Interactions of the Prime Numbers</a>, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.

%H Lucas Lacasa, Bartolome Luque, Ignacio Gómez, and Octavio Miramontes, <a href="https://arxiv.org/abs/1802.08349">On a Dynamical Approach to Some Prime Number Sequences</a>, Entropy 20.2 (2018): 131, also arXiv:1802.08349 [math.NT], 2018.

%H R. C. Laubenbacher and D. J. Pengelley, <a href="https://core-prod.cambridgecore.org/core/books/abs/who-gave-you-the-epsilon/eisensteins-misunderstood-geometric-proof-of-the-quadratic-reciprocity-theorem/268F98DBFEFF9E6FDF56C8A920972606">Eisenstein's Misunderstood Geometric Proof of the Quadratic Reciprocity Theorem</a>, In: Anderson M, Katz V, Wilson R, eds. Who Gave You the Epsilon?: And Other Tales of Mathematical History. Spectrum. Mathematical Association of America; 2009:309-312.

%H R. C. Laubenbacher and D. J. Pengelley, <a href="https://doi.org/10.1007/BF0302428">Gauss, Eisenstein and the 'third' proof of the Quadratic Reciprocity Theorem</a>, The Mathematical Intelligencer 16, 67-72 (1994).

%H K. Matthews, <a href="http://www.numbertheory.org/php/serret.html">Serret's algorithm based Server</a>.

%H Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, <a href="https://doi.org/10.7546/nntdm.2024.30.3.516-529">The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences</a>, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 521.

%H Carlos Rivera, <a href="https://www.primepuzzles.net/puzzles/puzz_968.htm">Puzzle 968. Another property of primes 4m+1</a>, The Prime Puzzles & Problems Connection.

%H D. Shanks, <a href="/A002142/a002142.pdf">Review of "K. E. Kloss et al., Class number of primes of the form 4n+1"</a>, Math. Comp., 23 (1969), 213-214. [Annotated scanned preprint of review]

%H S. A. Shirali, <a href="http://www.jstor.org/stable/2690862">A family portrait of primes-a case study in discrimination</a>, Math. Mag. Vol. 70, No. 4 (Oct., 1997), pp. 263-272.

%H Rosemary Sullivan and Neil Watling, <a href="http://www.emis.de/journals/INTEGERS/papers/n65/n65.Abstract.html">Independent divisibility pairs on the set of integers from 1 to n</a>, INTEGERS 13 (2013) #A65.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WilsonsTheorem.html">Wilson's Theorem</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PythagoreanTriple.html">Pythagorean Triples</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Quadratic_reciprocity">Quadratic reciprocity</a>

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/JacobiSymbol/31/01/ShowAll.html">The Gauss Reciprocity Law</a>.

%H G. Xiao, <a href="http://wims.unice.fr/~wims/en_tool~number~twosquares.en.html">Two squares</a>.

%H D. Zagier, <a href="http://www.jstor.org/stable/2323918">A One-Sentence Proof That Every Prime p == 1 (mod 4) Is a Sum of Two Squares</a>, Am. Math. Monthly, Vol. 97, No. 2 (Feb 1990), p. 144. [From _Wolfdieter Lang_, Jan 17 2015 (thanks to Charles Nash)]

%H <a href="https://oeis.org/index/Pri#primes_decomp_of">Index to sequences related to decomposition of primes in quadratic fields</a>.

%F Odd primes of form x^2 + y^2, (x=A002331, y=A002330, with x < y) or of form u^2 + 4*v^2, (u = A002972, v = A002973, with u odd). - _Lekraj Beedassy_, Jul 16 2004

%F p^2 - 1 = 12*Sum_{i = 0..floor(p/4)} floor(sqrt(i*p)) where p = a(n) = 4*n + 1. [Shirali]

%F a(n) = A000290(A002972(n)) + A000290(2*A002973(n)) = A000290(A002331(n+1)) + A000290(A002330(n+1)). - _Reinhard Zumkeller_, Feb 16 2010

%F a(n) = A002972(n)^2 + (2*A002973(n))^2, n >= 1. See the _Jean-Christophe Hervé_ Nov 11 2013 comment. - _Wolfdieter Lang_, Jan 13 2015

%F a(n) = 4*A005098(n) + 1. - _Zak Seidov_, Sep 16 2018

%F From _Vaclav Kotesovec_, Apr 30 2020: (Start)

%F Product_{k>=1} (1 - 1/a(k)^2) = A088539.

%F Product_{k>=1} (1 + 1/a(k)^2) = A243380.

%F Product_{k>=1} (1 - 1/a(k)^3) = A334425.

%F Product_{k>=1} (1 + 1/a(k)^3) = A334424.

%F Product_{k>=1} (1 - 1/a(k)^4) = A334446.

%F Product_{k>=1} (1 + 1/a(k)^4) = A334445.

%F Product_{k>=1} (1 - 1/a(k)^5) = A334450.

%F Product_{k>=1} (1 + 1/a(k)^5) = A334449. (End)

%F From _Vaclav Kotesovec_, May 05 2020: (Start)

%F Product_{k>=1} (1 + 1/A002145(k)) / (1 + 1/a(k)) = Pi/(4*A064533^2) = 1.3447728438248695625516649942427635670667319092323632111110962...

%F Product_{k>=1} (1 - 1/A002145(k)) / (1 - 1/a(k)) = Pi/(8*A064533^2) = 0.6723864219124347812758324971213817835333659546161816055555481... (End)

%F Sum_{k >= 1} 1/a(k)^s = (1/2) * Sum_{n >= 1 odd numbers} moebius(n) * log((2*n*s)! * zeta(n*s) * abs(EulerE(n*s - 1)) / (Pi^(n*s) * 2^(2*n*s) * BernoulliB(2*n*s) * (2^(n*s) + 1) * (n*s - 1)!))/n, s >= 3 odd number. - _Dimitris Valianatos_, May 21 2020

%F Legendre symbol (-1, a(n)) = +1, for n >= 1. - _Wolfdieter Lang_, Mar 03 2021

%e The following table shows the relationship between several closely related sequences:

%e Here p = A002144 = primes == 1 (mod 4), p = a^2+b^2 with a < b;

%e a = A002331, b = A002330, t_1 = ab/2 = A070151;

%e p^2 = c^2 + d^2 with c < d; c = A002366, d = A002365,

%e t_2 = 2ab = A145046, t_3 = b^2 - a^2 = A070079,

%e with {c,d} = {t_2, t_3}, t_4 = cd/2 = ab(b^2-a^2).

%e   ---------------------------------

%e    p  a  b  t_1  c   d t_2 t_3  t_4

%e   ---------------------------------

%e    5  1  2   1   3   4   4   3    6

%e   13  2  3   3   5  12  12   5   30

%e   17  1  4   2   8  15   8  15   60

%e   29  2  5   5  20  21  20  21  210

%e   37  1  6   3  12  35  12  35  210

%e   41  4  5  10   9  40  40   9  180

%e   53  2  7   7  28  45  28  45  630

%e   ...

%e a(7) = 53 = A002972(7)^2 + (2*A002973(7))^2 = 7^2 + (2*1)^2 = 49 + 4, and this is the only way. - _Wolfdieter Lang_, Jan 13 2015

%p a := []; for n from 1 to 500 do if isprime(4*n+1) then a := [op(a),4*n+1]; fi; od: A002144 := n->a[n];

%p # alternative

%p A002144 := proc(n)

%p     option remember ;

%p     local a;

%p     if n = 1 then

%p         5;

%p     else

%p         for a from procname(n-1)+4 by 4 do

%p             if isprime(a) then

%p                 return a;

%p             end if;

%p         end do:

%p     end if;

%p end proc:

%p seq(A002144(n),n=1..100) ; # _R. J. Mathar_, Jan 31 2024

%t Select[4*Range[140] + 1, PrimeQ[ # ] &] (* _Stefan Steinerberger_, Apr 16 2006 *)

%t Select[Prime[Range[150]],Mod[#,4]==1&] (* _Harvey P. Dale_, Jan 28 2021 *)

%o (Haskell)

%o a002144 n = a002144_list !! (n-1)

%o a002144_list = filter ((== 1) . a010051) [1,5..]

%o -- _Reinhard Zumkeller_, Mar 06 2012, Feb 22 2011

%o (Magma) [a: n in [0..200] | IsPrime(a) where a is 4*n + 1 ]; // _Vincenzo Librandi_, Nov 23 2014

%o (PARI) select(p->p%4==1,primes(1000))

%o (PARI)

%o A002144_next(p=A2144[#A2144])={until(isprime(p+=4),);p} /* NB: p must be of the form 4k+1. Beyond primelimit, this is *much* faster than forprime(p=...,, p%4==1 && return(p)). */

%o A2144=List(5); A002144(n)={while(#A2144<n, listput(A2144, A002144_next())); A2144[n]}

%o \\ _M. F. Hasler_, Jul 06 2024

%o (Python)

%o from sympy import prime

%o A002144 = [n for n in (prime(x) for x in range(1,10**3)) if not (n-1) % 4]

%o # _Chai Wah Wu_, Sep 01 2014

%o (Python)

%o from sympy import isprime

%o print(list(filter(isprime, range(1, 618, 4)))) # _Michael S. Branicky_, May 13 2021

%o (SageMath)

%o def A002144_list(n): # returns all Pythagorean primes <= n

%o     return [x for x in prime_range(5,n+1) if x % 4 == 1]

%o A002144_list(617) # _Peter Luschny_, Sep 12 2012

%Y Cf. A002145, A002314, A002476, A002972, A002973, A003658, A004431, A007519, A010051, A016813, A076339, A094407.

%Y Cf. A114200, A133870, A142925, A152676, A152680, A173330, A173331, A208177, A208178, A334912.

%Y Cf. A004613 (multiplicative closure).

%Y Apart from initial term, same as A002313.

%Y For values of n see A005098.

%Y Primes in A020668.

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_