A002313 -id:A002313 - cp's OEIS frontend

A002330 Value of y in the solution to p = x^2 + y^2, x <= y, with prime p = A002313(n).

1, 2, 3, 4, 5, 6, 5, 7, 6, 8, 8, 9, 10, 10, 8, 11, 10, 11, 13, 10, 12, 14, 15, 13, 15, 16, 13, 14, 16, 17, 13, 14, 16, 18, 17, 18, 17, 19, 20, 20, 15, 17, 20, 21, 19, 22, 20, 21, 19, 20, 24, 23, 24, 18, 19, 25, 22, 25, 23, 26, 26, 22, 27, 26, 20, 25, 22, 26, 28, 25

Offset: 1

N. J. A. Sloane

nonn

			The following table shows the relationship between several closely related sequences:
Here p = A002144 = primes == 1 (mod 4), p = a^2+b^2 with a < b;
a = A002331, b = A002330, t_1 = ab/2 = A070151;
p^2 = c^2+d^2 with c < d; c = A002366, d = A002365,
t_2 = 2ab = A145046, t_3 = b^2-a^2 = A070079,
with {c,d} = {t_2, t_3}, t_4 = cd/2 = ab(b^2-a^2).
---------------------------------
.p..a..b..t_1..c...d.t_2.t_3..t_4
---------------------------------
.5..1..2...1...3...4...4...3....6
13..2..3...3...5..12..12...5...30
17..1..4...2...8..15...8..15...60
29..2..5...5..20..21..20..21..210
37..1..6...3..12..35..12..35..210
41..4..5..10...9..40..40...9..180
53..2..7...7..28..45..28..45..630
.................................

A. J. C. Cunningham, Quadratic Partitions. Hodgson, London, 1904, p. 1.
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).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), pp. 1011-1013.
A. J. C. Cunningham, Quadratic Partitions, Hodgson, London, 1904. [Annotated scans of selected pages]
K. Matthews, Serret's algorithm Server.
J. Todd, A problem on arc tangent relations, Amer. Math. Monthly, 56 (1949), 517-528.
Eric Weisstein's World of Mathematics, Fermat's 4n Plus 1 Theorem.

Cf. A002331, A002313, A002144.

a := []; for x from 0 to 50 do for y from x to 50 do p := x^2+y^2; if isprime(p) then a := [op(a),[p,x,y]]; fi; od: od: writeto(trans); for i from 1 to 158 do lprint(a[i]); od: # then sort the triples in "trans"

