A002313 -id:A002313 - cp's OEIS frontend

A038874 Primes p such that 3 is a square mod p.

2, 3, 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, 227, 229, 239, 241, 251, 263, 277, 311, 313, 337, 347, 349, 359, 373, 383, 397, 409, 419, 421, 431, 433, 443, 457, 467, 479, 491, 503, 541, 563, 577, 587, 599, 601

Offset: 1

N. J. A. Sloane

Also primes congruent to {1, 2, 3, 11} mod 12.
The subsequence p = 1 (mod 4) corresponds to A068228 and only these entries of a(n) are squares mod 3 (from the quadratic reciprocity law). - Lekraj Beedassy, Jul 21 2004
Largest prime factors of n^2 - 3. - Vladimir Joseph Stephan Orlovsky, Aug 12 2009
Aside from 2 and 3, primes p such that Legendre(3, p) = 1. Bolker asserts there are infinitely many of these primes. - Alonso del Arte, Nov 25 2015
The associated bases of the squares are 1, 0, 5, 4, 7, 15, 12, 11, 8, 28, 21, 13...: 1^2 = 3 -1*2, 0^2 = 3-1*3, 5^2 = 3+ 2*11, 4^2 = 3+1*13, 7^2 = 3+2*23, 15^2 = 3+6*37, 12^2 = 3+3*47,... - R. J. Mathar, Feb 23 2017

			11 is in the sequence since the equation x^2 - 11y = 3 has solutions, such as x = 5, y = 2.
13 is in the sequence since the equation x^2 - 13y = 3 has solutions, such as x = 4, y = 1.
17 is not in the sequence because x^2 - 17y = 3 has no solutions in integers; Legendre(3, 17) = -1.

Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 74, Theorem 25.3.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Tamara M. Lavshuk, Regular polygons and polyhedra over finite field, Mathematical Notes of NEFU, Vol 22 No 4 (2015). Mentions this sequence.

Cf. A002313, A033203, A038873, A045331, A057125.

If the first two terms are omitted we get A097933. A040101 is another sequence.

[p: p in PrimesUpTo(1200) | p mod 12 in [1, 2, 3, 11]]; // Vincenzo Librandi, Aug 08 2012

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

