login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Fermat numbers: a(n) = 2^(2^n) + 1.
(Formerly M2503 N0990)
242

%I M2503 N0990 #292 Jan 11 2025 18:48:21

%S 3,5,17,257,65537,4294967297,18446744073709551617,

%T 340282366920938463463374607431768211457,

%U 115792089237316195423570985008687907853269984665640564039457584007913129639937

%N Fermat numbers: a(n) = 2^(2^n) + 1.

%C It is conjectured that just the first 5 numbers in this sequence are primes.

%C An infinite coprime sequence defined by recursion. - _Michael Somos_, Mar 14 2004

%C For n>0, Fermat numbers F(n) have digital roots 5 or 8 depending on whether n is even or odd (Koshy). - _Lekraj Beedassy_, Mar 17 2005

%C This is the special case k=2 of sequences with exact mutual k-residues. In general, a(1)=k+1 and a(n)=min{m | m>a(n-1), mod(m,a(i))=k, i=1,...,n-1}. k=1 gives Sylvester's sequence A000058. - _Seppo Mustonen_, Sep 04 2005

%C For n>1 final two digits of a(n) are periodically repeated with period 4: {17, 57, 37, 97}. - _Alexander Adamchuk_, Apr 07 2007

%C For 1 < k <= 2^n, a(A007814(k-1)) divides a(n) + 2^k. More generally, for any number k, let r = k mod 2^n and suppose r != 1, then a(A007814(r-1)) divides a(n) + 2^k. - _T. D. Noe_, Jul 12 2007

%C From _Daniel Forgues_, Jun 20 2011: (Start)

%C The Fermat numbers F_n are F_n(a,b) = a^(2^n) + b^(2^n) with a = 2 and b = 1.

%C For n >= 2, all factors of F_n = 2^(2^n) + 1 are of the form k*(2^(n+2)) + 1 (k >= 1).

%C The products of distinct Fermat numbers (in their binary representation, see A080176) give rows of Sierpiński's triangle (A006943). (End)

%C Let F(n) be a Fermat number. For n > 2, F(n) is prime if and only if 5^((F(n)-1)/4) == sqrt(F(n)-1) (mod F(n)). - _Arkadiusz Wesolowski_, Jul 16 2011

%C Conjecture: let the smallest prime factor of Fermat number F(n) be P(F(n)). If F(n) is composite, then P(F(n)) < 3*2^(2^n/2 - n - 2). - _Arkadiusz Wesolowski_, Aug 10 2012

%C The Fermat primes are not Brazilian numbers, so they belong to A220627, but the Fermat composites are Brazilian numbers so they belong to A220571. For a proof, see Proposition 3 page 36 on "Les nombres brésiliens" in Links. - _Bernard Schott_, Dec 29 2012

%C It appears that this sequence is generated by starting with a(0)=3 and following the rule "Write in binary and read in base 4". For an example of "Write in binary and read in ternary", see A014118. - _John W. Layman_, Jul 30 2013

%C Conjecture: the numbers > 5 in this sequence, i.e., 2^2^k + 1 for k>1, are exactly the numbers n such that (n-1)^4-1 divides 2^(n-1)-1. - _M. F. Hasler_, Jul 24 2015

%D M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.

%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 7.

%D P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 87.

%D James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).

%D Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, pp. 78-79.

%D R. K. Guy, Unsolved Problems in Number Theory, A3.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 14.

%D E. Hille, Analytic Function Theory, Vol. I, Chelsea, N.Y., see p. 64.

%D T. Koshy, "The Digital Root Of A Fermat Number", Journal of Recreational Mathematics Vol. 32 No. 2 2002-3 Baywood NY.

%D M. Krizek, F. Luca & L. Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.

%D C. S. Ogilvy and J. T. Anderson, Excursions in Number Theory, Oxford University Press, NY, 1966, p. 36.

%D Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see pp. 18, 59.

%D C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 202.

%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, Penguin Books, 1987, pp. 148-149.

%H N. J. A. Sloane, <a href="/A000215/b000215.txt">Table of n, a(n) for n = 0..11</a>

%H Richard Bellman, <a href="http://dx.doi.org/10.1090/S0002-9904-1947-08879-0">A note on relatively prime sequences</a>, Bull. Amer. Math. Soc. 53 (1947), 778-779.

%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php/FermatNumber.html">Fermat number</a>.

%H C. K. Caldwell, The prime pages <a href="https://primes.utm.edu/notes/proofs/SquareMerDiv.html">All prime-square Mersenne divisors are Wieferich</a> (2021).

%H Shane Chern, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Chern/chern2.html">Fermat Numbers in Multinomial Coefficients</a>, J. Int. Seq. 17 (2014) # 14.3.2.

%H Leonhard Euler, <a href="https://arxiv.org/abs/math/0501118">Observations on a theorem of Fermat and others on looking at prime numbers</a>, arXiv:math/0501118 [math.HO], 2005-2008.

%H Leonhard Euler, <a href="http://math.dartmouth.edu/~euler/pages/E026.html">Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus</a>.

%H Emmanuel Ferrand, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Ferrand/ferrand8.html">Deformations of the Taylor Formula</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

%H Richard K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

%H Wilfrid Keller, <a href="http://www.prothsearch.com/fermat.html">Prime factors k.2^n + 1 of Fermat numbers F_m</a>

%H Jiří Klaška, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Klaska/klaska6.html">Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem</a>, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.

%H T.-W. Leung, <a href="http://mathdb.org/resource_sharing/excalibur/Eng_v7_n4.pdf">A Brief Introduction to Fermat Numbers</a>

%H Romeo Meštrović, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012

%H Romeo Meštrović, <a href="https://www.researchgate.net/publication/329844912_GOLDBACH-TYPE_CONJECTURES_ARISING_FROM_SOME_ARITHMETIC_PROGRESSIONS">Goldbach-type conjectures arising from some arithmetic progressions</a>, University of Montenegro, 2018.

%H Romeo Meštrović, <a href="https://arxiv.org/abs/1901.07882">Goldbach's like conjectures arising from arithmetic progressions whose first two terms are primes</a>, arXiv:1901.07882 [math.NT], 2019.

%H Michael A. Morrison and John Brillhart, <a href="http://dx.doi.org/10.1090/S0002-9904-1971-12711-8">The factorization of F_7</a>, Bull. Amer. Math. Soc. 77 (1971), 264.

%H Robert Munafo, <a href="http://www.mrob.com/pub/seq/a000215.html">Fermat Numbers</a>

%H Robert Munafo, <a href="http://www.mrob.com/pub/math/ln-notes1.html#fermat">Notes on Fermat numbers</a>

%H Seppo Mustonen, <a href="http://www.survo.fi/papers/resseq.pdf">On integer sequences with mutual k-residues</a>.

%H Seppo Mustonen, <a href="/A000215/a000215.pdf">On integer sequences with mutual k-residues</a>. [Local copy]

%H OEIS Wiki, <a href="/wiki/Fermat_numbers">Fermat numbers</a>.

%H OEIS Wiki, <a href="/wiki/Sierpinski&#39;s_triangle">Sierpinski's triangle</a>.

%H G. A. Paxson, <a href="http://dx.doi.org/10.1090/S0025-5718-1961-0124264-0">The compositeness of the thirteenth Fermat number</a>, Math. Comp. 15 (76) (1961) 420-420.

%H Carl Pomerance, <a href="http://www.ams.org/notices/199612/pomerance.pdf">A tale of two sieves</a>, Notices Amer. Math. Soc., 43 (1996), 1473-1485.

%H P. Sanchez, PlanetMath.org, <a href="https://planetmath.org/fermatnumbers">Fermat Numbers</a>

%H Bernard Schott, <a href="http://quadrature.info/">Les nombres brésiliens</a>, Quadrature, no. 76, avril-juin 2010, pages 30-38. <a href="/A125134/a125134.pdf">Local copy</a>, included here with permission from the editors of Quadrature.

%H G. Villemin's Almanach of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Decompos/Fermat.htm">Nombres de Fermat</a>.

%H Le Roy J. Warren, Henry G. Bray, <a href="https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-22/issue-3/On-the-square-freeness-of-Fermat-and-Mersenne-numbers/pjm/1102992105.pdf"> On the square-freeness of Fermat and Mersenne Numbers</a>, Pac. J. Math. 22 (3) (1967) 563.

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GeneralizedFermatNumber.html">Generalized Fermat Number</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fermat_number">Fermat number</a>.

%H Wolfram Research, <a href="http://functions.wolfram.com/04.08.03.0008.01">Fermat numbers are pairwise coprime</a>.

%F a(0) = 3; a(n) = (a(n-1)-1)^2 + 1, n >= 1.

%F a(n) = a(n-1)*a(n-2)*...*a(1)*a(0) + 2, n >= 0, where for n = 0, we get the empty product, i.e., 1, plus 2, giving 3 = a(0). - _Benoit Cloitre_, Sep 15 2002 [edited by _Daniel Forgues_, Jun 20 2011]

%F The above formula implies that the Fermat numbers (being all odd) are coprime.

%F Conjecture: F is a Fermat prime if and only if phi(F-2) = (F-1)/2. - _Benoit Cloitre_, Sep 15 2002

%F A000120(a(n)) = 2. - _Reinhard Zumkeller_, Aug 07 2010

%F If a(n) is composite, then a(n) = A242619(n)^2 + A242620(n)^2 = A257916(n)^2 - A257917(n)^2. - _Arkadiusz Wesolowski_, May 13 2015

%F Sum_{n>=0} 1/a(n) = A051158. - _Amiram Eldar_, Oct 27 2020

%F From _Amiram Eldar_, Jan 28 2021: (Start)

%F Product_{n>=0} (1 + 1/a(n)) = A249119.

%F Product_{n>=0} (1 - 1/a(n)) = 1/2. (End)

%F a(n) = 2*A077585(n) + 3. - _César Aguilera_, Jul 26 2023

%F a(n) = 2*2^A000225(n) + 1. - _César Aguilera_, Jul 11 2024

%e a(0) = 1*2^1 + 1 = 3 = 1*(2*1) + 1.

%e a(1) = 1*2^2 + 1 = 5 = 1*(2*2) + 1.

%e a(2) = 1*2^4 + 1 = 17 = 2*(2*4) + 1.

%e a(3) = 1*2^8 + 1 = 257 = 16*(2*8) + 1.

%e a(4) = 1*2^16 + 1 = 65537 = 2048*(2*16) + 1.

%e a(5) = 1*2^32 + 1 = 4294967297 = 641*6700417 = (10*(2*32) + 1)*(104694*(2*32) + 1).

%e a(6) = 1*2^64 + 1 = 18446744073709551617 = 274177*67280421310721 = (2142*(2*64) + 1)*(525628291490*(2*64) + 1).

%p A000215 := n->2^(2^n)+1;

%t Table[2^(2^n) + 1, {n, 0, 8}] (* _Alonso del Arte_, Jun 07 2011 *)

%o (PARI) a(n)=if(n<1,3*(n==0),(a(n-1)-1)^2+1)

%o (Maxima) A000215(n):=2^(2^n)+1$ makelist(A000215(n),n,0,10); /* _Martin Ettl_, Dec 10 2012 */

%o (Haskell)

%o a000215 = (+ 1) . (2 ^) . (2 ^) -- _Reinhard Zumkeller_, Feb 13 2015

%o (Python)

%o def a(n): return 2**(2**n) + 1

%o print([a(n) for n in range(9)]) # _Michael S. Branicky_, Apr 19 2021

%Y a(n) = A001146(n) + 1 = A051179(n) + 2.

%Y Cf. A019434, A050922, A051158, A051179, A063486, A073617, A085866.

%Y See A004249 for a similar sequence.

%Y Cf. A080176 for binary representation of Fermat numbers.

%Y Cf. A220627, A220570, A220571, A125134, A249119.

%Y Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.

%Y Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.

%K nonn,easy,nice,changed

%O 0,1

%A _N. J. A. Sloane_