2

Do prime numbers have defined characteristics like say perfect squares do?

Without seeing the complete string of digits it is relatively easy to determine if a number is definitely not a perfect square by just looking at the least significant digits.

Is the same true for a prime number?

To further explain what I mean...

Imagine a game. The game generates an even number of prime and composite numbers all with the same number of digits, say 11. These numbers are not revealed to the players.

One feature of these numbers is that the least significant digit is always a 1,3,7 or 9. all other digits are effectively random.

The game displays one consecutive digit at a time starting with the least significant digit (from rightmost digit to leftmost). The players then try to determine if the entire number is prime or not prime.

The players can use any means available (outside of cheating) to try an determine if the number is going to be prime or composite.

If no player can decide if the number is prime or composite the next consecutive number is revealed.

When a player declares they know the answer. They indicate prime or composite. The complete number is revealed and if the player is correct they gain a point. If the player is wrong they lose a point.

The game continues for a set number of rounds until a winner is declared.

Sounds like fun? Well maybe not, but the point of the game is to determine at the earliest point in a round, whether a number is likely a prime or composite.

It is obvious after the first digit being a 1,3,7 or 9 it is impossible to know. But what about after each subsequent digit?

What strategies could one employ to determine if the number is prime or composite given that you do not know all the digits which will be revealed?

Guessing will result on average a losing score, so is not an acceptable strategy.

DeveloperChris
  • 338
  • Interesting question. Short answer: I'm quite sure it's no. This is only a comment because I don't have the time to flesh out my reasons in an answer. Maybe someone else will. – Ethan Bolker Sep 25 '20 at 00:06
  • 1
    I don't think this is clear. If the machine is choosing randomly (given the number $\pmod {10}$) then of course the number is much more likely to be composite, so you should always guess "composite". But I don't suppose that this is what you intended. – lulu Sep 25 '20 at 00:07
  • @lulu. I stated the game generates an even number of composites and primes, in other words guessing will on average result in a 0 score. The very last sentence was to reinforce this. – DeveloperChris Sep 25 '20 at 00:11
  • 2
    But you then need to explain how the machine is selecting the numbers. To make the odds even, the machine must be heavily biased against composites and the way the machine excludes them may convey information. – lulu Sep 25 '20 at 00:14
  • @lulu the machine randomly generates 1 million primes and composites and randomly picks 10 primes and 10 composites. However that is irrelevant. the game is only a way of conveying what I am looking for the question is the first sentence. – DeveloperChris Sep 25 '20 at 00:16
  • @ethan. the strategy would clearly be to select composites as I imagine that is an order of magnitude easier than trying to select the prime. however if you are confident it is not a composite then you could declare a prime. – DeveloperChris Sep 25 '20 at 00:18
  • 2
    As the density of primes thins out as the numbers get bigger, you would be able to tell before the last digit for most combinations if you have a prime table. I.e. if there is no prime of the form x12345678, you can infer composite if you see 12345678. You would never guess prime obviously. – Klaus Sep 25 '20 at 00:19
  • @klaus what if the length of the number was increased from 11 digits to say 25? 50 or 1000. the point is to find out if given a few least significant digits can you be confident enough to declare "composite" or even "prime". – DeveloperChris Sep 25 '20 at 00:26
  • @DeveloperChris That depends on the density of primes which you can look up. The more digits you have the more likely a prime with certain tail digits does not exist. But note that you will always need a significant amount (almost all) of digits and not just "a few". – Klaus Sep 25 '20 at 00:31
  • 2
    "A few" digits, no. A random $n$-digit number has probability approximately $0.43/n$ of being prime. If there are $k$ unknown digits that means $10^k$ possibilities, and so you expect around $0.43 \times 10^k/n$ primes. To have a good chance of no possible primes, you would need $10^k/n$ to be on the order of $1$, i.e. $k$ would need to be no more than about $\log_{10}(n)$. – Robert Israel Sep 25 '20 at 00:36
  • You can certainly never declare "prime" with certainty: if even one digit is unknown, there are always $3$ possibilities for that digit which make the number divisible by $3$. – Robert Israel Sep 25 '20 at 02:37
  • @RobertIsrael is it possible to declare"not prime" with any certainty? – DeveloperChris Sep 25 '20 at 02:42
  • 1
    @DeveloperChris Yes: if you know all except a few digits, you can just search all possibilities for those digits, and if none of the candidates give you a prime you are certain. For example, none of the $9$ numbers of the form $x149$, $x \in {1,\ldots,9}$, are prime. – Robert Israel Sep 25 '20 at 03:59
  • Would it not be correct to say that if a number has a repeating pattern say 3 nines pop out in a row that it is not likely to be prime because primes are supposedly pseudo random and while 3 nines is not impossible it is likely improbable? – DeveloperChris Sep 25 '20 at 04:28
  • 1
    I did a search of a couple of million 64bit primes and found lots of repeating numbers so that's a bust – DeveloperChris Sep 25 '20 at 09:10
  • @DeveloperChris We can only rule out a prime quickly, if we find a small prime factor. Since the choice of the digit is free, we can always achieve that the resulting number is neither divisible by $3$ nor by $7$ nor by $11$ , even if only one digit (not the ending digit) is missing. Hence, we cannot quickly rule out a prime whatever fragment is given , unless the ending digit is not $1,3,7$ or $9$. – Peter Sep 25 '20 at 13:23

0 Answers0