Select[Prime[Range[250]], MemberQ[{1, 2, 3, 11}, Mod[#, 12]] &] (* Vincenzo Librandi, Aug 08 2012 *)
Select[Flatten[Join[{2, 3}, Table[{12n - 1, 12n + 1}, {n, 50}]]], PrimeQ] (* Alonso del Arte, Nov 25 2015 *)

forprime(p=2, 1e3, if(issquare(Mod(3, p)), print1(p , ", "))) \\ Altug Alkan, Dec 04 2015

a(n) ~ 2n log n. - Charles R Greathouse IV, Nov 29 2016

More terms from Henry Bottomley, Aug 10 2000

A120304 Catalan numbers minus 2.

Original entry on oeis.org

-1, -1, 0, 3, 12, 40, 130, 427, 1428, 4860, 16794, 58784, 208010, 742898, 2674438, 9694843, 35357668, 129644788, 477638698, 1767263188, 6564120418, 24466267018, 91482563638, 343059613648, 1289904147322, 4861946401450, 18367353072150, 69533550916002, 263747951750358

Offset: 0

Alexander Adamchuk, Jul 13 2006

Prime p divides a(p). Prime p divides a(p+1) for p > 2. Prime p divides a((p-1)/2) for p = 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, ... = A002144(n) except 5. Pythagorean primes: primes of form 4n+1. Also A002313(n) except 2, 5. Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2; or, -1 is a square mod p. p^2 divides a(p^2) and a(p^2+1) for all prime p.

For n >= 2, number of Dyck paths of semilength n such that all four consecutive step patterns of length 2 occur at least once; a(3)=3: UDUUDD, UUDDUD, UUDUDD. For each n two paths do not satisfy the condition: U^{n}D^{n} and (UD)^n. - Alois P. Heinz, Jun 13 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2. [The sequence here begins 1, 1, 1, 3, 12, 40, 130, 427, 1428, 4860, ...]

Cf. A000108, A002144, A002313.

Cf. A243882, A243820.

a:= n-> binomial(2*n, n)/(n+1) -2:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 13 2014

Table[(2n)!/n!/(n+1)!-2,{n,0,30}]
CatalanNumber[Range[0,30]]-2 (* Harvey P. Dale, May 03 2019 *)

combinat::dyckWords::count(n)-2 $ n = 0..38; // Zerinvary Lajos, May 08 2008

a(n) = binomial(2*n, n)/(n+1)-2; \\ Altug Alkan, Dec 17 2017

a(n) = A000108(n) - 2.
a(n) = (2n)!/(n!*(n+1)!) - 2.
(n+1)*a(n) + 2*(-3*n+1)*a(n-1) + (9*n-13)*a(n-2) + 2*(-2*n+5)*a(n-3) = 0. - R. J. Mathar, May 30 2014

A248527 Numbers n such that the smallest prime divisor of n^2+1 is 13.

Original entry on oeis.org

34, 44, 60, 70, 86, 96, 164, 174, 190, 200, 216, 226, 294, 304, 320, 330, 346, 356, 424, 434, 450, 460, 476, 486, 554, 564, 580, 590, 606, 616, 684, 694, 710, 720, 736, 746, 814, 824, 840, 850, 866, 876, 944, 954, 970, 980, 996, 1006, 1074, 1084, 1100, 1110

Offset: 1

Michel Lagneau, Oct 08 2014

nonn

Or numbers n such that the smallest prime divisor of A002522(n) is A002313(3).
a(n) == 8 (mod 26) if n is odd and a(n) == 18 (mod 26) if n is even.
It is interesting to observe that a(n) is given by a linear formula (see the formula below).

			34 is in the sequence because 34^2+1= 13*89.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A002522, A089120, A002313.

[n: n in [2..3000] | PrimeDivisors(n^2+1)[1] eq 13]; // Bruno Berselli, Oct 08 2014

* first program *
with(numtheory):p:=13:
   for n from 1 to 1000 do:
    if factorset(n^2+1)[1] = p then printf(`%d, `, n):
    else
    fi:
   od:
* second program using the formula*
for n from 0 to 100 by 5 do:
   for k from 1 to 3 do:
     x:=8+(k+n)*26:y:=18+(k+n)*26:
     printf(`%d, `,x):printf(`%d, `,y):
   od:
  od:

lst={};Do[If[FactorInteger[n^2+1][[1,1]]==13,AppendTo[lst,n]],{n,2,2000}];lst
p = 13; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[1200], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

isok(n) = factor(n^2+1)[1,1] == 13; \\ Michel Marcus, Oct 08 2014

{a(n)} = {8+(k + m)*26} union {18+(k + m)*26} for m = 0, 5, 10,...,5p,... and k = 1, 2, 3 (values in increasing order).

A005529 Primitive prime factors of the sequence k^2 + 1 (A002522) in the order that they are found.

Original entry on oeis.org

2, 5, 17, 13, 37, 41, 101, 61, 29, 197, 113, 257, 181, 401, 97, 53, 577, 313, 677, 73, 157, 421, 109, 89, 613, 1297, 137, 761, 1601, 353, 149, 1013, 461, 1201, 1301, 541, 281, 2917, 3137, 673, 1741, 277, 1861, 769, 397, 241, 2113, 4357, 449, 2381, 2521, 5477

Offset: 1

N. J. A. Sloane

nonn

Primes associated with Stormer numbers.

See A002313 for the sorted list of primes. It can be shown that k^2 + 1 has at most one primitive prime factor; the other prime factors divide m^2 + 1 for some m < k. When k^2 + 1 has a primitive prime factor, k is a Stormer number (A005528), otherwise a non-Stormer number (A002312).

John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 246.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. Todd, Table of Arctangents. National Bureau of Standards, Washington, DC, 1951, p. vi.

T. D. Noe, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Stormer Number.
Eric Weisstein's World of Mathematics, Primitive Prime Factor

Cf. A002312, A002313 (primes of the form 4k+1), A002522, A005528.

V:=[]; for n in [1..75] do p:=Max([ x[1]: x in Factorization(n^2+1) ]); if not p in V then Append(~V, p); end if; end for; V; // Klaus Brockhaus, Oct 29 2008

prms={}; Do[f=First/@FactorInteger[k^2+1]; p=Complement[f, prms]; prms=Join[prms, p], {k, 100}]; prms

do(n)=my(v=List(),g=1,m,t,f); for(k=1,n, m=k^2+1; t=gcd(m,g); while(t>1, m/=t; t=gcd(m,t)); f=factor(m)[,1]; if(#f, listput(v,f[1]); g*=f[1])); Vec(v) \\ Charles R Greathouse IV, Jun 11 2017

Edited by T. D. Noe, Oct 02 2003

A031439 a(0) = 1, a(n) is the greatest prime factor of a(n-1)^2+1 for n > 0.

Original entry on oeis.org

1, 2, 5, 13, 17, 29, 421, 401, 53, 281, 3037, 70949, 1713329, 1467748131121, 37142837524296348426149, 101591133424866642486477019709, 1650979973845742266714536305651329, 78343914631785958284737, 4029445531112797145738746391569, 350080544438648120162733678636001, 26208090024628793745288451837610346882122253572537, 4717815978577117335515270825550279551117660519482308365269206484133871485221

Offset: 0

Yasutoshi Kohmoto

Does this sequence grow indefinitely, or does it cycle? - Franklin T. Adams-Watters, Oct 02 2006
All a(n) except a(0) = 1 belong to A014442(n) = {2, 5, 5, 17, 13, 37, 5, 13, 41, 101, ...} Largest prime factor of n^2 + 1. All a(n) except a(0) = 1 belong to A002313(n) = {2, 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, ...} Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2; or, -1 is a square mod p. All a(n) except a(0) = 1 and a(1) = 2 are the Pythagorean primes A002144(n) = {5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, ...} Primes of form 4n+1. - Alexander Adamchuk, Nov 05 2006
Essentially the same as A072268; A072268(n) = A031439(n-1)^2 + 1. - Charles R Greathouse IV, May 08 2009

			a(16)=A006530(a(15)^2+1)=
A006530(101591133424866642486477019709^2+1)=
A006530(10320758390549056348725939119133160378521185060950774444682)=
A006530(2*29*23201*4645528280970018601*1650979973845742266714536305651329)=
1650979973845742266714536305651329, factorization of A006530(a(15)^2+1) by Dario A. Alpern's program (see link).

Dennis Langdeau, Table of n, a(n) for n = 0..24
Dario A. Alpern, Factorization: Elliptic Curve Method
Jason Papadopoulos, Integer Factorization Source Code.

Cf. A056650, A003095.
Cf. A002144 - Pythagorean primes: primes of form 4n+1; A002313 - Primes congruent to 1 or 2 modulo 4; A014442 - Largest prime factor of n^2 + 1.
Cf. also A072268, A056650, A003095, A125256.

gpf[n_] := FactorInteger[n][[-1, 1]]; a[0] = 1; a[n_] := a[n] = gpf[a[n - 1]^2 + 1]; Table[an = a[n]; Print[an]; an, {n, 0, 21}] (* Jean-François Alcover, Nov 04 2011 *)
NestList[FactorInteger[#^2+1][[-1,1]]&,1,21] (* Harvey P. Dale, Jul 04 2013 *)

gpf(n)=local(pf);pf=factor(n);pf[matsize(pf)[1],1] vector(20,i,r=if(i==1,1,gpf(r^2+1)))

One more term from Vladeta Jovovic, Nov 26 2001
a(16) from Reinhard Zumkeller, Aug 07 2004
a(17)-a(21) from Richard FitzHugh (fitzhughrichard(AT)hotmail.com), Aug 12 2004

A185086 Fouvry-Iwaniec primes: Primes of the form k^2 + p^2 where p is a prime.

Original entry on oeis.org

5, 13, 29, 41, 53, 61, 73, 89, 109, 113, 137, 149, 157, 173, 193, 229, 233, 269, 281, 293, 313, 317, 349, 353, 373, 389, 397, 409, 433, 449, 461, 509, 521, 557, 569, 593, 601, 613, 617, 653, 673, 701, 733, 761, 773, 797, 809, 853, 857, 877, 929, 937, 941, 953

Offset: 1

Charles R Greathouse IV, Feb 18 2011

Sequence is infinite, see Fouvry & Iwaniec.
Its intersection with A028916 is A262340, by the uniqueness part of Fermat's two-squares theorem. - Jonathan Sondow, Oct 05 2015
Named after the French mathematician Étienne Fouvry (b. 1953) and the Polish-American mathematician Henryk Iwaniec (b. 1947). - Amiram Eldar, Jun 20 2021

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Étienne Fouvry and Henryk Iwaniec, Gaussian primes, Acta Arithmetica, Vol. 79, No. 3 (1997), pp. 249-287.
Lasse Grimmelt, Vinogradov's Theorem with Fouvry-Iwaniec Primes, arXiv:1809.10008 [math.NT], 2018.
Art of Problem Solving, Fermat's Two Squares Theorem.

Subsequence of A002144 and hence of A002313.
The positive terms of A240130 form a subsequence.
Cf. A010052, A001248, A000040, A028916, A262340.

a185086 n = a185086_list !! (n-1)
a185086_list = filter (\p -> any ((== 1) . a010052) $
               map (p -) $ takeWhile (<= p) a001248_list) a000040_list
-- Reinhard Zumkeller, Mar 17 2013

nn = 1000; Union[Reap[Do[n = k^2 + p^2; If[n <= nn && PrimeQ[n], Sow[n]], {k, Sqrt[nn]}, {p, Prime[Range[PrimePi[Sqrt[nn]]]]}]][[2, 1]]]

is(n)=forprime(p=2,sqrtint(n),if(issquare(n-p^2),return(isprime(n))));0

list(lim)=my(v=List(),N,t);forprime(p=2,sqrt(lim), N=p^2; for(n=1,sqrt(lim-N), if(ispseudoprime(t=N+n^2), listput(v,t)))); v=vecsort(Vec(v),,8); v

A145299 Smallest k such that k^2+1 is divisible by A002144(n)^6.

Original entry on oeis.org

1068, 1999509, 390112, 253879357, 756360062, 2363588163, 5041394261, 9435321777, 41865466758, 102666405913, 197177418061, 316411915250, 171829799914, 625667121807, 182312430890, 1095001339019, 6390289199260

Offset: 1

Klaus Brockhaus, Oct 17 2008

nonn

			a(1) = 1068 since A002144(1) = 5, 1068^2+1 = 1140625 = 5^6*73 and for no k < 1068 does 5^6 divide k^2+1. a(11) = 197177418061 since A002144(11) = 97, 197177418061^2+1 = 38878934193202368999722 = 2*97^6*23337479509 and for no k < 197177418061 does 97^6 divide k^2+1.

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A002144 (primes of form 4n+1), A002313 (-1 is a square mod p), A059321, A145296, A145297, A145298.

{ e=6; forprime(p=2, 1000, if(p%4==1, k=lift(sqrt(-1+O(p^e))); if(k>p^e/2,k=p^e-k); print1(k, ", "))) }

from itertools import islice
from sympy import nextprime, sqrt_mod_iter
def A145299_gen(): # generator of terms
    p = 1
    while (p:=nextprime(p)):
        if p&3==1:
            yield min(sqrt_mod_iter(-1,p**6))
A145299_list = list(islice(A145299_gen(),20)) # Chai Wah Wu, May 04 2024

More terms and efficient PARI program from. - Max Alekseyev, Oct 28 2008

A084161 Primes that are the sum of two squares and which set a record for the gap to the next prime of that form.

Original entry on oeis.org

2, 5, 17, 73, 113, 197, 461, 1493, 1801, 9533, 15661, 16741, 33181, 39581, 50593, 180797, 183089, 1561829, 1637813, 2243909, 4468889, 4874717, 7856441, 10087201, 12021029, 12213913, 18226661, 148363637, 292182097, 320262253, 468213937

Offset: 0

Sven Simon, May 17 2003

nonn

Real primes 2, 5, 13, 17, 29, 37, ... (A002313) have a unique representation as sum of two squares. Values larger than 2 are the primes p with p = 1 mod 4. If p = x^2 + y^2, the corresponding complex prime is x + y * i, where i is the imaginary unit.

The length of the gap can be found in A084162.

			a(3) = 73: There are no primes p = 1 mod 4 between 73 and 89, this gap is the largest up to 89, the length is 16. Note that 73 = (8 - 3i)(8 + 3i) and 89 = (8 - 5i)(8 + 5i). The primes 79 and 83 are inert in Z[i].

Ervand Kogbetliantz and Alice Krikorian, Handbook of First Complex Prime Numbers, Parts 1 and 2, Gordon and Breach, 1971.

Charles R Greathouse IV, Table of n, a(n) for n = 0..42
Alexei Kourbatov and Marek Wolf, Predicting maximal gaps in sets of primes, arXiv preprint arXiv:1901.03785 [math.NT], 2019.

Cf. A002313, A084160, A084162 (gap sizes), A268963 (end-of-gap primes).

Reap[Print[2]; Sow[2]; r = 0; p = 5; For[q = 7, q < 10^7, q = NextPrime[q], If[Mod[q, 4] == 3, Continue[]]; g = q - p; If[g > r, r = g; Print[p] Sow[p]]; p = q]][[2, 1]] (* Jean-François Alcover, Feb 20 2019, from PARI *)

print1(2);r=0;p=5;forprime(q=7,1e7,if(q%4==3,next);g=q-p;if(g>r,r=g;print1(", "p));p=q) \\ Charles R Greathouse IV, Apr 29 2014

A111635 Smallest prime of the form x^(2^n) + y^(2^n) where x,y are distinct integers.

Original entry on oeis.org

2, 5, 17, 257, 65537, 3512911982806776822251393039617, 4457915690803004131256192897205630962697827851093882159977969339137, 1638935311392320153195136107636665419978585455388636669548298482694235538906271958706896595665141002450684974003603106305516970574177405212679151205373697500164072550932748470956551681

Offset: 0

Max Alekseyev, Aug 09 2005

nonn

Is this sequence defined for all n?
From Jeppe Stig Nielsen, Sep 16 2015: (Start)
Numbers of this form are sometimes called extended generalized Fermat numbers.
If we restrict ourselves to the case y=1, we get instead the sequence A123599, therefore a(n) <= A123599(n) for all n. Can this be an equality for some n > 4?
The formula x^(2^m) + y^(2^m) also gives the decreasing chain {A000040, A002313, A002645, A006686, A100266, A100267, ...} of subsets of the prime numbers if we drop the requirement that x != y and take all primes (not just the smallest one) with m greater than some lower bound.
(End)
For more terms (the values of max(x,y)), see A291944. - Jeppe Stig Nielsen, Dec 28 2019

Jeppe Stig Nielsen, Table of n, a(n) for n = 0..9

Cf. A019434, A100270, A123599, A291944.

A145296 Smallest k such that k^2 + 1 is divisible by A002144(n)^3.

Original entry on oeis.org

57, 239, 1985, 10133, 9466, 11389, 27590, 51412, 153765, 344464, 107551, 296344, 172078, 432436, 931837, 753090, 676541, 2321221, 2027724, 3394758, 1706203, 4841182, 1438398, 2947125, 398366, 5657795, 4942017, 9400802, 11906503

Offset: 1

Klaus Brockhaus, Oct 08 2008

nonn

			a(3) = 1985 since A002144(3) = 17, 1985^2 + 1 = 3940226 = 2*17^3*401 and for no k < 1985 does 17^3 divide k^2+1.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..150 from Klaus Brockhaus)

Cf. A002144 (primes of form 4n+1), A002313 (-1 is a square mod p), A059321, A145297, A145298, A145299.

{m=12000000; pmax=300; z=70; v=vector(z); for(n=1, m, fac=factor(n^2+1); for(j=1, #fac[, 1], if(fac[j, 2]>=3&&fac[j, 1]<=pmax, q=primepi(fac[j, 1]); if(q<=z&&v[q]==0, v[q]=n)))); t=1; j=0; while(t&&j

{e=3; forprime(p=2, 300, if(p%4==1, q=p^e; m=q; while(!ispower(m-1,2,&n), m=m+q); print1(n, ",")))} \\ Klaus Brockhaus, Oct 09 2008

from itertools import islice
from sympy import nextprime, sqrt_mod_iter
def A145296_gen(): # generator of terms
    p = 1
    while (p:=nextprime(p)):
        if p&3==1:
            yield min(sqrt_mod_iter(-1,p**3))
A145296_list = list(islice(A145296_gen(),20)) # Chai Wah Wu, May 04 2024

cp's OEIS Frontend

A038874 Primes p such that 3 is a square mod p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A120304 Catalan numbers minus 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

MuPAD

PARI

Formula

A248527 Numbers n such that the smallest prime divisor of n^2+1 is 13.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A005529 Primitive prime factors of the sequence k^2 + 1 (A002522) in the order that they are found.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A031439 a(0) = 1, a(n) is the greatest prime factor of a(n-1)^2+1 for n > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A185086 Fouvry-Iwaniec primes: Primes of the form k^2 + p^2 where p is a prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI