31
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ as usual downvoters are incouraged for feedback, and should realize how an answer (if ever exist) to this question would be usefull ;) $\endgroup$
    – CoffeDeveloper
    May 6, 2016 at 9:15
  • 3
    $\begingroup$ 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$ $\endgroup$
    – Aniket Bhattacharyea
    May 6, 2016 at 9:16
  • $\begingroup$ I'm interested in that, please make an answer so I can at least upvote (and maybe later accept it). Thanks @AniketBhattacharyea $\endgroup$
    – CoffeDeveloper
    May 6, 2016 at 9:18
  • 2
    $\begingroup$ Just be sure you don't add a 2 at the end $\endgroup$
    – moonshine
    May 11, 2016 at 17:21

1 Answer 1

Reset to default
37
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – CoffeDeveloper
    May 6, 2016 at 9:29
  • $\begingroup$ just realized that do not preclude that a way exists even in that range, for some ranges at least. $\endgroup$
    – CoffeDeveloper
    May 6, 2016 at 9:53
  • 1
    $\begingroup$ And to amplify in the intersection of this answer and the original question: The current state of the art technique for finding primes in an interval is a slightly smarter version of "bruteforce": keep track of residues modulo small primes (so you just know which numbers are divisible by 2, 3, 5, 7, and so on up to some limit on how many small primes you want to not have to worry about) then use a general prime proving technique on the ones that don't have small prime divisors. $\endgroup$
    – Eric Towers
    May 6, 2016 at 17:22
  • 2
    $\begingroup$ Similarly, one can append a 1 to the end if necessary, and then the existence of many primes ending in those digits is Dirichlet's theorem for primes in arithmetic progressions. $\endgroup$
    – Greg Martin
    May 6, 2016 at 20:09
  • 2
    $\begingroup$ In fact, Baker, Harman and Pintz lowered $\delta$ to $0.525$ in 2001. $\endgroup$
    – Vincenzo Oliva
    May 7, 2016 at 7:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .