OFFSET
1,1
COMMENTS
Is it true that this sequence consists of the odd primes p with 2^(2^p) == 1 (mod p)? (David Wilson, Jul 31 2008). Answer from Max Alekseyev: Yes! If prime p divides Fm = 2^(2^m)+1, then 2^(2^(m+1)) == 1 (mod p) and p is of the form p = k*2^(m+2)+1 > m+1. Squaring the last congruence p-(m+1) times, we get 2^(2^p) == 1 (mod p). On the other hand, if 2^(2^p) == 1 (mod p) for prime p, consider a sequence 2^(2^0), 2^(2^1), 2^(2^2), ..., 2^(2^p). Modulo p this sequence ends with a bunch of 1's but just before the first 1 we must see -1 (as the only other square root of 1 modulo prime p), i.e. for some m, 2^(2^m) == -1 (mod p), implying that p divides Fermat number 2^(2^m) + 1.
Also primes p such that the multiplicative order of 2 (mod p) is a power of 2. A theorem of Lucas states that if m>1 and prime p divides 1+2^2^m (the m-th Fermat number), then p = 1+k*2^(m+2) for some integer k. - T. D. Noe, Jan 29 2009
Wilfrid Keller analyzed the current status of the search for prime factors of Fermat number and stated that all prime factors less than 10^19 are now known. He sent me terms a(25) to a(50). - T. D. Noe, Feb 01 2009, Feb 03 2009, Jan 14 2013
Křížek, Luca, & Somer (2002) show that the sum of the reciprocals of this sequence converge, answering a question of Golomb (1955). - Charles R Greathouse IV, Jul 15 2013
To test if a prime p is a member, it suffices to check if the multiplicative order of 2 modulo p is a power of two. But it obvious that the order is a divisor of p-1. Therefore it is enough to test if 2^(2^j) == 1 (mod p) where 2^j is the largest power of two that divides p-1. Jeppe Stig Nielsen, Mar 13 2022
Primes p such that 2^(2^p) == 2^p - 1 (mod p); i.e., prime numbers in A373580. - Thomas Ordowski, Jun 11 2024
REFERENCES
Michal Krížek, Florian Luca and Lawrence Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..50 (from Wilfrid Keller)
Wilfrid Keller, Prime factors k.2^n + 1 of Fermat numbers F_m.
Michal Krížek, Florian Luca and Lawrence Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory, Vol. 97 (2002), pp. 95-112.
Sourangshu Ghosh and Pranjal Jain, On Fermat Numbers and Munafo's Conjecture, ResearchGate (2021).
A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp., Vol. 64. No. 203 (1995), 1357.
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof (2012), arXiv preprint arXiv:1202.3670 [math.HO], 2012-2018.
Robert Munafo, Prime Factors of Fermat Numbers.
Mercedes Orús-Lacort, Fermat numbers are not prime numbers for n >= 5, ResearchGate (2020).
Lorenzo Sauras-Altuzarra, Some properties of the factors of Fermat numbers, Art Discrete Appl. Math. (2022).
FORMULA
a(n) >> n^2 log^2 n, see Křížek, Luca, & Somer. - Charles R Greathouse IV, Jul 16 2013
Sum_{n>=1} 1/a(n) = A344784. - Amiram Eldar, May 30 2021
MAPLE
q:=p->(isprime(p) and irem(2^(2^padic:-ordp(p-1, 2))-1, p) = 0):
select(q, [$1..10^5])[]; # Lorenzo Sauras Altuzarra, Feb 20 2023
MATHEMATICA
Select[Prime[Range[100000]], IntegerQ[Log[2, MultiplicativeOrder[2, # ]]]&] (* T. D. Noe, Jan 29 2009 *)
PROG
(PARI) is(p)=p>2 && Mod(2, p)^lift(Mod(2, znorder(Mod(2, p)))^p)==1 && isprime(p) \\ Charles R Greathouse IV, Feb 04 2013
(PARI) my(isfermatdivisor(m)=if(m>0, if(m==1, return(1), v=valuation(m-1, 2); c=0; if(m>2, e=logint(m-1, 2); if(e==v&&Mod(m-1, e)==0, t=logint(v, 2); c=1)); if(v>6&&c==0, x=2; t=0; for(i=0, v-2, if(x+1==m, c=1; break); s=x*x; x=s-s\m*m; t++)); if(c==1, print((m-1)/2^v"*2^"v" + 1 divides 2^(2^"t") + 1")); return(c)))); L=List([]); forstep(m=3, 63766529, 2, if(isprime(m)&&isfermatdivisor(m), listput(L, m))); print(); print(Vec(L)); \\ Arkadiusz Wesolowski, Jan 16 2018
(PARI) forprime(p=2, , Mod(2, p)^(2^valuation(p-1, 2))==1&&print1(p, ", ")) \\ Jeppe Stig Nielsen, Mar 13 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved