Are there primes $p=47\cdot 2^n+1$?

Question

Are there primes $p=47\cdot 2^n+1$, where $n\in\mathbb Z_+$? Tested for all primes $p<100,000,000$ without equality.

Answer 1

Yes. We can start by quick Maple search, yielding for example $n=583$ (isprime(47*2^583+1)). Next ones are $n=1483$ and $n=6115$, I haven't found any others yet. We can speed up this search by noting that for certain $n$ it is clear that it cannot be prime. For example if $n$ is even, then we have $47\cdot 2^n+1 \equiv 2\cdot 2^0+1=0 \pmod 3$. Similarly, if $n$ is odd and $n \equiv 1 \bmod 4$, then $47\cdot 2^n+1 \equiv 2\cdot 2^{1}+1=0 \pmod 5$. This reduces search to $n \equiv 3 \pmod 4$ .

However as pointed out in comments, Maple performs probabilistic primality tests for such large numbers (one strong pseudo-primality test and one Lucas test per documentation https://www.maplesoft.com/support/help/maple/view.aspx?path=isprime), so there is a chance these could be false positives (although no such counter example has been yet found). Anyway further testing with some deterministic approach would be nice, and fortunately there is one very specific to these numbers! (see below)

It turns out these numbers are special case of what is called Proth numbers, and you are especially interested in Proth primes. In fact these numbers are popular in large prime search, largest currently known non Mersenne prime (as of 2018) is $10223\cdot 2^{31172165}+1$ (https://primes.utm.edu/top20/page.php?id=3). The reason is there is very effective way to check their primality, using something called Proth's theorem. Roughly it states:

If $p=k\cdot 2^n+1$ with $k$ odd and $k<2^n$, and if there exists an integer $a$ for which $a^{(p-1)/2}\equiv -1 \bmod p$, then $p$ is a prime.

So this can be turned into an effective algorithm to verify primality of the cases found above by probabilistic test. And indeed, for $a=3$ and $p=47\cdot 2^{583}+1$ we already have a match, e.g.:

a := 3: 
p := 47*2^583+1: 
is((Power(a, (p-1)/2) mod p) = p-1);

So putting together, we can run something like (which I am sure could be optimized)

m:=1:
do: 
  n := 4*m+3:
  p := 47*2^n+1:
  if isprime(p) then 
    for a from 1 to 10 do 
      if is((Power(a, (p-1)/2) mod p) = p-1) then 
        print('n' = n, 'a' = a): 
      break: 
      end if: 
    end do: 
  end if: 
  m := m+1 
end do:

Answer 2

Smallest $m\ge0$ such that $2^mn+1$ is prime is tabulated at OEIS. The first "interesting" case is the one under discussion here, $n=47$; it's at most 8 for $n<47$, then $583$ for $n=47$. For $n=383$ it's $6393$, for $n=2897$ it's $9715$, and it's known that for infinitely many $n$ there is no such $m$. See the links at OEIS.