Flatten[#, 1]&[Table[PowersRepresentations[Prime[k], 2, 2], {k, 1, 142}]][[All, 2]] (* Jean-François Alcover, Jul 05 2011 *)

f(p)=my(s=lift(sqrt(Mod(-1,p))),x=p,t);if(s>p/2,s=p-s); while(s^2>p, t=s;s=x%s;x=t);s
forprime(p=2,1e3,if(p%4-3,print1(f(p)", "))) \\ Charles R Greathouse IV, Apr 24 2012

do(p)=qfbsolve(Qfb(1,0,1),p)[1]
forprime(p=2,1e3,if(p%4-3,print1(do(p)", "))) \\ Charles R Greathouse IV, Sep 26 2013

print1(1); forprimestep(p=5,1e3,4, print1(", "qfbcornacchia(1,p)[1])) \\ Charles R Greathouse IV, Sep 15 2021

a(n) = A096029(n) + A096030(n) + 1, for n>1. - Lekraj Beedassy, Jul 21 2004

a(n+1) = Max(A002972(n), 2*A002973(n)). - Reinhard Zumkeller, Feb 16 2010

A002331 Values of x in the solution to p = x^2 + y^2, x <= y, with prime p = A002313(n).

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 4, 2, 5, 3, 5, 4, 1, 3, 7, 4, 7, 6, 2, 9, 7, 1, 2, 8, 4, 1, 10, 9, 5, 2, 12, 11, 9, 5, 8, 7, 10, 6, 1, 3, 14, 12, 7, 4, 10, 5, 11, 10, 14, 13, 1, 8, 5, 17, 16, 4, 13, 6, 12, 1, 5, 15, 2, 9, 19, 12, 17, 11, 5, 14, 10, 18, 4, 6, 16, 20, 19, 10, 13, 4, 6, 15, 22, 11, 3, 5

Offset: 1

N. J. A. Sloane

nonn

			The following table shows the relationship between several closely related sequences:
Here p = A002144 = primes == 1 (mod 4), p = a^2+b^2 with a < b;
a = A002331, b = A002330, t_1 = ab/2 = A070151;
p^2 = c^2+d^2 with c < d; c = A002366, d = A002365,
t_2 = 2ab = A145046, t_3 = b^2-a^2 = A070079,
with {c,d} = {t_2, t_3}, t_4 = cd/2 = ab(b^2-a^2).
---------------------------------
.p..a..b..t_1..c...d.t_2.t_3..t_4
---------------------------------
.5..1..2...1...3...4...4...3....6
13..2..3...3...5..12..12...5...30
17..1..4...2...8..15...8..15...60
29..2..5...5..20..21..20..21..210
37..1..6...3..12..35..12..35..210
41..4..5..10...9..40..40...9..180
53..2..7...7..28..45..28..45..630
.................................

A. J. C. Cunningham, Quadratic Partitions. Hodgson, London, 1904, p. 1.
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).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
A. T. Benjamin and D. Zeilberger, Pythagorean primes and palindromic continued fractionsINTEGERS 5(1) (2005) #A30
John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), pp. 1011-1013.
A. J. C. Cunningham, Quadratic Partitions, Hodgson, London, 1904. [Annotated scans of selected pages]
K. Matthews, Serret's algorithm Server.
J. Todd, A problem on arc tangent relations, Amer. Math. Monthly, 56 (1949), 517-528.
Eric Weisstein's World of Mathematics, Fermat's 4n Plus 1 Theorem.

Cf. A002330, A002313, A002144, A027862 (locates y=x+1).

See A002330 for Maple program.
# alternative
A002331 := proc(n)
    A363051(A002313(n)) ;
end proc:
seq(A002331(n),n=1..100) ; # R. J. Mathar, Feb 01 2024

pmax = 1000; x[p_] := Module[{x, y}, x /. ToRules[Reduce[0 <= x <= y && x^2 + y^2 == p, {x, y}, Integers]]]; For[n=1; p=2, pJean-François Alcover, Feb 26 2016 *)

f(p)=my(s=lift(sqrt(Mod(-1,p))),x=p,t);if(s>p/2,s=p-s); while(s^2>p,t=s;s=x%s;x=t);s
forprime(p=2,1e3,if(p%4-3,print1(sqrtint(p-f(p)^2)", ")))
\\ Charles R Greathouse IV, Apr 24 2012

do(p)=qfbsolve(Qfb(1,0,1),p)[2]
forprime(p=2,1e3,if(p%4-3,print1(do(p)", "))) \\ Charles R Greathouse IV, Sep 26 2013

a(n) = A096029(n) - A096030(n) for n > 1. - Lekraj Beedassy, Jul 16 2004
a(n+1) = Min(A002972(n), 2*A002973(n)). - Reinhard Zumkeller, Feb 16 2010
a(n) = A363051(A002313(n)). - R. J. Mathar, Jan 31 2024

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Original entry on oeis.org

1, 2, 8, 4, 12, 6, 32, 30, 50, 46, 34, 22, 10, 76, 98, 100, 44, 28, 80, 162, 112, 14, 122, 144, 64, 16, 82, 60, 228, 138, 288, 114, 148, 136, 42, 104, 274, 334, 20, 266, 392, 254, 382, 348, 48, 208, 286, 52, 118, 86, 24, 516, 476, 578, 194, 154, 504, 106, 58, 26, 566, 96, 380, 670, 722, 62, 456, 582, 318, 526, 246, 520, 650, 726, 494, 324

Offset: 0

M. F. Hasler, Mar 11 2012

nonn

