A002496 -id:A002496 - cp's OEIS frontend

A056993 a(n) is the smallest k >= 2 such that k^(2^n)+1 is prime, or -1 if no such k exists.

2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444

Offset: 0

Robert G. Wilson v, Sep 06 2000

Smallest base value yielding generalized Fermat primes. - Hugo Pfoertner, Jul 01 2003
The first 5 terms correspond with the known (ordinary) Fermat primes. A probable candidate for the next entry is 62722^131072+1, discovered by Michael Angel in 2003. It has 628808 decimal digits. - Hugo Pfoertner, Jul 01 2003
For any n, a(n+1) >= sqrt(a(n)), because k^(2^(n+1))+1 = (k^2)^(2^n)+1. - Jeppe Stig Nielsen, Sep 16 2015
Does the sequence contain any perfect squares? If a(n) is a perfect square, then a(n+1) = sqrt(a(n)). - Jeppe Stig Nielsen, Sep 16 2015
If for a particular n, a(n) exists, then a(i) exist for all i=0,1,2,...,n. No proof is known that this sequence is infinite. Such a result would clearly imply the infinitude of A002496. - Jeppe Stig Nielsen, Sep 18 2015
919444 is a candidate for a(20). See Zimmermann link. -  Serge Batalov, Sep 02 2017
Now PrimeGrid has tested and double checked all b^(2^20) + 1 with b < 919444, so we have proof that a(20) = 919444. - Jeppe Stig Nielsen, Dec 30 2017

			The primes are 2^(2^0) + 1 = 3, 2^(2^1) + 1 = 5, 2^(2^2) + 1 = 17, 2^(2^3) + 1 = 257, 2^(2^4) + 1 = 65537, 30^(2^5) + 1, 102^(2^6) + 1, ....

Yves Gallot, Generalized Fermat Prime Search
Lucile and Yves Gallot, Generalized Fermat Prime Search
Michael Goetz, id=103235 of Top 5000 Primes
Luke Harmon, Gaetan Delavignette, Arnab Roy, and David Silva, PIE: p-adic Encoding for High-Precision Arithmetic in Homomorphic Encryption, Cryptology ePrint Archive 2023/700.
Stephen Scott, id=84401 of Top 5000 Primes
Sylvanus A. Zimmerman, PrimeGrid’s Generalized Fermat Prime Search

Cf. A006093, A005574, A000068, A006314, A006313, A006315, A006316, A056994, A056995, A057465, A057002, A088361, A088362, A226528, A226529, A226530, A251597, A253854, A244150, A243959, A321323.

Cf. A019434 (Fermat primes).

f[n_] := (p = 2^n; k = 2; While[cp = k^p + 1; !PrimeQ@cp, k++ ]; k); Do[ Print[{n, f@n}], {n, 0, 17}] (* Lei Zhou, Feb 21 2005 *)

a(n)=my(k=2);while(!isprime(k^(2^n)+1),k++);k \\ Anders Hellström, Sep 16 2015

a(n) = A085398(2^(n+1)). - Jianing Song, Jun 13 2022

from Robert G. Wilson v, Oct 30 2000
from Jeppe Stig Nielsen, Aug 07 2005
and 75898 from Lei Zhou, Feb 01 2012
919444 from Jeppe Stig Nielsen, Dec 30 2017

A037896 Primes of the form k^4 + 1.

Original entry on oeis.org

2, 17, 257, 1297, 65537, 160001, 331777, 614657, 1336337, 4477457, 5308417, 8503057, 9834497, 29986577, 40960001, 45212177, 59969537, 65610001, 126247697, 193877777, 303595777, 384160001, 406586897, 562448657, 655360001, 723394817, 916636177, 1049760001, 1416468497

Offset: 1

Donald S. McDonald, Feb 27 2000

From Bernard Schott, Apr 22 2019: (Start)
These primes are the primitive terms which generate the sequence of integers with only one prime factor and whose Euler's totient is a perfect biquadrate: A307690, so this sequence is a subsequence of A078164 and A307690.
If p prime = k^4 + 1, phi(p) = k^4.
The last three Fermat primes in A019434 {17, 257, 65537} belong to this sequence; with F_k = 2^(2^k) + 1 and for k = 2, 3, 4, phi(F_k) = (2^(2^(k-2)))^4. (End)

			6^4 + 1 = 1297 is prime.

T. D. Noe, Table of n, a(n) for n=1..1000
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
M. Lal, Primes of the form n^4 + 1, Math. Comp. 21 (1967), pp. 245-247.

Cf. A000068, A002523, A019434, A078164, A307690.

Subsequence of A002496, A078164 and A039770.

[n^4+1: n in [1..200] | IsPrime(n^4+1)]; // G. C. Greubel, Apr 28 2019

Select[Range[200]^4+1,PrimeQ] (* Harvey P. Dale, Jul 20 2015 *)

j=[]; for(n=1,200, if(isprime(n^4+1),j=concat(j,n^4+1))); j

list(lim)=my(v=List([2]),p); forstep(k=2,sqrtnint(lim\1-1,4),2, if(isprime(p=k^4+1), listput(v,p))); Vec(v) \\ Charles R Greathouse IV, Mar 31 2022

[n^4+1 for n in (1..200) if is_prime(n^4+1)] # G. C. Greubel, Apr 28 2019

a(n) = A002523(A000068(n)). - Elmo R. Oliveira, Feb 21 2025

Corrected and extended by Jason Earls, Jul 19 2001

A089120 Smallest prime factor of n^2 + 1.

Original entry on oeis.org

2, 5, 2, 17, 2, 37, 2, 5, 2, 101, 2, 5, 2, 197, 2, 257, 2, 5, 2, 401, 2, 5, 2, 577, 2, 677, 2, 5, 2, 17, 2, 5, 2, 13, 2, 1297, 2, 5, 2, 1601, 2, 5, 2, 13, 2, 29, 2, 5, 2, 41, 2, 5, 2, 2917, 2, 3137, 2, 5, 2, 13, 2, 5, 2, 17, 2, 4357, 2, 5, 2, 13, 2, 5, 2, 5477, 2, 53, 2, 5, 2, 37, 2, 5, 2

Offset: 1

Cino Hilliard, Dec 05 2003

This includes A002496, primes that are of the form n^2+1.

Note that a(n) is the smallest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

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

[Min(PrimeDivisors(n^2+1)):n in [1..100]]; // Marius A. Burtea, Nov 13 2019

Array[FactorInteger[#^2 + 1][[1, 1]] &, {83}] (* Michael De Vlieger, Sep 08 2015 *)

smallasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v[1]",") ) }

A089120(n)=factor(n^2+1)[1,1]  \\ M. F. Hasler, Mar 11 2012

a(2k+1)=2; a(10k +/- 2)=5, else a(26k +/- 8)=13, else a(34k +/- 4)=17, else a(58k +/- 12)=29, else a(74k +/- 6)=37,... - M. F. Hasler, Mar 11 2012

A089120(n) = 2 if n is odd, else A089120(n) = min { A002144(k) | n = +/- A209874(k) (mod 2*A002144(k)) }.

A056892 a(n) = square excess of the n-th prime.

Original entry on oeis.org

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

Offset: 1

Henry Bottomley, Jul 05 2000

nonn

			a(5) = 2 since the 5th prime is 11 = 3^2 + 2.
From _M. F. Hasler_, Oct 19 2018: (Start)
Written as a table, starting a new row when a square is reached, the sequence reads:
  1, 2,    // = 2 - 1, 3 - 1 = {primes between 1^2 = 1 and 2^2 = 4} - 1
  1, 3,     // = 5 - 4, 7 - 4 = {primes between 2^2 = 4 and 3^2 = 9} - 4
  2, 4,      // = 11 - 9, 13 - 9 = {primes between 3^2 = 9 and 4^2 = 16} - 9
  1, 3, 7,    // = 17 - 16, 19 - 16, 23 - 16 = {primes between 16 and 25} - 16
  4, 6,        // = 29 - 25, 31 - 25 = {primes between 5^2 = 25 and 6^2 = 36} - 25
  1, 5, 7, 11,  // = {37, 41, 43, 47: primes between 6^2 = 36 and 7^2 = 49} - 36
  4, 10, 12,    // = {53, 59, 61: primes between 7^2 = 49 and 8^2 = 64} - 49
  3, 7, 9, 15,  // = {67, 71, 73, 79: primes between 8^2 = 64 and 9^2 = 81} - 64
  2, 8, 16,     // = {83, 89, 97: primes between 9^2 = 81 and 10^2 = 100} - 81
  etc. (End)

