# Tag Info

This problem has been studied already; see this Wikipedia article. Does there a exist a prime $q$ such that $p = 2^kq + 1$ is also prime? A number $q$ such that $p$ is never prime is called a Sierpiński number; such numbers do exist, and some of them are prime. The smallest known such prime is $q = 271129$; the next known ones are $322523, 327739, ... 5 There is numerical evidence that for the vast majority of primes$p$, there exists$k$making$q=2^k\,p+1$prime. See first exceptions in A137715. The only practical way I see to find which$(p,k)$make$q=2^k\,p+1$prime in the question's context is testing$q\$ for primality using a fast test. As noted in the other answer, sieving for small primes can be ...