A002496 -id:A002496 - cp's OEIS frontend

A125256 Smallest odd prime divisor of n^2 + 1.

5, 5, 17, 13, 37, 5, 5, 41, 101, 61, 5, 5, 197, 113, 257, 5, 5, 181, 401, 13, 5, 5, 577, 313, 677, 5, 5, 421, 17, 13, 5, 5, 13, 613, 1297, 5, 5, 761, 1601, 29, 5, 5, 13, 1013, 29, 5, 5, 1201, 41, 1301, 5, 5, 2917, 17, 3137, 5, 5, 1741, 13, 1861, 5, 5, 17, 2113, 4357, 5, 5

Offset: 2

Nick Hobson, Nov 26 2006

Any odd prime divisor of n^2+1 is congruent to 1 modulo 4.
n^2+1 is never a power of 2 for n > 1; hence a prime divisor congruent to 1 modulo 4 always exists.
a(n) = 5 if and only if n is congruent to 2 or -2 modulo 5.
If the map "x -> smallest odd prime divisor of n^2+1" is iterated, does it always terminate in the 2-cycle (5 <-> 13)? - Zoran Sunic, Oct 25 2017

			The prime divisors of 8^2 + 1 = 65 are 5 and 13, so a(7) = 5.

D. M. Burton, Elementary Number Theory, McGraw-Hill, Sixth Edition (2007), p. 191.

Ray Chandler, Table of n, a(n) for n = 2..20001 (first 999 terms from Nick Hobson)

Cf. A002522, A002496, A014442, A057207, A031439.
For bisections see A256970, A293958.
See also A125257, A125258, A294656, A294657, A294658.

with(numtheory, factorset);
A125256 := proc(n) local t1,t2;
if n <= 1 then return(-1); fi;
if (n mod 5) = 2 or (n mod 5) = 3 then return(5); fi;
t1 := numtheory[factorset](n^2+1);
t2:=sort(convert(t1,list));
if (n mod 2) = 1 then return(t2[2]); fi;
t2[1];
end;
[seq(A125256(n),n=1..40)]; # N. J. A. Sloane, Nov 04 2017

Table[Select[First/@FactorInteger[n^2+1],OddQ][[1]],{n,2,68}] (* James C. McMahon, Dec 16 2024 *)

vector(68, n, if(n<2, "-", factor(n^2+1)[1+(n%2),1]))

A125256(n)=factor(n^2+1)[1+bittest(n,0),1] \\ M. F. Hasler, Nov 06 2017

A083847 a(n) = number of primes of the form x^2 + 1 <= 2^n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 14, 18, 24, 33, 42, 54, 70, 91, 114, 158, 212, 293, 393, 539, 713, 957, 1301, 1792, 2459, 3378, 4615, 6233, 8418, 11540, 15867, 21729, 29843, 41169, 56534, 77697, 106787, 147067, 203025, 280340, 387308, 535153, 739671, 1023655, 1416635, 1960813, 2716922, 3764693, 5218926, 7238715

Offset: 1

Harry J. Smith, May 05 2003

nonn

It is conjectured that the number of primes of the form x^2+1 is infinite and thus this sequence does not become a constant, but this has never been proved.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 17.
P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, 1991, p. 190.

C. K. Caldwell, An amazing prime heuristic.
Eric Weisstein's World of Mathematics, Landau's Problems.

Cf. A005574, A002496, A083844 - A083849.

a(n) = my(nb = 0); forprime(p=2, 2^n, if (issquare(p-1), nb++);); nb  \\ Michel Marcus, Jun 14 2013

More terms from Alexander D. Healy, Feb 06 2005

A180252 Numbers where all prime divisors are of the form k^2+1.

Original entry on oeis.org

1, 2, 4, 5, 8, 10, 16, 17, 20, 25, 32, 34, 37, 40, 50, 64, 68, 74, 80, 85, 100, 101, 125, 128, 136, 148, 160, 170, 185, 197, 200, 202, 250, 256, 257, 272, 289, 296, 320, 340, 370, 394, 400, 401, 404, 425, 500, 505, 512, 514

Offset: 1

Michel Lagneau, Jan 20 2011

nonn

			a(17) = 74 because 74 = 2*37 = (1^2+1)*(6^2+1).

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A002496, A002522, A005574.