M. F. Hasler, Table of n, a(n) for n = 1..10000

Cf. A000040, A000196, A002496, A048760, A053186, A056893 .. A056898.

When written as a table, row lengths are A014085, and row sums are A108314 - A014085 * A000290 = A320688.

lst={};Do[p=Prime[n];s=p^(1/2);f=Floor[s];a=f^2;d=p-a;AppendTo[lst,d],{n,6!}];lst (* Vladimir Joseph Stephan Orlovsky, Mar 11 2009 *)
#-Floor[Sqrt[#]]^2&/@Prime[Range[90]] (* Harvey P. Dale, Jul 06 2014 *)

A056892(n)={my(p=prime(n));p-sqrtint(p)^2} \\ M. F. Hasler, Oct 04 2009

a(n) = A053186(A000040(n)).

a(n) = A000040(n) - A000006(n)^2. - M. F. Hasler, Oct 04 2009

A134406 Composite numbers of the form k^2 + 1.

Original entry on oeis.org

10, 26, 50, 65, 82, 122, 145, 170, 226, 290, 325, 362, 442, 485, 530, 626, 730, 785, 842, 901, 962, 1025, 1090, 1157, 1226, 1370, 1445, 1522, 1682, 1765, 1850, 1937, 2026, 2117, 2210, 2305, 2402, 2501, 2602, 2705, 2810, 3026, 3250, 3365, 3482, 3601, 3722, 3845

Offset: 1

Jani Melik, Jan 18 2008

nonn

Square roots of these numbers are quadratic irrationals and corresponding chain fraction representations are periodic: sqrt(10) = [3;{2,3}], sqrt(26) = [5;{2,5}], sqrt(50) = [7;{2,7}], ..., where {} is denoted a period (we write {6} == {2,3}).

			10 is a term because 10 = 3^2 + 1 is composite,
26 is a term because 26 = 5^2 + 1 is composite,
50 is a term because 50 = 7^2 + 1 is composite.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A002496, A005574, A134407.

Supersequence of A144255.

ts_fn1:=proc(n) local i,tren,ans; ans:=[ ]: for i from 1 to n do tren := i^(2)+1: if (isprime(tren) = false) then ans:=[ op(ans), tren ]: fi od: RETURN(ans) end: ts_fn1(200);

