The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002496 Primes of the form k^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 the form k^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 the first two terms {2,5}, the 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 From _Bernard Schott_, Mar 22 2019: (Start)

%C These primes are the primitive terms which generate the sequence of integers with only one prime factor and whose Euler's totient is square: A054755. So this sequence is a subsequence of A054755 and of A039770. Additionally, the terms of this sequence also have a square cototient, so this sequence is a subsequence of A063752 and A054754.

%C If p prime = n^2 + 1, phi(p) = n^2 and cototient(p) = 1^2.

%C Except for 3, the four Fermat primes in A019434 {5, 17, 257, 65537}, belong to this sequence; with F_k = 2^(2^k) + 1, phi(F_k) = (2^(2^(k-1)))^2.

%C See the file "Subfamilies and subsequences" (& I) in A039770 for more details, proofs with data, comments, formulas and examples. (End)

%C In this sequence, primes ending with 7 seem to appear twice as often as primes ending with 1. This is because those with 7 come from integers ending with 4 or 6, while those with 1 come only from integers ending with 0 (see De Koninck & Mercier reference). - _Bernard Schott_, Nov 29 2020

%D Jean-Marie De Koninck & Armel Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 211 pp. 34 and 169, Ellipses, Paris, 2004.

%D Leonhard 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 Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.

%D C. Stanley 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 Tewodros Amdeberhan, Luis A. Medina and Victor 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, Vol. 128, No. 6 (2008), pp. 1807-1846, eq. (1.10).

%H William D. Banks, John B. Friedlander, Carl Pomerance and Igor 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 Paul T. Bateman and Roger 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, Vol. 16, No. 79 (1962), pp. 363-367.

%H N. A. Carella, <a href="https://arxiv.org/abs/1912.05923">The Euler Polynomial Prime Values Problem</a>, arXiv:1912.05923 [math.GM], 2019.

%H Frank 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, Vol. 56, No. 1 (1949), pp. 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 Apoloniusz Tyszka, <a href="https://philarchive.org/rec/TYSDAS">On sets X subset of N for which we know an algorithm that computes a threshold number t(X) in N such that X is infinite if and only if X contains an element greater than t(X)</a>, 2019.

%H Apoloniusz Tyszka and Sławomir Kurpaska, <a href="https://philarchive.org/archive/TYSDASv104">Open problems that concern computable sets X, subset of N, and cannot be formally stated as they refer to current knowledge about X</a>, (2020).

%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-2010.

%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

%F Sum_{n>=1} 1/a(n) = A172168. - _Amiram Eldar_, Nov 14 2020

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

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

%t Join[{2},Select[Range[2,300,2]^2+1,PrimeQ]] (* _Harvey P. Dale_, Dec 18 2018 *)

%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, A172168.

%Y Cf. A000668 (Mersenne primes), A019434 (Fermat 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 Subsequence of A039770, A054754, A054755, A063752.

%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).

%Y Cf. A030430 (primes ending with 1), A030432 (primes ending with 7).

%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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 00:03 EDT 2021. Contains 342877 sequences. (Running on oeis4.)