How can we turn any number into a prime number by simply adding more digits?

How can we turn any number (where the number is > 2) into a prime number by simply appending more digits? I'm referring to the right side of the number.

So

4 is not a prime number

But If I append 1 or 3 or 7 it can become a prime number

41, 43, 47 are all in fact prime numbers

I "know" this is possible (however I don't have a proof for that) simply because of "density" of prime numbers, so given any number I can simply add many "5" digits and then starting searching prime numbers by adding "1" to the resulting number and test it for primality.

However is there any smarter way to do that without using "bruteforce" (i.e. testing for primality a range of values )

Out of the box solutions are preferred, in example.

if the number is in the form XYZ then XYZ(ZYX+1) is prime.

• as usual downvoters are incouraged for feedback, and should realize how an answer (if ever exist) to this question would be usefull ;) – CoffeDeveloper May 6 '16 at 9:15
• There's a problem I found in *Problem Solving Strategies by Arthur Engel that may be relevant- I start with a multidigit number $a_1$ and generate a sequence $a_1,a_2,a_3,...$ Here $a_{n+1}$ comes from $a_n$ by attaching a digit $\ne 9$.Then I cannot avoid the fact that $a_n$ is infinitely often a composite number. Then he says, *If I could use 9, then I could not tell if I could get only primes from some $n$ upwards for ex. with $a_1=1$ I get the following primes of length 9- $1979339333,1979339339$ – Aniket Bhattacharyea May 6 '16 at 9:16
• I'm interested in that, please make an answer so I can at least upvote (and maybe later accept it). Thanks @AniketBhattacharyea – CoffeDeveloper May 6 '16 at 9:18
• Just be sure you don't add a 2 at the end – moonshine May 11 '16 at 17:21

It is known that there is a positive number $\delta$ strictly less than 1 such that, if $n$ is large enough, then there's a prime between $n$ and $n+n^{\delta}$. [I think the state of the art has $\delta=.535$] If $n$ is large enough, then $n$ and $n+n^{\delta}$ start with the same however-many-digits-you-like. So that proves it's always possible, although it doesn't give you a good way to do it.
It is conjectured that there's always a prime between $n$ and $n+C(\log n)^2$ for some positive constant $C$ [$C=2$ may even do, at least for large $n$], but this is way beyong what anyone currently knows how to prove.
• conjecture = so there is no (known) smart way to find that number if it is between n + C(logn)^2 and n range. What about prime numbers out of that range that still have same X digits? – CoffeDeveloper May 6 '16 at 9:29
• In fact, Baker, Harman and Pintz lowered $\delta$ to $0.525$ in 2001. – Vincenzo Oliva May 7 '16 at 7:12