A122870 -id:A122870 - cp's OEIS frontend

A002145 Primes of the form 4*k + 3.

3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, 523, 547, 563, 571

Offset: 1

N. J. A. Sloane

Or, odd primes p such that -1 is not a square mod p, i.e., the Legendre symbol (-1/p) = -1. [LeVeque I, p. 66]. - N. J. A. Sloane, Jun 28 2008
Primes which are not the sum of two squares, see the comment in A022544. - Artur Jasinski, Nov 15 2006
Natural primes which are also Gaussian primes. (It is a common error to refer to this sequence as "the Gaussian primes".)
Inert rational primes in the field Q(sqrt(-1)). - N. J. A. Sloane, Dec 25 2017
Numbers n such that the product of coefficients of (2n)-th cyclotomic polynomial equals -1. - Benoit Cloitre, Oct 22 2002
For p and q both belonging to the sequence, exactly one of the congruences x^2 = p (mod q), x^2 = q (mod p) is solvable, according to Gauss reciprocity law. - Lekraj Beedassy, Jul 17 2003
Also primes p that divide L((p-1)/2) or L((p+1)/2), where L(n) = A000032(n), the Lucas numbers. Union of A122869 and A122870. - Alexander Adamchuk, Sep 16 2006
Also odd primes p that divide ((p-1)!! + 1) or ((p-2)!! + 1). - Alexander Adamchuk, Nov 30 2006
Also odd primes p that divide ((p-1)!! - 1) or ((p-2)!! - 1). - Alexander Adamchuk, Apr 18 2007
This sequence is a proper subset of the set of the absolute values of negative fundamental discriminants (A003657). - Paul Muljadi, Mar 29 2008
Bernard Frénicle de Bessy discovered that such primes cannot be the hypotenuse of a Pythagorean triangle in opposition to primes of the form 4*n+1 (see A002144). - after Paul Curtz, Sep 10 2008
A079261(a(n)) = 1; complement of A145395. - Reinhard Zumkeller, Oct 12 2008
Subsequence of A007970. - Reinhard Zumkeller, Jun 18 2011
A151763(a(n)) = -1.
Primes p such that p XOR 2 = p - 2. Brad Clardy, Oct 25 2011 (Misleading in the sense that this is a formula for the super-sequence A004767. - R. J. Mathar, Jul 28 2014)
It appears that each term of A004767 is the mean of two terms of this subsequence of primes therein; cf. A245203. - M. F. Hasler, Jul 13 2014
Numbers n > 2 such that ((n-2)!!)^2 == 1 (mod n). - Thomas Ordowski, Jul 24 2016
Odd numbers n > 1 such that ((n-1)!!)^2 == 1 (mod n). - Thomas Ordowski, Jul 25 2016
Primes p such that (p-2)!! == (p-3)!! (mod p). - Thomas Ordowski, Jul 28 2016
See Granville and Martin for a discussion of the relative numbers of primes of the form 4k+1 and 4k+3. - Editors, May 01 2017
Sometimes referred to as Blum primes for their connection to A016105 and the Blum Blum Shub generator. - Charles R Greathouse IV, Jun 14 2018
Conjecture: a(n) for n > 4 can be written as a sum of 3 primes of the form 4k+1, which would imply that primes of the form 4k+3 >= 23 can be decomposed into a sum of 6 nonzero squares. - Thomas Scheuerle, Feb 09 2023

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 146-147.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, p. 219, th. 252.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 66.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 90.

Zak Seidov, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Dario Alpern, Gaussian primes.
Lenore Blum, Manuel Blum, and Mike Shub, A simple unpredictable pseudo-random number generator, SIAM Journal on Computing 15:2 (1 May 1986), pp. 364-383.
Andrew Granville and Greg Martin, Prime number races, arXiv:math/0408319 [math.NT], 2004.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Lucas Lacasa, Bartolome Luque, Ignacio Gómez, and Octavio Miramontes, On a Dynamical Approach to Some Prime Number Sequences, Entropy 20.2 (2018): 131, also arXiv:1802.08349 [math.NT], 2018.
E. T. Ordman, Tables of the class number for negative prime discriminants, Deposited in Unpublished Mathematical Table file of Math. Comp. [Annotated scanned partial copy with notes]
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 67.
Harry J. Smith, Gaussian Primes.
Ian Stewart, The Great Mathematical Problems, 2013.
Eric Weisstein's World of Mathematics, Gaussian Prime.
Eric Weisstein's World of Mathematics, Gaussian Integer.
Wolfram Research, The Gauss Reciprocity Law.
Index entries for Gaussian integers and primes.
Index to sequences related to decomposition of primes in quadratic fields.

