This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002496 Primes of form n^2 + 1.
(Formerly M1506 N0592)

%I M1506 N0592

%S 2,5,17,37,101,197,257,401,577,677,1297,1601,2917,3137,4357,5477,7057,

%T 8101,8837,12101,13457,14401,15377,15877,16901,17957,21317,22501,

%U 24337,25601,28901,30977,32401,33857,41617,42437,44101,50177

%N Primes of form n^2 + 1.

%C It is conjectured that this sequence is infinite, but this has never been proved.

%C An equivalent description: primes of form P = (p1*p2*...*pm)^k + 1 where p1 ... pm are primes and k > 1, since then k must be even for P to be prime.

%C Also prime = p(n) if A054269(n) = 1, i.e., quotient-cycle-length = 1 in continued fraction expansion of sqrt(p) - _Labos Elemer_, Feb 21 2001

%C Also primes p such that phi(p) is a square.

%C Also primes of form x*y + z, where x, y and z are three successive numbers. - _Giovanni Teofilatto_, Jun 05 2004

%C 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). - Pieter Moree (moree(AT)mpim-bonn.mpg.de), Nov 03 2003

%C 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_, Mar 04 2007

%C With exception of two first terms {2,5} continued fraction (1 + sqrt(p))/2 has period 3. - _Artur Jasinski_, Feb 03 2010

%C With exception of the first term {2} congruent to 1 mod 4. - _Artur Jasinski_, Mar 22 2011

%C With exception of the first two terms, congruent to 1 or 17 mod 20. - _Robert Israel_, Oct 14 2014

%C Beginning at a(2)=5 a k exists such that all terms in this sequence can be found with ((2*k+1)*2*k+5) + (2*k+3)*(2*k+7) + (2*k+5)*(2*k+9) + (2*k+7)*(2*k+11))/4. The same is true for 4*k^2 + 24*k + 37. For k=1, a(4) = 37 = (1*5 + 3*7 + 5*6 + 7*11)/4. - _J. M. Bergot_, Nov 09 2014

%D J.-M. De Koninck & A. Mercier, 1001 Problemes en Theorie Classique Des Nombres, Problem 211 pp. 34; 169, Ellipses Paris 2004.

%D L. Euler, De numeris primis valde magnis (E283), reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 3, p. 22.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 17.

%D H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.

%D C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 116.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D David Wells, The Penguin Dictionary of Curious and Interesting Numbers (Rev. ed. 1997), p. 134

%H T. D. Noe, <a href="/A002496/b002496.txt">Table of n, a(n) for n = 1..10000</a>

%H T. Amdeberhan, L. A. Median, V. H. Moll, <a href="http://dx.doi.org/10.1016/j.jnt.2007.05.008">Arithmetical properties of a sequence arising from an arctangent sum</a>, J. Numb. Theory 128 (2008) 1807-1846, eq. (1.10).

%H 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 P. Bateman and R. A. Horn, <a href="http://dx.doi.org/10.1090/S0025-5718-1962-0148632-7">A heuristic asymptotic formula concerning the distribution of prime numbers</a>, Mathematics of Computation, 16 (1962), 363-367.

%H F. Ellermann, <a href="/A002496/a002496.txt">Primes of the form (m^2)+1 up to 10^6</a>

%H Leon Mirsky, <a href="http://www.jstor.org/stable/2305811">The number of representations of an integer as the sum of a prime and a k-free integer</a>, Amer. Math. Monthly 56 (1949), 17-19.

%H Maxie D. Schmidt, <a href="https://arxiv.org/abs/1701.04741">New Congruences and Finite Difference Equations for Generalized Factorial Functions</a>, arXiv:1701.04741 [math.CO], 2017.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LandausProblems.html">Landau's Problems.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Near-SquarePrime.html">Near-Square Prime</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Bateman%E2%80%93Horn_conjecture">Bateman-Horn Conjecture</a>

%H Marek Wolf, <a href="http://arXiv.org/abs/0803.1456">Search for primes of the form m^2+1</a>, arXiv:0803.1456 [math.NT], 2008.

%F There are O(sqrt(n)/log(n)) members of this sequence up to n. But this is just an upper bound. See the Bateman-Horn or Wolf papers, for example, for the conjectured for what is believed to be the correct density.

%F a(n) = 1 + A005574(n)^2. - _R. J. Mathar_, Jul 31 2015

%p select(isprime, [2, seq(4*i^2+1, i= 1..1000)]); # _Robert Israel_, Oct 14 2014

%t Select[Range[100]^2+1, PrimeQ]

%o (PARI) isA002496(n) = isprime(n) && issquare(n-1) \\ _Michael B. Porter_, Mar 21 2010

%o (PARI) is_A002496(n)=issquare(n-1)&&isprime(n) \\ For "random" numbers in the range 10^10 and beyond, at least 5 times faster than the above. - _M. F. Hasler_, Oct 14 2014

%o (MAGMA) [p: p in PrimesUpTo(100000)| IsSquare(p-1)]; // Vincenzo Librandi, Apr 09 2011

%o (Haskell)

%o a002496 n = a002496_list !! (n-1)

%o a002496_list = filter ((== 1) . a010051') a002522_list

%o -- _Reinhard Zumkeller_, May 06 2013

%o (Python)

%o # Python 3.2 or higher required

%o from itertools import accumulate

%o from sympy import isprime

%o A002496_list = [n+1 for n in accumulate(range(10**5),lambda x,y:x+2*y-1) if isprime(n+1)] # _Chai Wah Wu_, Sep 23 2014

%o (Python)

%o # Python 2.4 or higher required

%o from sympy import isprime

%o A002496_list = list(filter(isprime, (n*n+1 for n in range(10**5)))) # _David Radcliffe_, Jun 26 2016

%Y Cf. A083844 (number of these primes < 10^n), A199401 (growth constant).

%Y Cf. A001912, A005574, A054964, A062325, A088179, A090693, A141293.

%Y Cf. A000668 = Mersenne primes.

%Y Subsequence of A039770.

%Y Cf. A010051, subsequence of A002522.

%Y Cf. A237040 (an analog for n^3 + 1).

%Y Cf. A010051, A000290; subsequence of A028916.

%Y Primes of form n^2+b^4, b fixed: A243451 (b=2), A256775 (b=3), A256776 (b=4), A256777 (b=5), A256834 (b=6), A256835 (b=7), A256836 (b=8), A256837 (b=9), A256838 (b=10), A256839 (b=11), A256840 (b=12), A256841 (b=13).

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_

%E Formula, reference, and comment from _Charles R Greathouse IV_, Aug 24 2009

%E Edited by _M. F. Hasler_, Oct 14 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 17 09:45 EST 2018. Contains 297815 sequences.