3
$\begingroup$

It is clear to see that 11 and 101 are primes which sum of digit is 2. I wonder are there more or infinte many of such prime.

At first, I was think of the number $10^n+1$. Soon, I knew that $n\neq km$ for odd $k>1$, otherwise $10^m+1$ is a factor.

So, here is my question:

Are there infinite many integer $n\ge 0$ such that $10^{2^n}+1$ prime numbers?

After a few minutes: I found that if $n=2$, $10^{2^n}+1=10001=73\times137$, not a prime; if $n=3$, $10^{2^n}+1=17\times5882353$, not a prime; $n=4$, $10^{2^n}+1=353\times449\times641\times1409\times69857$, not a prime.

Now I wonder if 11 and 101 are the only two primes with this property.

  • 0
    @ThomasAndrews Thanks for pointing out this. I have edited it.2012-11-23

3 Answers 3

4

Many people wonder the same thing you do. Wilfrid Keller keeps track of what they find out. So far: prime for $n=0$ and $n=1$ only; known to be composite for all other $n$, $2\le n\le23$, and many other values of $n$. The first value for which primality status is unknown is $n=24$.

  • 0
    Opps... I am so sorry.2012-11-23
3

Since no one else has mentioned it:

Standard heuristics in number theory suggest that there are only finitely many primes of the form $(2k)^{2^n}+1$ for any integer $k>0.$ The probability that a random number around $(2k)^{2^n}+1$ is prime is roughly $1/(2^n\log(2k))$; if you take into account the congruence conditions for such numbers and treat the chance that such a number is prime as a random variable, then the expectation is $C_k/2^n$ and the sum over these values converges.

If you sum this 'probability' over $n\ge24$ the expected number of primes of this form is less than 0.000001.

1

If you're interested in quickly determining whether or not $10^{2^n}+1$ is prime (or positive integers in general), I suggest using OpenPFGW. It has (among other things) an efficient implementation of a PRP test.

Using the ABC2 input format, we input this:      ABC2 10^(2^$a)+1     a: from 1 to 1000 

and it outputs:

PFGW Version 3.6.6.64BIT.20120917.x86_Dev [GWNUM 27.8]   CPU Information (From Woltman v26 library code) Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz CPU speed: 2195.32 MHz, 4 hyperthreaded cores CPU features: RDTSC, CMOV, Prefetch, MMX, SSE, SSE2, SSE4.1, SSE4.2 L1 cache size: 32 KB L2 cache size: 256 KB, L3 cache size: 6 MB L1 cache line size: 64 bytes L2 cache line size: 64 bytes TLBS: 64  Recognized ABC Sieve file:                                      ABC2 File 10^(2^0)+1 is trivially prime!: 11                                     10^(2^1)+1 is trivially prime!: 101                                     Switching to Exponentiating using GMP                                     Switching to Exponentiating using Woltman FFT's                                     10^(2^13)+1 is composite: RES64: [64182BF8406B65C3] (2.4100s+0.0002s) 10^(2^14)+1 is composite: RES64: [C5FF6A4A68324D5A] (12.6942s+0.0003s) 10^(2^15)+1 is composite: RES64: [A874DC2BD3F1B9C8] (58.8378s+0.0003s)