with(numtheory):T:=array(1..50):U:=array(1..1000):k:=1:for m from 1 to 300
  do:x:=m^2+1:if type(x,prime)=true then T[k]:=x:k:=k+1:else fi:od:for x from
  2 to 2000 do: B:=factorset(x):yy:=nops(B):A:=convert(T, set):if A intersect
  B = B then printf(`%d, `, x):else fi:od:

Select[Range@520, And @@ IntegerQ /@ Sqrt[FactorInteger[#][[All, 1]] - 1] &] (* Ivan Neretin, Aug 31 2016 *)

Sum_{n>=1} 1/a(n) = Product_{p in A002496} p/(p-1) = Product_{k in A005574} (1 + 1/k^2) = 2.809865... - Amiram Eldar, Sep 27 2020

A193558 Differences between consecutive primes of the form k^2+1.

Original entry on oeis.org

3, 12, 20, 64, 96, 60, 144, 176, 100, 620, 304, 1316, 220, 1220, 1120, 1580, 1044, 736, 3264, 1356, 944, 976, 500, 1024, 1056, 3360, 1184, 1836, 1264, 3300, 2076, 1424, 1456, 7760, 820, 1664, 6076, 2724, 2796, 1904, 4900, 3036, 2064, 2096, 3204, 5500, 2256

Offset: 1

Michel Lagneau, Jul 30 2011

nonn

It is conjectured that the sequence of primes of the form k^2+1 is infinite, but this has never been proved. This sequence contains a subset of squares: {64, 144, 100, 1024, 4900, 10816, 11664, 12544, 18496, 102400, 41616, ...}.

			a(2) = 12 because (4^2+1)-(2^2+1) = 17 - 5 = 12.

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

Cf. A002496.

Differences[Select[Range[250]^2 + 1, PrimeQ]]

lista(nn) = my(v=select(x->issquare(x-1), primes(nn))); vector(#v-1, k, v[k+1] - v[k]) \\ Michel Marcus, Dec 04 2020

A199401 Decimal expansion of constant Product_{p>=3} (1 - (-1)^((p-1)/2)/(p-1)). Hardy-Littlewood constant of x^2 + 1.

Original entry on oeis.org

1, 3, 7, 2, 8, 1, 3, 4, 6, 2, 8, 1, 8, 2, 4, 6, 0, 0, 9, 1, 1, 2, 1, 9, 2, 6, 9, 6, 7, 2, 7, 0, 1, 8, 8, 6, 8, 1, 7, 8, 3, 3, 3, 1, 0, 1, 2, 5, 5, 7, 5, 9, 5, 5, 7, 9, 3, 6, 2, 3, 4, 1, 4, 7, 3, 2, 7, 8, 4, 2, 2, 2, 6, 7, 1, 7, 3, 7, 0, 2, 3, 1, 7, 2, 7, 7, 1

Offset: 1

N. J. A. Sloane, Nov 05 2011

Arises in studying A002496.

The constant is Product_{primes p} (1-chi(p)/(p-1)) where chi is the Dirichlet character A101455. Its Euler expansion is (1/(L(m=4,r=2,s=1)* zeta(m=4,n=3,s=2)) *Product_{s>=2} zeta(m=4,n=1,s)^gamma(s), where L and zeta are the functions tabulated in arXiv:1008.2547 and gamma is the sequence A001037. In particular L(m=4,r=2,s=1) = A003881 and zeta(m=4,n=1,s=2)=A175647. - R. J. Mathar, Nov 29 2011

			1.372813462818246009112192696727...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.1, p. 85.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 264.

T. Amdeberhan, L. A. Median, and V. H. Moll, Arithmetical properties of a sequence arising from an arctangent sum, J. Numb. Theory 128 (2008) 1807-1846, eq. (1.10).
Karim Belabas and Henri Cohen, Computation of the Hardy-Littlewood constant for quadratic polynomials, PARI/GP script, 2020.
Henri Cohen, High-precision computation of Hardy-Littlewood constants, (1998). [pdf copy, with permission]
G. H. Hardy and J. E. Littlewood, Some problems of 'Partitio numerorum'; III: On the expression of a number as a sum of primes, Acta Math., Vol. 44, No. 1 (1923), pp. 1-70. See Section 5.41.
Richard J. Mathar, Table of Dirichlet L-Series and Prime Zeta Modulo Functions for Small Moduli, arXiv:1008.2547 [math.NT], 2010-2015.
Marek Wolf, Search for primes of the form m^2+1, arXiv:0803.1456 [math.NT], 2008-2010.

Cf. A002496.
Cf. A001037, A003881, A083844, A175647, A221712, A331942.
Equals 2*constant given by A331941.

\\ See Belabas, Cohen link. Run as HardyLittlewood2(x^2+1) after setting the required precision.

Extended title, a(30) and beyond from Hugo Pfoertner, Feb 16 2020

A206400 Number of composites of the form n^2 + 1 between two successive primes of this form.

Original entry on oeis.org

0, 1, 1, 3, 3, 1, 3, 3, 1, 9, 3, 13, 1, 9, 7, 9, 5, 3, 15, 5, 3, 3, 1, 3, 3, 11, 3, 5, 3, 9, 5, 3, 3, 19, 1, 3, 13, 5, 5, 3, 9, 5, 3, 3, 5, 9, 3, 15, 5, 7, 11, 13, 9, 33, 1, 9, 3, 5, 13, 9, 5, 3, 3, 19, 1, 3, 3, 15, 5, 39, 7, 11, 13, 5, 7, 9, 39, 1, 7, 1, 7

Offset: 1

Michel Lagneau, Feb 07 2012

nonn

a(n) is the number of composites of A134406 between A002496(n) and A002496(n+1).

			a(4) = 3 because there exist 3 composite numbers of the form n^2+1 : {50, 65, 82} between A002496(4) = 37 and A002496(5) = 101.

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A002522, A002496, A134406.

i:=0:for n from 2 to 1000 do:x:=n^2+1:if type (x,prime)=true then printf(`%d, `,i):i:=0:else i:=i+1:fi:od:

cfn2[{a_,b_}]:=Count[Range[a+1,b-1],?(IntegerQ[Sqrt[#-1]]&)]; cfn2/@ Partition[ Select[Prime[Range[50000]],IntegerQ[Sqrt[#-1]]&],2,1] (* _Harvey P. Dale, Jan 13 2019 *)

c=0; for(n=2,1e9, !ispseudoprime(n^2+1) & c++ & next; print1(c","); c=0) \\ M. F. Hasler, Feb 07 2012

A240587 Primes p of the form n^2 + 123456789 where 123456789 is the first zeroless pandigital number.

Original entry on oeis.org

123457189, 123459289, 123465253, 123466789, 123470713, 123481753, 123482389, 123486373, 123489913, 123501733, 123505189, 123510613, 123535189, 123545593, 123564373, 123571033, 123584953, 123587833, 123592213, 123610453, 123631513, 123641689, 123657493

Offset: 1

K. D. Bajpai, Apr 08 2014

			123457189 is a prime and appears in the sequence because 123457189 = 20^2 + 123456789.
123459289 is a prime and appears in the sequence because 123459289 = 50^2 + 123456789.

K. D. Bajpai, Table of n, a(n) for n = 1..1111

Cf. A000040, A002496, A028871, A050289, A056899.

KD := proc() local a; a:=n^2+123456789; if isprime(a) then RETURN (a); fi; end: seq(KD(), n=1..1000);

Select[Table[k^2+123456789,{k,1,3000}],PrimeQ]

A279967 Square array read by antidiagonals upwards in which each term is the sum of prior elements in the same row, column, diagonal, or antidiagonal that divide n; the array is seeded with an initial value a(1)=1.

Original entry on oeis.org

1, 1, 2, 2, 2, 7, 2, 9, 10, 15, 2, 10, 1, 13, 17, 8, 0, 13, 1, 14, 9, 8, 0, 13, 3, 30, 13, 10, 2, 16, 1, 23, 5, 7, 14, 15, 2, 8, 28, 32, 2, 23, 2, 9, 49, 12, 0, 48, 2, 11, 1, 20, 3, 18, 13, 28, 0, 4, 1, 56, 5, 8, 16, 35, 46, 4, 2, 6, 2, 10

Offset: 1

Alec Jones, Dec 24 2016

From Hartmut F. W. Hoft, Jan 23 2017: (Start)
Shown by induction and direct (modular) computations for
column 1: Every number is even, except for the first two 1's; in addition to row 3, value 2 occurs in rows 4*k and 4*k+1, and every value in rows 4*k+2 and 4*k+3 is divisible by 4, for all k>=1.
column 2: The first four entries, 2, 2, 9 and 10, contain the only odd number; no nonzero entry in row k>3 has 9 as a factor, and value 0 occurs in rows 4*k+1 and 4*k+2, for all k>=1.
Conjecture:
a({1, 6, 8, 9, 10, 15, 26, 45, 48, 84, 96, 112, 115, 252, 336, 343}) =
  {1, 7, 9,10, 15, 17, 30, 49, 48,104,117, 115, 122, 257, 343, 395} are the only numbers in the sequence with the property a(n) >= n (verified through n=500500, i.e., the triangle with 1000 antidiagonals).
This conjecture together with Bouniakowsky's conjecture that certain quadratic integer polynomials generate infinitely many primes (e.g. see A002496 for n^2+1 and A188382 for 2*n^2+n+1) implies that in every column in the triangle infinitely many prime sequence indices occur and therefore infinitely many 0's whenever the column contains no 1's. The proof is based on the fact that for a large enough prime sequence index p in whose prior column no 1 occurs then a(p)=0; therefore infinitely many 0's occur in that column. Obviously, once value 1 occurs in a column no 0 value can occur in a subsequent row.
Conjecture:
Every row in the triangle contains exactly two 1's.
(End)

			After 6 terms, the array looks like:
.
1   2   7
1   2
2
We have a(6) = 7 because a(1) = 1, a(3) = 2, a(4) = 2, and a(5) = 2 divide 6; 1 + 2 + 2 + 2 = 7.
From _Hartmut F. W. Hoft_, Jan 23 2017: (Start)
1   2   7  15  17   9  10  15  49  13   4  31  22
1   2  10  13  14  13  14   9  18  46  12  66
2   9   1   1  30   7   2   3  35  12   3
2  10  13   3   5  23  20  16  14  17
2   0  13  23   2   1   8  11   2
8   0   1  32  11   5   3   6
8  16  28   2  56  42   8
2   8  48   1   2 104
2   0   4  10   1
12   0   2  10
28   6   2
2  42
2
.
Expanded the triangle to the first 13 antidiagonals of the array, i.e. a(1) ... a(91), to show the start of the 2- and 0-value patterns in columns 1 and 2. The first 0 beyond column 2 is a(677) in row 27, column 11 of the triangle.
A188382(n)=2*n^2+n+1 for n>=0 are the alternate sequence indices for column 1 starting in row 1, 2*n^2+n+2 for n>=1 are the alternate sequence indices for column 2 starting in row 2, and 2*n^2+n+11 for n>=5 are the alternate sequence indices for column 11 starting in row 1.
The sequence indices in the triangle for row positions k>=1 in columns 1,..., 5 are given in sequences A000124(k), A152948(k+3), A152950(k+3), A145018(k+4) and A167499(k+4).
(End)

Peter Kagey, Table of n, a(n) for n = 1..5000

Cf. A279966 for the related sequence which counts prior terms.
Cf. A269347 for a one-dimensional version of this sequence.
Cf. also A279211, A279212.
Cf. A000124, A002496, A145018, A152948, A152950, A167499, A188382.

(*  printing of the triangle is commented out of function a279967[]  *)
pCol[{i_, j_}] := Map[{#, j}&, Range[1, i-1]]
pDiag[{i_, j_}] := If[j>=i, Map[{#, j-i+#}&, Range[1, i-1]], Map[{i-j+#, #}&, Range[1, j-1]]]
pRow[{i_, j_}] := Map[{i, #}&, Range[1, j-1]]
pAdiag[{i_, j_}] := Map[{i+j-#, #}&, Range[1, j-1]]
priorPos[{i_, j_}] := Join[pCol[{i, j}], pDiag[{i, j}], pRow[{i, j}], pAdiag[{i, j}]]
seqPos[{i_, j_}] := (i+j-2)(i+j-1)/2+j
antiDiag[k_] := Map[{k+1-#, #}&, Range[1, k]]
upperTriangle[k_] := Flatten[Map[antiDiag, Range[1, k]], 1]
a279967[k_] := Module[{ut=upperTriangle[k], ms=Table[" ", {i, 1, k}, {j, 1, k}], h, pos, val, seqL={1}}, ms[[1, 1]]=1; For[h=2, h<=Length[ut], h++, pos=ut[[h]]; val=Apply[Plus, Select[Map[ms[[Apply[Sequence, #]]]&, priorPos[pos]], #!=0 && Mod[seqPos[pos], #]==0&]]; AppendTo[seqL, val]; ms[[Apply[Sequence, pos]]]=val]; (* Print[TableForm[ms]]; *) seqL]
a279967[13] (* values in first 13 antidiagonals *)
(* Hartmut F. W. Hoft, Jan 23 2017 *)

A054754 Totient(n) and cototient(n) are squares.

Original entry on oeis.org

1, 2, 5, 8, 17, 32, 37, 101, 125, 128, 197, 257, 401, 468, 512, 577, 677, 1297, 1417, 1601, 1872, 2048, 2340, 2917, 3125, 3137, 3145, 4100, 4212, 4357, 4913, 5477, 7057, 7488, 8101, 8192, 8837, 9360, 12101, 13457, 14401, 14841, 15377, 15588, 15877

Offset: 1

Labos Elemer, Apr 25 2000

nonn

Subsequence of A039770, supersequence of A002496.
a(n) is an odd power of a prime q = w^2+1, like 4913 = 17^3, where A000010(a(31)) = phi(4913) = 4624 = 68^2 and A051953(4913) = 4913-4624 = 289 = 17^2.
a(n) is not an odd power of a prime of A002496, like a(14) = 468, where phi(468) = 144 and 468-phi(468) = 324 = 18^2.
Intersection of A039770 and A063752. - Altug Alkan, Aug 16 2017

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A000010, A002496, A039770, A051953, A063752.

Select[Range@ 16000, Function[n, AllTrue[{#, n - #} &@ EulerPhi@ n, IntegerQ@ Sqrt@ # &]]] (* Michael De Vlieger, Aug 16 2017 *)

isok(n) = issquare(eulerphi(n)) && issquare(n-eulerphi(n)); \\ Michel Marcus, Sep 09 2013

A000010(a(n))=x^2 and a(n)-A000010(a(n))=y^2.

A056893 Smallest prime with square excess of n.

Original entry on oeis.org

2, 3, 7, 13, 41, 31, 23, 89, 73, 59, 47, 61, 113, 239, 79, 97, 593, 139, 163, 461, 277, 191, 167, 193, 281, 251, 223, 317, 353, 991, 431, 761, 433, 563, 359, 397, 521, 479, 439, 569, 617, 571, 619, 773, 829, 887, 947, 673, 1493, 1571, 727, 1013, 953, 1279

Offset: 1

Henry Bottomley, Jul 05 2000

nonn

			a(4)=13 since 13=3^2+4, while 2, 3, 5, 7 and 11 have square excesses of 1, 2, 1, 3 and 3 respectively.

Cf. A053186, A000196, A002496, A048760, A056892-A056898.

A056893 := proc(n)
    local p ;
    p :=2 ;
    while A053186(p) <> n do
        p := nextprime(p) ;
    end do:
    return p ;
end proc: # R. J. Mathar, Jul 28 2013

A056893(n)={
    local(p=2) ;
    while( A053186(p)!=n,
        p=nextprime(p+1)
    ) ;
    return(p)
} /* R. J. Mathar, Jul 28 2013 */

a(n) =n+A056894(n).

a(n) = min{p in A000040: A053186(p) = n}. - R. J. Mathar, Jul 28 2013

cp's OEIS Frontend

A125256 Smallest odd prime divisor of n^2 + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A083847 a(n) = number of primes of the form x^2 + 1 <= 2^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A180252 Numbers where all prime divisors are of the form k^2+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A193558 Differences between consecutive primes of the form k^2+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A199401 Decimal expansion of constant Product_{p>=3} (1 - (-1)^((p-1)/2)/(p-1)). Hardy-Littlewood constant of x^2 + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A206400 Number of composites of the form n^2 + 1 between two successive primes of this form.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A240587 Primes p of the form n^2 + 123456789 where 123456789 is the first zeroless pandigital number.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs