1

For example I'm given $53687$ and I'm asked to find the smallest prime such that it ends with $53687$.

Do I just need to brute force check the primality of all values that end in the given value?

I expect there's no way to get the exact answer, but is there a way to get at least an order of magnitude of the goal prime so I can skip to brute forcing on the right magnitude?

I'd hate to start brute forcing if there's a way to determine it must be greater than $10,000,000$

Kay K.
  • 9,931
user708873
  • 11
  • 2
    There's not going to be an easy answer to this. Just do the search. – lulu Sep 12 '22 at 18:14
  • Yes, you are supposed to try a bit. It took me three trials in less than $10$ seconds. Then $353687$ is this smallest prime. (You can ask a similar question, to continue like this, see this post. Also there, one has to try, but it is known that this terminates soon.) – Dietrich Burde Sep 12 '22 at 18:14
  • @DietrichBurde thanks for linking to that post. My question is slightly different, for mine the given ending is not prime. For my small example I do think brute force would be best, although for larger given endings (say 50 digits long) I feel like just brute forcing it is quite inefficient. – user708873 Sep 12 '22 at 18:26
  • 1
    I suppose that you don't have to search too far, at least not with examples you have been asked for. I tried $123456789$, and a quick search gave the prime $28123456789$. Of course, bigger numbers will be less efficient to find. But then also an estimate will not help to make it more efficient. Finally, properties of prime numbers can pose a hard problem, as we know from cryptography. – Dietrich Burde Sep 12 '22 at 18:43
  • I noticed that often adding 100, or 1000 or 10,000 on the left to a given prime will often hit on a prime. For example 3 and 103, 7 and 107, 31 and 131, 37 and 137...Your number being a six digit number, you may try first 1353687, 10653687... – user25406 Sep 12 '22 at 20:26
  • 2
    The theoretical result that addresses how far one might need to search, by the way, is called Linnik's theorem. – Greg Martin Sep 12 '22 at 20:30
  • Useful fact here: In base-ten, all prime numbers (except 2 and 5) end in the digit 1, 3, 7, or 9. – Dan Sep 12 '22 at 22:36

1 Answers1

1

Do I just need to brute force check the primality of all values that end in the given value?

Well, there are some values you can rule out when determining if $10^5n + 53687$ is prime.

  • Since $53687$ is itself composite ($37 \times 1451$), we know that $n$ is nonzero. Nor can $n$ be a multiple of either $37$ or $1451$.
  • By the sum-of-digits rule for divisibility by $3$, we know that $n \operatorname{mod} 3 \ne 1$.

But otherwise, yes, just brute-force it. It turns out that you don't have to look far: The answer is $353687$.

Dan
  • 14,978