Can we find $n$ such that $3061\cdot2^n +1$ is prime?

Not a complete solution but some observations. Let $a_n=2^np+1$.

I. If $n$ is odd then $3\,|\,a_n$.

Pf: Indeed $3061\equiv 1 \pmod 3$ so $a_n\equiv 2^n+1\pmod 3$ and the claim follows.

II. If $n\equiv 2 \pmod 4$ then $5\,|\,a_n$

Pf: Indeed, $3061\equiv 1 \pmod 5$ so $a_n\equiv 2^n+1\pmod 5$ and the claim follows.

So you only need to worry about $n\equiv 0 \pmod 4$. For those there does not appear to be a simple congruence. Indeed, for $n\in \{1,\cdots 10\}$ the least prime which divides $a_{4n}$ is, respectively, $$\{17,19,17,797, 17,821,17,31,17,59\cdots\}$$

From which we are led to conjecture that $n\equiv 4 \mod 8\implies 17\,|\,a_n$, which is easily proven (since $3061\equiv 1\pmod {17}$ and $2^4\equiv -1 \pmod {17}$).

That just leaves $n\equiv 0\pmod 8$ to study.


These are Proth numbers so you can apply Proth's theorem for efficient primality testing (see also Are there primes $p=47\cdot 2^n+1$?.). This way, we can verify that the pseudoprime posted by @DmitryEzhov in comments is indeed a prime by choosing $a=3$, $N=3061\cdot 2^{33288}+1$, because $$ a^{\frac{N-1}{2}} \equiv -1 \pmod{N}. $$ (e.g. a := 3: p := 3061*2^33288+1: is((Power(a, (p-1)/2) mod p) = p-1) in Maple).

Also Effective Primality Test for $p2^n+1$, $p$ prime, $n>1$ could be of interest. It especially mentions:

Sierpinski numbers of the second kind are integers $k$ such that $k2^n + 1$ is not prime for all positive integers $n$.

So in your case, if the Sierpinski number $k=p$ happens to be a prime, you will not find $n$ such that $p2^n+1$ is a prime. There are infinitely many such numbers, the $k=271129$ is conjectured to be the smallest (see Prime Sierpinski problem). See Alex's answer for more examples.

Even more reading The Sierpiński Problem: Definition and Status.