0

I need to find a prime with the info, the sum of all its digits, the first and last digit and how much digits the number has.

For example, lets check if $13$ is prime.

First digit: 1

Last digit: 3

Sum of all digits: 13 -> 1 + 3 = 4

Amount of digits: 2

How can I be sure that this number is 100% prime by only using this info?

A...................
  • 131
  • 2
    If the number is larger than $2$, then it cannot be prime of it's even. If its digits sum to a multiple of $3$ then it's divisible by $3$ and is not prime. If it ends in a $0$ or a $5$, then it's divisible by $5$ and is not prime. Typically it's difficult to determine whether large numbers are prime because there are few tricks and techniques to determine if it's prime, which is why primes are so important in cryptography. – Bilbottom May 10 '18 at 09:22
  • If last digit is even then the no. is a non-prime. If the sum of digits is divisble by 3 , the no. itself is divisble by 3. If the last digit is 5 or 0, the no. is divisble by 5. –  May 10 '18 at 09:24

4 Answers4

3

Unfortunately no, you cannot deduce the primality of a number from the number and sum of its digits, in general. The best one can achieve, currently, is a polynomial time algorithm. There is more information on Wikipedia.

However, you can use the so-called divisibility criteria, to weed out composite numbers that have those factors for which you have a criterion.

rubik
  • 9,344
2

That can't be done.

The numbers $1753$ and $1573$ share all the mentioned properties, but only one of them is prime.

Henrik supports the community
  • 6,831
1

For certain numbers, say e.g., $3, 7, 109$ and $673$, if you concatenate any two of these numbers in any order , the resulting number will still be a prime ; as in this case Concatenating $7$ at the end of $673$ resulting in $6737$ which is a prime . Concatenating 7 in the front of $673$, which gives $7673$ , is also a prime . So is $1093, 1097, 3109, 7109$. However, this cannot be generalized and as such is a special case.

Hence, it can't be used as a primality test.

0

If the first and the last digit of a number is known and the sum of the digits is known, there is no way to guess if it is prime or not because there are infinitely many numbers satisfying these conditions.

E.g. The first digit of a number is 1, the last digit is 3 and the sum of the digits is 4. The we will have infinitely any primes and non primes as shown below

13 = prime,

103 = prime,

1003 = composite,

10003 = composite,

100003 = prime

Nilotpal Sinha
  • 19,424