Determining if a binary string represents a prime integer

Question

Let $\Sigma = \{0,1\}$ and $w$ be the string $0011101$ over $\Sigma$.

If we work out what $w$ is, $w$ is the binary representation of $57$, which is not prime.

It is remarked in Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman, that $w$ cannot be the representation of a prime because

"...every integer except $0$ has a binary representation that begins with $1$."

And I fail to follow the reasoning. Could someone knock the rocks in my head back into place? Thanks!

Answer 1

There is no mistake and the meaning is clear. However, it might have been simpler to state that $0011101$ is not the binary representation of any number (prime or not) because except for $0$, the binary representation of a number always start by $1$.

Let me quote the whole paragraph:

The problem of testing primality can be expressed by the language $L_P$ 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 $L_P$, so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example.

Answer 2

I think it's likely a mistake, although I don't see any mention in the errata.

Perhaps he means every prime except 2 when expressed as a binary digit ends with a 1?

Answer 3

Not sure what the book has in mind there. Perhaps there is a line missing? Is it possible to give a bit more context than you have so far?

Anyway, some remarks about divisibility for binary numbers: A binary number is divisible by $3$ (i.e., $11_2$) iff the number of even-indexed $1$'s and the number of odd-indexed $1$'s are equivalent modulo $3$. Thus, for instance, $57 = 111001_2$ is divisible by $3$, because there are two even-indexed $1$'s and two odd-indexed $1$'s. $2 \equiv 2 \pmod 3$ (trivially), so this number is divisible by $3$.

Note that this is not true of $29 = 11101_2$, which has one even-indexed $1$ and three odd-indexed $1$'s. This doesn't, however, show that $29$ is a prime, although obviously it happens to be. The first counterexample is $5^2 = 25 = 11001_2$, which has one even-indexed $1$ and two odd-indexed $1$'s, but is obviously composite.

Answer 4

Okay. I found the text online and this is my interpretation.

However the formatting was hard to read, a page or two seems to be missing, and it's a subject I have never studied not even an iota....

but... I think

He's talking about writing a string parser. You give it a binary string and the program is supposed to analyze whether the string is member of a described set. The set could be ... anything. Lp would be the set of prime numbers. But Lc would be the set of valid C programs. I imagine other sets could be capital cities transposed to binary strings but I could be misunderstanding.

So, I think he is saying sometimes it's easy for the program to recognize if a string is a member of a set. If the set is of strings that start with "010" it'd be trivial. Sometimes it is hard. My understanding is if the set is Lc terminating C programs the only way to tell is to actually run it. (Again, I have never studied this field so I might just have said something utterly idiotic and stupid.) So he's saying (I think) the set of Lp is sometimes easy: If the string begins with a 0 then the string isn't an integer at all and can not be a prime. But if the string begins with a 1 and is therefore an integer, there isn't necessarily any easy way to tell if a number is prime.

That's what I think he is saying. 0011101 is not a number therefore not prime. But 11101 is 29 which... we have to do some programming to determine if it is prime simply by looking at it.

I think.

Excerpt:

============

"32 CHAPTER 1. AUTOMATA: THE METHODS AND THE MADNESS

Set-Formers as a Way to Define Languages

It is common to describe a language using a "set-former" :

{w | something about w)

This expression is read "the set of words w such that (whatever is said about w to the right of the vertical bar}." Examples are:

1 . {vj | w consists of an equal number of O's and 1 's } .

2. {w | w is a binary integer that is prime }.

3. {w J id is a syntactically correct C program }.

It is also common to replace w by some expression with parameters and describe the strings in the language by stating conditions on the parame- ters. Here are some examples; the first with parameter n, the second with parameters i and j:

1. {0™1" | n > 1}. Read "the set of 0 to the n 1 to the n such that n is greater than or equal to 1," this language consists of the strings {01,0011,000111,...}. Notice that, as with alphabets, we can raise a single symbol to a power n in order to represent n copies of that symbol.

2. {0 l V | 0 < i < j}. This language consists of strings with some O's (possibly none) followed by at least as many l's.

...*page missing????....

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 L p , so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example. □

One potentially unsatisfactory aspect of our definition of "problem' 7 is that one commonly thinks of problems not as decision questions (is or is not the following true?) but as requests to compute or transform some input (find the best way to do this task). For instance, the task of the parser in a C compiler can be thought of as a problem in our formal sense, where one is given an ASCII string and asked to decide whether or not the string is a member of L c , the set of valid C programs. However, the parser does more than decide. It produces a parse tree, entries in a symbol table and perhaps more. Worse, the compiler as a whole solves the problem of turning a C program into object code for some "