# Positive integers satisfying: for all odd prime powers $p^k < n$, $n - p^k$ is prime

Given positive integer $k$, define the subset $S(k)$ of positive integers $n$ where for every odd prime power $p^k < n$, $n - p^k$ is prime. In other words, $$S(k) = \{n \in \mathbb{N} \mid \forall p \in \mathbb{P} : (p > 2 \wedge p^k < n) \Rightarrow n - p^k \in \mathbb{P}\}.$$

Question: Is $S(k)$ is finite for every $k > 0$?

I suspect this is the case from initial computer searches. I am hoping there is an elementary proof of this (if it's true), but I have had little success.

Some observations: any $n < 3^k$ will be in $S(k)$ since the condition holds vacuously true on $n$. Furthermore, the largest odd element of $S(k)$ must be $\leq 3^k + 2$ as otherwise it could be written as $3^k + \text{composite even number}$ and thus not be in $S(k)$. So, it suffices to focus attention on the even elements of $S(k)$.

Intuitively, it makes sense that the larger you go, the less likely a number belongs to $S(k)$ since there are more "chances" for at least one $n - p^k$ to be composite. But it is not at all obvious that this is actually "impossible to belong to $S(k)$ once we exceed a certain number".

• @rtybase But $n-(p')^k$ may be composite for some odd prime $p'<p$. – Batominovski Sep 8 '18 at 14:43
• @rtybase I don't understand your reasoning. Say, $k=2$. Then, you claim that $n=5^2+11=36$ is in $S(2)$, right? But this can't be because $n-3^2=27$ is not prime. – Batominovski Sep 8 '18 at 14:54
• @rtybase It surely does look like you were asserting that $p^k+q\in S(k)$ for all odd primes $p$ and $q$. The last two sentences of your first comment make it look like that. – Batominovski Sep 8 '18 at 15:01
• @rtybase 1. No, you are missing a $\forall$ somewhere. 2. Your definition allows $p = 2$. One way to write it out is $$S(k) = \{n \in \mathbb{N} \mid \forall p \in \mathbb{P} : (p > 2 \wedge p^k < n) \Rightarrow n - p^k \in \mathbb{P}\}.$$ – theyaoster Sep 8 '18 at 16:16
• If $k$ is an odd positive integer, then $S(k)$ is finite. It can be easily seen that $\max S(k)\leq 7^k+3$. Indeed, if an integer $n$ satisfies $n>7^k+3$, then $n-7^k>3$, $n-5^k>3$, or $n-3^k>3$ is divisible by $3$ – Batominovski Sep 10 '18 at 15:27