Does there exist such a positive integer? 
Does there exist such a positive integer $M$ such that, $2\left(M^{2^k}\right)-1$ is prime for all $k= 0, 1, 2, \dotsc$?

I was trying to solve the problem: 

Show that there are infinitely many integers which are not sum of a prime and a square.

I ended up showing that there are infinitely many numbers of the form $3k + 1$ which are not sum of a square and a prime. But then I was trying to find a different solution. I assumed that there are finitely many such numbers, and that $M$ is the biggest number which can't be written as a sum of a prime and a square. Then I tried to derive a contradiction by showing that there exists and integer $N$ greater than $M$ such that $N$ is a sum of a square and a prime.
 A: Evidently this is part of a contest problem. The question was to show that there are infinitely many natural numbers that cannot be written as a square plus a prime. If you do a simple computer run, you find that such numbers are usually squares themselves. Furthermore, the set of such numbers that are not squares seems to be finite. This is, indeed Hardy and Littlewood's Conjecture H. 
https://oeis.org/A020495
https://oeis.org/A020495/b020495.txt 
On page 36, problem 3.3.1 in The Hardy-Littlewood Method, by R. C. Vaughan, one is asked to prove that all sufficiently large natural numbers can be written as $p_1+p_2+x^k,$ for fixed exponent $k \geq 2.$ 
On the other hand, the set of squares that cannot be written as a smaller square plus a prime is, evidently, infinite. 
Take any natural number $$ n \equiv 2 \pmod 3  $$. Take any smaller number
$$ 1 \leq m < n  $$
If
$$ n^2 - m^2 = (n + m)(n-m)  $$
is prime, the only possibility is $n-m=1$ or $m = n-1.$ Alright, assume
$$ n^2 - (n-1)^2  $$
is prime. Well
$$ n^2 - (n-1)^2 = 2n - 1.  $$
However,
$$ 2n-1 \equiv 2 \cdot 2 -1 \equiv 0 \pmod 3  $$
is divisible by $3$ and not prime. 
So, $n^2$ is not the sum of a prime and a smaller square.
