$L_p$ contains all binary strings whose value as binary number is prime. What are those values?

Question

Context-: https://math.stackexchange.com/questions/1600257/determining-if-a-binary-string-represents-a-prime-integer

Confused text-:

The problem of testing primality can be expressed by the language LP consisting of all binary strings whose values as a binary number is prime. That is, given a string of 0's and 1's, say "yes" if the string is the binary representation of a prime and say "no" if not. For some strings, this decision is easy. For instance, 0011101 cannot be the representation of a prime, for the simple reason that every integer except 0 has a binary representation that begins with 1. However, it is less obvious whether the string 11101 belongs to LP, so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example.

I didn't understand why 0011101 can't be representation of prime.

Answer 1

The concept of prime is the usual one (a non-unit positive integer is prime if and only if it has no positive integer divisors except for $1$ and itself).

The author is probably just trying to say that, in general, deciding whether a given binary number is prime is a non-trivial task. However, you might be able to easily tell that some binary numbers cannot possibly be prime (for example any binary number that ends with $0$ and is not $10$).

I don't really agree with the provided explanation though. $0011101$ is a valid binary representation of the decimal number $29$, just like $029$ is a valid alternative decimal representation of the decimal number $29$. In a positional number system adding leading zeroes to a number does not change its value.

Perhaps the author has previously restricted him/herself to binary representations whose most significant bit is $1$ (except for the number $0$)?

Answer 2

I got the answer. I don't know which rule is that, but every binary number except 0 starts with 1. So We are starting 0011101 with 0, so it is not valid binary representation hence not binary prime. But it is hard to decide if 11101 is prime binary string or not as it needs to be processed using some algorithms.