Cf. A000032, A002144, A003657, A085992, A122869, A122870, A334912.
Cf. A000408, A005098, A095278, A016754.
Apart from initial term, same as A045326.
Cf. A016105.
Cf. A004614 (multiplicative closure).

a002145 n = a002145_list !! (n-1)
a002145_list = filter ((== 1) . a010051) [3, 7 ..]
-- Reinhard Zumkeller, Aug 02 2015, Sep 23 2011

[4*n+3 : n in [0..142] | IsPrime(4*n+3)]; // Arkadiusz Wesolowski, Nov 15 2013

A002145 := proc(n)
    option remember;
    if n = 1 then
        3;
    else
        a := nextprime(procname(n-1)) ;
        while a mod 4 <>  3 do
            a := nextprime(a) ;
        end do;
        return a;
    end if;
end proc:
seq(A002145(n),n=1..20) ; # R. J. Mathar, Dec 08 2011

Select[4Range[150] - 1, PrimeQ] (* Alonso del Arte, Dec 19 2013 *)
Select[ Prime@ Range[2, 110], Length@ PowersRepresentations[#^2, 2, 2] == 1 &] (* or *)
Select[ Prime@ Range[2, 110], JacobiSymbol[-1, #] == -1 &] (* Robert G. Wilson v, May 11 2014 *)

forprime(p=2,1e3,if(p%4==3,print1(p", "))) \\ Charles R Greathouse IV, Jun 10 2011

def A002145_list(n): return [p for p in prime_range(1, n + 1) if p % 4 == 3]  # Peter Luschny, Jul 29 2014

Remove from A000040 terms that are in A002313.
Intersection of A000040 and A004767. - Alonso del Arte, Apr 22 2014
From Vaclav Kotesovec, Apr 30 2020: (Start)
Product_{k>=1} (1 - 1/a(k)^2) = A243379.
Product_{k>=1} (1 + 1/a(k)^2) = A243381.
Product_{k>=1} (1 - 1/a(k)^3) = A334427.
Product_{k>=1} (1 + 1/a(k)^3) = A334426.
Product_{k>=1} (1 - 1/a(k)^4) = A334448.
Product_{k>=1} (1 + 1/a(k)^4) = A334447.
Product_{k>=1} (1 - 1/a(k)^5) = A334452.
Product_{k>=1} (1 + 1/a(k)^5) = A334451. (End)
From Vaclav Kotesovec, May 05 2020: (Start)
Product_{k>=1} (1 + 1/a(k)) / (1 + 1/A002144(k)) = Pi/(4*A064533^2) = 1.3447728438248695625516649942427635670667319092323632111110962...
Product_{k>=1} (1 - 1/a(k)) / (1 - 1/A002144(k)) = Pi/(8*A064533^2) = 0.6723864219124347812758324971213817835333659546161816055555481... (End)
Sum_{k >= 1} 1/a(k)^s = (1/2) * Sum_{n >= 1 odd numbers} moebius(n) * log(2 * (2^(n*s) - 1) * (n*s - 1)! * zeta(n*s) / (Pi^(n*s) * abs(EulerE(n*s - 1))))/n, s >= 3 odd number. - Dimitris Valianatos, May 20 2020

More terms from James Sellers, Apr 21 2000

A020669 Numbers of form x^2 + 5 y^2.

Original entry on oeis.org

0, 1, 4, 5, 6, 9, 14, 16, 20, 21, 24, 25, 29, 30, 36, 41, 45, 46, 49, 54, 56, 61, 64, 69, 70, 80, 81, 84, 86, 89, 94, 96, 100, 101, 105, 109, 116, 120, 121, 125, 126, 129, 134, 141, 144, 145, 149, 150, 161, 164, 166, 169, 174, 180, 181, 184, 189, 196, 201, 205, 206, 214, 216

Offset: 1

David W. Wilson

In other words, numbers represented by quadratic form with Gram matrix [1,0; 0,5].
x^2 + 5 y^2 has discriminant -20.
A positive integer n is in this sequence if and only if the p-adic order ord_p(n) of n is even for any prime p with floor(p/10) odd, and the number of prime divisors p == 3 or 7 (mod 20) of n with ord_p(n) odd has the same parity with ord_2(n). - Zhi-Wei Sun, Mar 24 2018

H. Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. See pp. 3, 4 and later chapters.
David A. Cox, Primes of the Form x^2 + n y^2, Wiley, 1989. See Eq. (2.22), p. 33.

N. J. A. Sloane, Table of n, a(n) for n = 1..13859
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)

Cf. A033205, A106865, A154778, A216815, A122870.
For primes see A033205.
For the properly represented numbers see A344231.

[n: n in [0..216] | NormEquation(5, n) eq true]; // Arkadiusz Wesolowski, May 11 2016

select(t -> [isolve(x^2+5*y^2=t)]<>[], [$0..1000]); # Robert Israel, May 11 2016

formQ[n_] := Reduce[x >= 0 && y >= 0 && n == x^2 + 5 y^2, {x, y}, Integers] =!= False; Select[ Range[0, 300], formQ] (* Jean-François Alcover, Sep 20 2011 *)
mx = 300;
limx = Sqrt[mx]; limy = Sqrt[mx/5];
Select[
Union[
Flatten[
Table[x^2 + 5*y^2, {x, 0, limx}, {y, 0, limy}]
       ]
     ], # <= mx &
] (* T. D. Noe, Sep 20 2011 *)

List contains 0 and all positive n such that 2*A035170(n) = A028586(2n) is nonzero. - Michael Somos, Oct 21 2006

Entry revised by N. J. A. Sloane, Sep 20 2012

A106865 Primes of the form 2x^2 + 2xy + 3y^2.

Original entry on oeis.org

2, 3, 7, 23, 43, 47, 67, 83, 103, 107, 127, 163, 167, 223, 227, 263, 283, 307, 347, 367, 383, 443, 463, 467, 487, 503, 523, 547, 563, 587, 607, 643, 647, 683, 727, 743, 787, 823, 827, 863, 883, 887, 907, 947, 967, 983, 1063, 1087, 1103, 1123, 1163, 1187

Offset: 1

T. D. Noe, May 09 2005

Discriminant = -20.
Also: Primes of the form 2x^2 - 2xy + 3y^2 with x and y nonnegative. Cf. A106864.
Primes congruent to 2, 3, 7 modulo 20. - Michael Somos, Aug 13 2006
In Z[sqrt(-5)], these numbers are irreducible but not prime. In terms of ideals, they generate principal ideals that are not prime (or maximal). The equation x^2 + 5y^2 = a(n) has no solutions, but x^2 = -5 (mod a(n)) does. For example, 2 * 3 = (1 - sqrt(-5))(1 + sqrt(-5)) and 7 * 23 = (9 - 4*sqrt(-5))(9 + 4*sqrt(-5)). - Alonso del Arte, Dec 19 2015

			x = 1, y = 1 gives 2x^2 + 2xy + 3y^2 = 2 + 2 + 3 = 7.
x = 1, y = -3 gives 2x^2 + 2xy + 3y^2 = 2 - 6 + 27 = 23.

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989; see p. 33.

Vincenzo Librandi and Ray Chandler, Table of n, a(n) for n = 1..10000 [First 1000 terms from Vincenzo Librandi]
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)

For n > 1, a(n) = A122870(n-1). Cf. A122870, A106864.

select(isprime, [2, seq(seq(5+s+20*i,s=[-2,2]),i=0..10^3)]); # Robert Israel, Dec 23 2015

QuadPrimes2[2, -2, 3, 10000] (* see A106856 *)

is(n)=isprime(n) && #qfbsolve(Qfb(2,2,3),n)>0 \\ Charles R Greathouse IV, Feb 09 2017

Complement(A000040, A020669).

A122869 Primes p that divide Lucas((p-1)/2), where Lucas is A000032.

Original entry on oeis.org

11, 19, 31, 59, 71, 79, 131, 139, 151, 179, 191, 199, 211, 239, 251, 271, 311, 331, 359, 379, 419, 431, 439, 479, 491, 499, 571, 599, 619, 631, 659, 691, 719, 739, 751, 811, 839, 859, 911, 919, 971, 991, 1019, 1031, 1039, 1051, 1091, 1151, 1171, 1231, 1259

Offset: 1

Alexander Adamchuk, Sep 16 2006

nonn

Final digit of a(n) is 1 or 9.
A002145 is the union of this sequence and A122870, Primes p that divide Lucas((p+1)/2).
Conjecture: This sequence is just the primes congruent to 11 or 19 mod 20. - Charles R Greathouse IV, May 25 2011 [The conjecture is correct. - Jianing Song, Jun 20 2025]
Note that F(p-1) = F((p-1)/2)*Lucas((p-1)/2), where F = A000045. Since gcd(F(n),Lucas(n)) = 1 or 2 (because Lucas(n)^2 - 5*F(n)^2 = 4*(-1)^n), this sequence lists primes p such that p divides F(p-1) but does not divides F((p-1)/2). By Propositions 1.1 and 1.2 (the k = 3 case) of my link below, this is primes p == 11, 19 (mod 20). - Jianing Song, Jun 20 2025

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Vincenzo Librandi)
Jianing Song, Lucas sequences and entry point modulo p
Eric Weisstein's World of Mathematics, Gaussian Prime.
Eric Weisstein's World of Mathematics, Lucas Number.

Cf. A000032, A000045, A053032, A076518, A122870.

Subsequence of A002145, A003626, A040105, A040147 and A064739.

Select[Prime[Range[1000]],IntegerQ[(Fibonacci[(#1-1)/2-1]+Fibonacci[(#1-1)/2+1])/#1]&]

lista(kmax) = {my(lucas1 = 1, lucas2 = 3, lucas3, p); for(k = 3, kmax, lucas3 = lucas1 + lucas2; p = 2*k + 1; if(isprime(p) && !(lucas3 % p), print1(p, ", ")); lucas1 = lucas2; lucas2 = lucas3);} \\ Amiram Eldar, Jun 06 2024

A385225 Primes p such that multiplicative order of -5 modulo p is odd.

Original entry on oeis.org

2, 3, 7, 23, 29, 43, 47, 61, 67, 83, 103, 107, 127, 163, 167, 223, 227, 229, 263, 283, 307, 347, 349, 367, 383, 421, 443, 449, 463, 467, 487, 503, 509, 521, 523, 547, 563, 587, 607, 643, 647, 661, 683, 701, 709, 727, 743, 761, 787, 821, 823, 827, 863, 883, 887, 907, 947, 967, 983

Offset: 1

Jianing Song, Jun 22 2025

The multiplicative order of -5 modulo a(n) is A385231(n).
Contained in primes congruent to 1, 3, 7, 9 modulo 20 (primes p such that -5 is a quadratic residue modulo p, A139513), and contains primes congruent to 3, 7 modulo 20 (A122870).
Conjecture: this sequence has density 1/3 among the primes.

Jianing Song, Table of n, a(n) for n = 1..10000

Subsequence of A139513. Contains A122870 as a subsequence.
Cf. A385231 (the actual multiplicative orders).
Cf. other bases: A014663 (base 2), A385220 (base 3), A385221 (base 4), A385192 (base 5), A163183 (base -2), A385223 (base -3), A385224 (base -4), this sequence (base -5).

Select[Prime[Range[200]], OddQ[MultiplicativeOrder[-5, #]] &] (* Paolo Xausa, Jun 28 2025 *)

isA385225(p) = isprime(p) && (p!=5) && znorder(Mod(-5,p))%2

A216815 Primes congruent to 1 or 9 mod 20.

Original entry on oeis.org

29, 41, 61, 89, 101, 109, 149, 181, 229, 241, 269, 281, 349, 389, 401, 409, 421, 449, 461, 509, 521, 541, 569, 601, 641, 661, 701, 709, 761, 769, 809, 821, 829, 881, 929, 941, 1009, 1021, 1049, 1061, 1069, 1109, 1129, 1181, 1201, 1229, 1249, 1289, 1301, 1321, 1361, 1381, 1409, 1429, 1481, 1489, 1549, 1601, 1609, 1621, 1669, 1709, 1721, 1741, 1789, 1801, 1861

Offset: 1

N. J. A. Sloane, Sep 20 2012

This is a subsequence of A033205 but it is an important sequence in its own right.

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989; see p. 33.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

A subsequence of A033205. Cf. A122870.

[p: p in PrimesUpTo(2000) | p mod 20 in [1, 9]]; // Vincenzo Librandi, Mar 22 2013

Select[Prime[Range[300]], MemberQ[{1, 9}, Mod[#, 20]]&] (* Vincenzo Librandi, Mar 22 2013 *)

A228141 Numbers that are congruent to {1, 5} mod 20.

Original entry on oeis.org

1, 5, 21, 25, 41, 45, 61, 65, 81, 85, 101, 105, 121, 125, 141, 145, 161, 165, 181, 185, 201, 205, 221, 225, 241, 245, 261, 265, 281, 285, 301, 305, 321, 325, 341, 345, 361, 365, 381, 385, 401, 405, 421, 425, 441, 445, 461, 465, 481, 485, 501, 505, 521, 525

Offset: 1

Colin Barker, Aug 12 2013

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A216815, A122870, A228142.

Flatten[Table[20n + {1, 5}, {n, 0, 24}]] (* Alonso del Arte, Aug 12 2013 *)

Vec(x*(15*x^2+4*x+1)/((x-1)^2*(x+1)) + O(x^100))

a(n) = -3*(4+(-1)^n) + 10*n.
a(n) = a(n-1) + a(n-2) - a(n-3).
G.f.: x*(15*x^2+4*x+1) / ((x-1)^2*(x+1)).
E.g.f.: 15 + (10*x - 12)*exp(x) - 3*exp(-x). - David Lovler, Sep 05 2022

A384948 Primes p == 3 (mod 4) such that 5 is a primitive root of integers modulo p, but 2+-i are not primitive roots of Gaussian integers modulo p.

Original entry on oeis.org

83, 307, 347, 503, 587, 863, 947, 1103, 1223, 1523, 1567, 1667, 1787, 1907, 2063, 2087, 2267, 2663, 2683, 2687, 2903, 2963, 3167, 3343, 3347, 3623, 3803, 3863, 4283, 4463, 4523, 4643, 4967, 5147, 5303, 5387, 5507, 5563, 5807, 5843, 6047, 6203, 6607, 6863, 6983, 7187, 7247, 7523, 7583

Offset: 1

Jianing Song, Jun 20 2025

For p = A002145(k), A385165(k) divides (p+1) * ord(5,p), since we have (2+-i)^(p+1) == 5 (mod p). Hence if 2+-i are primitive roots of Gaussian integers modulo p, then 5 is a primitive root of integers modulo p. This sequence lists p such that the converse does not hold.

			5 is a primitive root modulo 83, but the multiplicative order of 2+-i modulo 83 in Gaussian integers is not 83^2 - 1 = 6888; it is 2296 = 6888/3. In other words, 2+-i are not generators of (Z[i]/83Z[i])*.

Jianing Song, Table of n, a(n) for n = 1..10000

By definition, subsequence of A019335, A122870, and A385168.

isprim(p) = my(f = factor(p^2-1)[,1]~); for(i=1, #f, if(Mod([2, -1; 1, 2], p)^((p^2-1)/f[i]) == 1, return(0))); return(1) \\ for a prime p == 3 (mod 4), determines if 2+-i are primitive roots modulo p
isA384948(p) = isprime(p) && (p%4==3) && znorder(Mod(5,p))==p-1 && !isprim(p)

cp's OEIS Frontend

A216816 Duplicate of A122870.

Views

Author

Keywords

A002145 Primes of the form 4*k + 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A020669 Numbers of form x^2 + 5 y^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A106865 Primes of the form 2x^2 + 2xy + 3y^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A122869 Primes p that divide Lucas((p-1)/2), where Lucas is A000032.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A385225 Primes p such that multiplicative order of -5 modulo p is odd.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A216815 Primes congruent to 1 or 9 mod 20.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma