retagged by
2,018 views
9 votes
9 votes

Consider the following statements:

  1. For every positive integer $n,$ let $\#{n}$ be the product of all primes less than or equal to $n.$
     Then, $\# {p}+1$ is a prime, for every prime $p.$
  2. $\large\pi$ is a universal constant with value $\dfrac{22}{7}.$
  3. No polynomial time algorithm exists that can find the greatest common divisor of two integers given as input in binary.
  4. Let $L \equiv \{x \in \{0,1\}^{*}\mid x \text{ is the binary encoding of an integer that is divisible by 31}\}$
    Then, $L$ is a regular language.

Then which of the following is TRUE ?

  1. Only statement (i) is correct.
  2. Only statement (ii) is correct. 
  3. Only statement (iii) is correct.
  4. Only statement (iv) is correct. 
  5. None of the statements are correct.
retagged by

1 Answer

Best answer
9 votes
9 votes

π is not equal to 22/7

https://math.stackexchange.com/questions/93222/is-22-7-equal-to-the-pi-constant

For (i), consider $n=9$. Now, we get product of primes less than $9$ as $\#n = 2\times 3\times 5\times 7\times 9 = 1890.$ Now $\#n+1 = 1891$ is not a prime as $1891 = 31 \times 61.$  (This example might be difficult to arrive during exam, but this option could have been eliminated by good intuition or by seeing that other there are better other options).

We can construct dfa for binary string divisible by 31 

https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n

Option 4

selected by
Answer:

Related questions

4 votes
4 votes
1 answer
1