Well, first of all, happy new year to everyone.
I am trying to solve the following problem: "Let $k$ be a fixed natural number. Find the least prime $p$ such that there exists a natural number $n$ such that $p^n + k$ is the product of $n$ distinct primes." As a related problem, suppose that $k,n$ are both fixed and find the least prime $p$ for which $p^k+n$ is the product of $n$ distinct primes.
Now, let's say I have found the least prime $p$ for a specific value of $n$ and $k$. Can we find a lower and/or upper bound for the problem when we want to look for the $n+1$ case or in general for the $n+a$ case?
I've no idea how to proceed or start in this problem.
As an example, when $k=2$ we have the following solutions:
$$(p,n)\in{(3,1),(2,2),(7,3),(71,4),(241,5),(83,6),(157,7),\dots}\tag1$$
And when $k=4$ we have the following solutions:
$$(p,n)\in{(3,1),(19,2),(11,3),(29,4),(131,5),(983,6),(353,7),\dots}\tag2$$