%I A002496 M1506 N0592
%S A002496 2,5,17,37,101,197,257,401,577,677,1297,1601,2917,3137,4357,5477,
%T A002496 7057,8101,8837,12101,13457,14401,15377,15877,16901,17957,21317,
%U A002496 22501,24337,25601,28901,30977,32401,33857,41617,42437,44101,50177
%N A002496 Primes of form n^2 + 1.
%C A002496 It is conjectured that this sequence is infinite, but this has never 
               been proved.
%C A002496 An equivalent description: primes of form m = (p1*p2*...*pm)^k + 1 where 
               p1 ... pm are primes and k>1, since then k must be even for m to 
               be prime.
%C A002496 Also prime = p(n) if A054269(n) = 1, i.e. quotient-cycle-length = 1 in 
               continued fraction expansion of sqrt(p) - Labos E. (labos(AT)ana.sote.hu), 
               Feb 21 2001
%C A002496 Also primes p such that phi(p) is a square.
%C A002496 Also primes of form x*y + z, where x, y and z are three successive numbers. 
               - Giovanni Teofilatto (g.teofilatto(AT)tiscalinet.it), Jun 05 2004
%C A002496 From Pieter Moree (moree(AT)science.uva.nl), Nov 03 2003: It is a result 
               that goes back to Mirsky that the set of primes p for which p-1 is 
               squarefree has density A, where A denotes the Artin constant (A = 
               prod_q (1-1/(q(q-1))), q running over all primes). Numerically A 
               = 0.3739558136.... More precisely, Sum_{p <= x} mu(p-1)^2 = Ax/log 
               x + o(x/log x) as x tends to infinity. Conjecture: sum_{p <= x, mu(p-1)=1} 
               1 = (A/2)x/log x + o(x\log x) and sum_{p <= x, mu(p-1)=-1} 1 = (A/
               2)x/log x + o(x/log x).
%C A002496 Also primes of the form x^y + 1, where x>0, y>1. Primes of the form x^y 
               - 1 (x>0, y>1) are the Mersenne primes listed in A000668(n) = {3, 
               7, 31, 127, 8191, 131071, 524287, 2147483647, ...}. - Alexander Adamchuk 
               (alex(AT)kolmogorov.com), Mar 04 2007
%C A002496 Also, if p=n^2+1, the congruence p^m=1 mod (n) is always verified for 
               all m. Example: p=5, n=2, then 5^m=1 mod(2), 5=1 mod(2), 5^2=1 mod(2), 
               5^3=1 mod(2); p=37, n=6, then 37^3=1 mod (6); p=101, n=10, then 101^5=1 
               mod (10) [From Vincenzo Librandi (vincenzo.librandi(AT)tin.it), Feb 
               05 2009]
%D A002496 J.-M. De Koninck & A. Mercier, 1001 Problemes en Theorie Classique Des 
               Nombres, Problem 211 pp. 34; 169, Ellipses Paris 2004.
%D A002496 L. Euler, De numeris primis valde magnis (E283), reprinted in: Opera 
               Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 3, p. 22.
%D A002496 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 
               5th ed., Oxford Univ. Press, 1979, th. 17.
%D A002496 Leon Mirsky, Amer. Math. Monthly 56 (1949), 17-19.
%D A002496 H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number 
               Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
%D A002496 C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 
               116.
%D A002496 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002496 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002496 David Wells, The Penguin Dictionary of Curious and Interesting Numbers 
               (Rev. ed. 1997), p. 134
%H A002496 T. D. Noe, <a href="b002496.txt">Table of n, a(n) for n=1..10000</a>
%H A002496 W. D. Banks, J. B. Friedlander, C. Pomerance and I. E. Shparlinski, <a 
               href="http://math.dartmouth.edu/~carlp/PDF/banksfinal2.pdf">Multiplicative 
               structure of values of the Euler function</a>, in High Primes and 
               Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh 
               Cowie Williams (A. Van der Poorten, ed.), Fields Inst. Comm. 41 (2004), 
               pp. 29-47.
%H A002496 F. Ellermann, <a href="a002496.txt">Primes of the form (m^2)+1 up to 
               10^6</a>
%H A002496 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               LandausProblems.html">Landau's Problems.</a>
%H A002496 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Near-SquarePrime.html">Near-Square Prime</a>
%H A002496 Marek Wolf, <a href="http://arXiv.org/abs/0803.1456">Search for primes 
               of the form m^2+1</a>
%F A002496 There are O(sqrt(n)/log(n)) members of this sequence up to n.
%t A002496 Intersection[Table[n^2 + 1, {n, 225}], Prime[Range[5153]]]
%t A002496 s="";For[i=1, i<10^2, If[PrimeQ[i^2+1], s=s<>ToString[i^2+1]<>", "];i++ 
               ];Print[s] (from Vladimir Orlovsky (4vladimir(AT)gmail.com), Apr 
               29 2008)
%Y A002496 Cf. A083844 (number of these primes < 10^n).
%Y A002496 Cf. A001912, A005574, A054964, A062325, A088179, A090693, A141293.
%Y A002496 Cf. A000668 = Mersenne primes.
%Y A002496 Subsequence of A039770.
%Y A002496 Sequence in context: A107630 A078523 A078324 this_sequence A127436 A064168 
               A118727
%Y A002496 Adjacent sequences: A002493 A002494 A002495 this_sequence A002497 A002498 
               A002499
%K A002496 nonn,easy,nice
%O A002496 1,1
%A A002496 N. J. A. Sloane (njas(AT)research.att.com).
%E A002496 Formula, reference, and comment from Charles R Greathouse IV (charles.greathouse(AT)case.edu), 
               Aug 24 2009