This yields the prime factors of numbers of the form N^2+1, cf. formula in A089120: For n=0,1,2,... check whether N = +/- a(n) [mod 2*A002313(n+1)], if so, then A002313(n+1) is a prime factor of N^2+1.
Obviously, p then divides (2kp +/- a(n))^2+1 for all k >=0 ; in particular it will be the least prime factor of such numbers if there is no earlier match.
Alternatively one could deal separately with the case of odd N, for which p=2 divides N^2+1, and even N, for which only Pythagorean primes A002144(n)=A002313(n+1) can be prime factors of N^2+1.

Cf. A002496, A014442, A085722, A144255, A089120, A193432.

Cf. A002314, A177979.

A209874(n)=if( n, 2*lift(sqrt(Mod(-1, A002144[n])/4)), 1)

/* for illustrative purpose: a(n) is the smaller of the 2 possible remainders mod 2*p of numbers N such that N^2+1 has p as smallest prime factor */ forprime( p=1,199, p>2 & p%4 != 1 & next; my(c=[]); for(i=1,9e9, factor(i^2+1)[1,1]==p |next; c=vecsort(concat(c,i%(2*p)),,8); #c==1 || print1(","c[1]) || break))

For n>0, A209874(n) = 2*sqrt(-1/4 mod A002144(n)), where sqrt(a mod p) stands for the positive x < p/2 such that x^2=a in Z/pZ.

A209874(n) = A209877(n)*2 for n>0.

A185389 Largest number k such that the greatest prime factor of k^2+1 is A002313(n), the n-th prime not congruent to 3 mod 4.

Original entry on oeis.org

1, 7, 239, 268, 307, 18543, 2943, 485298, 330182, 478707, 24208144, 22709274, 2189376182, 284862638, 599832943, 19696179, 314198789, 3558066693, 69971515635443, 18986886768, 18710140581, 104279454193

Offset: 1

Charles R Greathouse IV, Feb 21 2011

For any prime p, there are finitely many k such that k^2+1 has p as its largest prime factor.

Numbers k such that k^2+1 is p-smooth appear in arctan-relations for the computation of Pi (for example, Machin's identity Pi/4 = 4*arctan(1/5) - arctan(1/239)), see the fxtbook link. [Joerg Arndt, Jul 02 2012]

Joerg Arndt, Matters Computational (The Fxtbook), section 32.5 "Arctangent relations for Pi", pp. 633-640.
Filip Najman, Smooth values of some quadratic polynomials, Glasnik Matematicki Series III 45 (2010), pp. 347-355.
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19-24.
Filip Najman, Home Page (gives all 811 numbers x such that x^2+1 has no prime factor greater than 197)

Equivalents for other polynomials: A175607 (k^2 - 1), A145606 (k^2 + k).

A223702 Irregular triangle of numbers k such that A002313(n), the n-th prime not congruent to 3 mod 4 is the largest prime factor of k^2 + 1.

Original entry on oeis.org

1, 2, 3, 7, 5, 8, 18, 57, 239, 4, 13, 21, 38, 47, 268, 12, 17, 41, 70, 99, 157, 307, 6, 31, 43, 68, 117, 191, 302, 327, 882, 18543, 9, 32, 73, 132, 278, 378, 829, 993, 2943, 23, 30, 83, 182, 242, 401, 447, 606, 931, 1143, 1772, 6118, 34208, 44179, 85353, 485298

Offset: 1

T. D. Noe, Apr 03 2013

Note that primes of the form 4x+3 are not divisors.

			Irregular triangle:
   p | {k}
-----+---------------------------------
   2 | {1},
   5 | {2, 3, 7},
  13 | {5, 8, 18, 57, 239},
  17 | {4, 13, 21, 38, 47, 268},
  29 | {12, 17, 41, 70, 99, 157, 307},
  37 | {6, 31, 43, 68, 117, 191, 302, 327, 882, 18543},
  41 | {9, 32, 73, 132, 278, 378, 829, 993, 2943}
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..811 (first 22 rows for primes up to 197)
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19-24.
Filip Najman, Smooth values of some quadratic polynomials, Glasnik Matematicki Series III 45 (2010), pp. 347-355
Filip Najman, List of Publications Page (Adjacent to entry number 7 are links with a data file for the first 22 rows (=811 terms) of this sequence). [As of Dec 2024, the link has the incorrect URL. Should be https://web.math.pmf.unizg.hr/~fnajman/rezplus1.html]

Cf. A002313, A014442, A177979 (first terms), A185389 (last terms), A223705, A285283, A379346 (row lengths), A379347 (row sums).
Cf. A285282, A285523.
Cf. A223701, A223703, A223704 (related tables).

t = Table[FactorInteger[n^2 + 1][[-1,1]], {n, 10^5}]; Table[Flatten[Position[t, Prime[n]]], {n, 13}]

Definition amended by Andrew Howroyd, Dec 22 2024

A177979 Smallest number k such that A002313(n) divides k^2+1.

Original entry on oeis.org

1, 2, 5, 4, 12, 6, 9, 23, 11, 27, 34, 22, 10, 33, 15, 37, 44, 28, 80, 19, 81, 14, 107, 89, 64, 16, 82, 60, 53, 138, 25, 114, 148, 136, 42, 104, 115, 63, 20, 143, 29, 179, 67, 109, 48, 208, 235, 52, 118, 86, 24, 77, 125, 35, 194, 154, 149, 106, 58, 26, 135, 96, 353, 87, 39

Offset: 1

Eva-Maria Zschorn (e-m.zschorn(AT)zaschendorf.km3.de), May 16 2010

1 followed by A002314. [From R. J. Mathar, May 29 2010]

			1^2+1 = 2 which is divided by A002313(1) which adds 1 to the sequence.
2^2+1 = 5 is divided by A002313(2) which adds 2 to the sequence.
27^2+1 = 730 is divided by A002313(10) which adds 27 to the sequence.

Friedhelm Padberg: Elementare Zahlentheorie. Spektrum Akademischer Verlag, Berlin Heidelberg, 1996

Disentangled variables in the definition - R. J. Mathar, Jun 07 2010

A185952 Partial products of A002313, the primes that are 1 or 2 (mod 4).

Original entry on oeis.org

2, 10, 130, 2210, 64090, 2371330, 97224530, 5152900090, 314326905490, 22945864100770, 2042181904968530, 198091644781947410, 20007256122976688410, 2180790917404459036690, 246429373666703871145970

Offset: 1

Jonathan Vos Post, Feb 07 2011

Product of the first n primes which are natural primes which are not Gaussian primes. Product of the first n primes congruent to 1 or 2 modulo 4. Product of the first n primes of form x^2+y^2. Product of the first n primes p such that -1 is a square mod p. Factors of primorials (A002110) not divisible by natural primes which are also Gaussian primes.

Essentially twice A006278.

			a(10) = 2 * 5 * 13 * 17 * 29 * 37 * 41 * 53 * 61 * 73 = 22945864100770.

G. C. Greubel, Table of n, a(n) for n = 1..300

Cf. A000040, A002110, A002313, A042963, A103222.

Rest@ FoldList[#1*#2 &, 1, Select[ Prime@ Range@ 30, Mod[#, 4] != 3 &]] (* Robert G. Wilson v *)

pp(v)=my(t=1); vector(#v,i,t*=v[i])
pp(select(n->n%4<3, primes(20))) \\ Charles R Greathouse IV, Apr 21 2015

a(n) = Product_{i=1..n} A002313(i) = 2 * Product_{i=1..n} {p in A000040 but p not in A002145} = Product_{i=1..n} {A000040 intersection A042963}.

Terms corrected by Robert G. Wilson v, Feb 11 2011

A285283 Number of integers x such that the greatest prime factor of x^2 + 1 is at most A002313(n), the n-th prime not congruent to 3 mod 4.

Original entry on oeis.org

1, 4, 9, 15, 22, 32, 41, 57, 74, 94, 120, 156, 192, 232, 278, 325, 381, 448, 521, 607, 704, 811

Offset: 1

Tomohiro Yamada, Apr 16 2017

In other words, x^2 + 1 is A002313(n)-smooth.
Størmer shows that the number of such integers is finite for any n.
a(n) <= 3^n - 2^n follows from Størmer's argument.
a(n) <= (2^n-1)*(A002313(n)+1)/2 is implicit in Lehmer 1964.
Luca 2004 determines all integers x such that x^2 + 1 is 100-smooth, which is pushed to 200 by Najman 2010.

D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57--69.
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19--24.
Filip Najman, Smooth values of some quadratic polynomials, Glas. Mat. 45 (2010), 347--355. Tables are available in the author's Home Page (gives all 811 numbers x such that x^2+1 has no prime factor greater than 197).
A. Schinzel, On two theorems of Gelfond and some of their applications, Acta Arithmetica 13 (1967-1968), 177--236.
Carl Størmer, Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications (in French), Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2), 48 pp.

Equivalents for x(x+1): A145604.

Cf. A002313, A014442, A185389, A223702, A285282, A379346 (first differences).

a(13)-a(22) added by Andrew Howroyd, Dec 22 2024

A084160 First occurrence prime gaps of the primes in sequence A002313 (Real primes with corresponding complex primes). a(0) = 2 with length of gap 3. For n>0 the size of the gap in the sequence is 4n, a(n) is the starting prime of the gap.

Original entry on oeis.org

2, 13, 5, 17, 73, 293, 113, 1153, 197, 2557, 1321, 1553, 461, 2161, 1493, 1801, 10993, 9533, 15661, 27817, 76001, 24593, 16741, 40709, 53453, 58789, 62297, 33181, 256189, 110321, 112757, 344497, 39581, 138661, 269761, 448421, 78989, 50593

Offset: 0

Sven Simon, May 17 2003

nonn

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

			a(3) = 17 because the next prime in sequence A002313 is 29, the size of the gap is 3*4 = 12.

Handbook of First Complex Prime Numbers, Part1+2 Ervand Kogbetliantz and Alice Krikorian, Gordon and Breach, 1971

Cf. A002313, A084161.

A084163 Primes which are -1 mod m, where m is the index of the prime in sequence A002313 (Real primes with corresponding complex primes). The index m can be found in A084164 Primes which are 1 mod m can be found in sequence A084165.

Original entry on oeis.org

29, 41, 197, 229, 269, 2617, 2729, 2897, 4649, 37201, 37277, 169553, 170081, 170873, 282577, 9491309, 9493889, 15614761, 69955373, 69955577, 115195429, 115196129, 312316481, 513773717, 846651233, 3778288373, 3778289381, 3778290641

Offset: 1

Sven Simon, May 17 2003

nonn

Real primes 2,5,13,17,29,37,... have a unique representation as sum of two squares. Values larger 2 are the primes p with p = 1 mod 4. This is sequence A002313. If p = x^2 + y^2, the corresponding complex prime is x+y*i. First complex prime is 1+i with 2 as corresponding real prime, according to reference, page 1-2.

			197 is the 22nd prime in sequence A002313, 22*9 = 198, so 197 = -1 mod 22.

Handbook of First Complex Prime Numbers, Part1+2 Ervand Kogbetliantz and Alice Krikorian, Gordon and Breach, 1971. The list in Part 2 contains an error: on page 919, column 2, number 5 is printed twice, so the indices after that number are wrong.

Cf. A002313, A084164, A084165.

cp's OEIS Frontend

A002330 Value of y in the solution to p = x^2 + y^2, x <= y, with prime p = A002313(n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A002331 Values of x in the solution to p = x^2 + y^2, x <= y, with prime p = A002313(n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A185389 Largest number k such that the greatest prime factor of k^2+1 is A002313(n), the n-th prime not congruent to 3 mod 4.

Views

Author

Keywords

Comments

Links

Crossrefs

A223702 Irregular triangle of numbers k such that A002313(n), the n-th prime not congruent to 3 mod 4 is the largest prime factor of k^2 + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A177979 Smallest number k such that A002313(n) divides k^2+1.

Views

Author

Keywords

Comments

Examples

References

Extensions

A185952 Partial products of A002313, the primes that are 1 or 2 (mod 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A285283 Number of integers x such that the greatest prime factor of x^2 + 1 is at most A002313(n), the n-th prime not congruent to 3 mod 4.