Select[Range[70]^2+1,!PrimeQ[#]&] (* Harvey P. Dale, Aug 12 2012 *)

for(n=3,99, if(!isprime(t=n^2+1), print1(t", "))) \\ Charles R Greathouse IV, Aug 29 2016

from sympy import isprime
from itertools import count, takewhile
def aupto(limit):
    form = takewhile(lambda x: x <= limit, (k**2+1 for k in count(1)))
    return [number for number in form if not isprime(number)]
print(aupto(3845)) # Michael S. Branicky, Oct 26 2021

a(n) = 1 + A134407(n)^2. - R. J. Mathar, Oct 13 2019

A054269 Length of period of continued fraction for sqrt(prime(n)).

Original entry on oeis.org

1, 2, 1, 4, 2, 5, 1, 6, 4, 5, 8, 1, 3, 10, 4, 5, 6, 11, 10, 8, 7, 4, 2, 5, 11, 1, 12, 6, 15, 9, 12, 6, 9, 18, 9, 20, 17, 18, 4, 5, 14, 21, 16, 13, 1, 20, 26, 4, 2, 5, 11, 12, 17, 14, 1, 12, 3, 24, 21, 13, 18, 5, 14, 16, 17, 11, 34, 19, 14, 7, 15, 4, 20, 5, 30, 8, 9, 21, 1, 21, 18, 37, 16

Offset: 1

N. J. A. Sloane, May 05 2000

The following sequences (allowing offset of first term) all appear to have the same parity: A034953, triangular numbers with prime indices; A054269, length of period of continued fraction for sqrt(p), p prime; A082749, difference between the sum of next prime(n) natural numbers and the sum of next n primes; A006254, numbers n such that 2n-1 is prime; A067076, 2n+3 is a prime. - Jeremy Gardiner, Sep 10 2004
Note that primes of the form n^2+1 (A002496) have a continued fraction whose period length is 1; odd primes of the form n^2+2 (A056899) have length 2; odd primes of the form n^2-2 (A028871) have length 4. - T. D. Noe, Nov 03 2006
For an odd prime p, the length of the period is odd if p=1 (mod 4) or even if p=3 (mod 4). - T. D. Noe, May 22 2007

T. D. Noe, Table of n, a(n) for n = 1..10000
A. I. Gliga, On continued fractions of the square root of prime numbers

Cf. A003285, A130272 (primes at which the period length sets a new record).

with(numtheory): for i from 1 to 150 do cfr := cfrac(ithprime(i)^(1/2), 'periodic','quotients'); printf(`%d,`, nops(cfr[2])) od:

Table[p=Prime[n]; Length[Last[ContinuedFraction[Sqrt[p]]]],{n,100}] (* T. D. Noe, May 22 2007 *)
Length[ContinuedFraction[Sqrt[#]][[2]]]&/@Prime[Range[100]] (* Harvey P. Dale, Sep 28 2024 *)

More terms from James Sellers, May 05 2000

A083844 Number of primes of the form x^2 + 1 < 10^n.

Original entry on oeis.org

2, 4, 10, 19, 51, 112, 316, 841, 2378, 6656, 18822, 54110, 156081, 456362, 1339875, 3954181, 11726896, 34900213, 104248948, 312357934, 938457801, 2826683630, 8533327397, 25814570672, 78239402726, 237542444180, 722354138859, 2199894223892

Offset: 1

Harry J. Smith, May 05 2003

nonn

It is conjectured that there are infinitely many primes of the form x^2 + 1 (and thus this sequence never becomes constant), but this has not been proved.

These primes can be found quickly using a sieve based on the fact that numbers of this form have at most one primitive prime factor (A005529). The sum of the reciprocals of these primes is 0.81459657... - T. D. Noe, Oct 14 2003

			a(3) = 10 because the only primes or the form x^2 + 1 < 10^3 are the ten primes: 2, 5, 17, 37, 101, 197, 257, 401, 577, 677.

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 A pdf file.
Jon Grantham, Parallel Computation of Primes of the form x^2+1
Jon Grantham and Hester Graves, Primes of the Form m^2+1 and Goldbach's 'Other Other' Conjecture, arXiv:2502.03513 [math.NT], 2025.
Apoloniusz Tyszka, Sławomir Kurpaska, Open problems that concern computable sets X, subset of N, and cannot be formally stated as they refer to current knowledge about X, (2020).
Eric Weisstein's World of Mathematics, Landau's Problems.
Marek Wolf, Search for primes of the form m^2+1, arXiv:0803.1456 [math.NT], 2008-2010.

Cf. A005574, A002496, A083845, A083846, A083847, A083848, A083849, A214452, A214454, A214455.

Cf. A005529 (primitive prime factors of the sequence k^2+1).

c = 1; k = 2; (* except for the initial prime 2, all X's must be odd. *) Do[ While[ k^2 + 1 < 10^n, If[ PrimeQ[k^2 + 1], c++ ]; k += 2]; Print[c], {n, 1, 20}]

Edited by Robert G. Wilson v, May 08 2003
More terms from T. D. Noe, Oct 14 2003
a(17)-a(22) from Robert Gerbicz, Apr 15 2009
a(23)-a(25) from Marek Wolf and Robert Gerbicz (code from Robert, computation done by Marek) Robert Gerbicz, Mar 13 2010
a(26)-a(28) from Jon Grantham, Jan 18 2017
a(28) corrected by Jon Grantham, Jan 30 2018

A243451 Primes of the form n^2 + 16.

Original entry on oeis.org

17, 41, 97, 137, 241, 457, 641, 857, 977, 1697, 2417, 2617, 3041, 4241, 5641, 6257, 6577, 7937, 8297, 9041, 9817, 11897, 13241, 14177, 14657, 15641, 16657, 22817, 27241, 32057, 36497, 44537, 47977, 48857, 52457, 53377, 60041, 62017, 70241, 75641, 78977, 83537

Offset: 1

Vincenzo Librandi, Jun 05 2014

nonn

Intersection of A241751 and A028916; conjecture: sequence is infinite. - Reinhard Zumkeller, Apr 11 2015

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A122062 (associated n).
Cf. similar sequences listed in A243449.
Cf. A010051, A241751; subsequence of A028916.
Primes of form n^2+b^4, b fixed: A002496 (b=1),  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).

a243451 n = a243451_list !! (n-1)
a243451_list = [x | x <- a241751_list, a010051' x == 1]
-- Reinhard Zumkeller, Apr 11 2015

[a: n in [0..1000] | IsPrime(a) where a is n^2+16];

Select[Table[n^2 + 16, {n, 0, 1000}], PrimeQ]
Select[Range[1,301,2]^2+16,PrimeQ] (* Harvey P. Dale, Nov 05 2015 *)

list(lim)=if(lim<17,return([])); my(v=List(),t); forstep(n=1,sqrtint(lim\1-16),2, if(isprime(t=n^2+16), listput(v,t))); Vec(v) \\ Charles R Greathouse IV, Aug 18 2017

A121326 Primes of the form 4*k^2 + 1.

Original entry on oeis.org

5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 1601, 2917, 3137, 4357, 5477, 7057, 8101, 8837, 12101, 13457, 14401, 15377, 15877, 16901, 17957, 21317, 22501, 24337, 25601, 28901, 30977, 32401, 33857, 41617, 42437, 44101, 50177, 52901, 55697

Offset: 1

Cino Hilliard, Aug 26 2006

Except for the initial 2 in A002496 this sequence is the same as A002496.

The prime factors of numbers of the form 4k^2 + 1 (a sum of two squares) are of the form 4m + 1.

			For k=4, 4k^2 + 1 = 17, a prime.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000

Cf. A002496.

[a: n in [0..400] | IsPrime(a) where a is 4*n^2+1]; // Vincenzo Librandi, Dec 02 2011

Select[Table[4n^2+1,{n,0,800}],PrimeQ] (* Vincenzo Librandi, Dec 02 2011 *)

for(x=1,200,y=4*x^2+1;if(isprime(y),print1(y",")))

A049423 Primes of the form k^2 + 3.

Original entry on oeis.org

3, 7, 19, 67, 103, 199, 487, 787, 1447, 2503, 2707, 3847, 4099, 4903, 5479, 5779, 8467, 8839, 11239, 12547, 14887, 16903, 17959, 19603, 21319, 23719, 24967, 25603, 29587, 31687, 47527, 52903, 58567, 59539, 61507, 65539, 75079, 81799, 88807

Offset: 1

Paul Jobling (paul.jobling(AT)whitecross.com)

Note that all terms after the first are congruent to 7 modulo 12.

			19 is prime and is equal to 4^2 + 3, so 19 is a term.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Near-Square Prime

Cf. A002496, A056899. Note that apart from first term, all of (a(n)-7)/12 have to be terms of A001082 for a(n) to be prime.

[n: n in PrimesUpTo(175000) | IsSquare(n-3)];  // Bruno Berselli, Apr 05 2011

[a: n in [0..300] | IsPrime(a) where a is n^2+3]; // Vincenzo Librandi, Dec 08 2011

Intersection[Table[n^2+3,{n,0,10^2}],Prime[Range[9*10^3]]] ...or... For[i=3,i<=3,a={};Do[If[PrimeQ[n^2+i],AppendTo[a,n^2+i]],{n,0,100}];Print["n^2+",i,",",a];i++ ] (* Vladimir Joseph Stephan Orlovsky, Apr 29 2008 *)
Select[Table[n^2+3,{n,0,198000}],PrimeQ] (* Vincenzo Librandi, Dec 08 2011 *)

list(lim)=my(v=List(),t); forstep(k=0,sqrtint(lim\1-3),2, if(isprime(t=k^2+3), listput(v,t))); Vec(v) \\ Charles R Greathouse IV, Nov 06 2024

Primes m such that m-3 is a square.
For n>0, a(n) = 36*A056902(n-1)^2 + 24*A056902(n-1) + 7. - Henry Bottomley, Jul 06 2000
a(n) = 3 + (2*A097697(n-1))^2. - R. J. Mathar, Aug 07 2008
a(n) >> n^2 log n. - Charles R Greathouse IV, Nov 06 2024

cp's OEIS Frontend

A056993 a(n) is the smallest k >= 2 such that k^(2^n)+1 is prime, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A037896 Primes of the form k^4 + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Sage

Formula

Extensions

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A056892 a(n) = square excess of the n-th prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A134406 Composite numbers of the form k^2 + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A054269 Length of period of continued fraction for sqrt(prime(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions