(Proof techniques.) You’re a programmer! You’ve found yourself dealing with a pr
ID: 3143404 • Letter: #
Question
(Proof techniques.) You’re a programmer! You’ve found yourself dealing with a program mystery(n) that has no comments in its code, and you want to know what it does. After some experimentation, you’ve found that mystery(n) takes in as input a natural number n, and does the following:
(i) If n is either 0, 1, 2, or 3, output n and stop. Otherwise, go to (ii).
(ii) If n is even, replace n with n/2 and go back to (i). Otherwise, go to (iii).
(iii) Replace n with n + 5 and go to (i).
Come up with the following proofs about mystery(n):
(a) Use the contrapositive to prove the claim “if this program outputs 3 on input n, then n is not a power1 of 2.”
(b) Disprove the claim “Given any natural number n as input, this program will eventually stop” by finding a counterexample.
(c) Prove by construction the claim “There is some input to this program that causes it to output 0.”
(d) Prove that “the input to this program is 1” and “the output of this program is 1” are equivalent statements (that is, do an A B proof.)
A number n is a power of 2 if there is some integer k Z such that n = 2k .
Explanation / Answer
(i) If n is either 0, 1, 2, or 3, output n and stop. Otherwise, go to (ii).
(ii) If n is even, replace n with n/2 and go back to (i). Otherwise, go to (iii).
(iii) Replace n with n + 5 and go to (i)
output table for various inputs -
(a) Use the contrapositive to prove the claim “if this program outputs 3 on input n, then n is not a power1 of 2.”
For a number 2k where k > 1
it will go to step (ii) and become 2k-1
again it will go to step (i), and will be referred to step (ii) untill it is greater than 2
next it will become 2k-2 and referred back to step (i)
This process will keep getting repeated untill it becomes 2 and then the program will stop.
So if a number is of the form 2k, it will output as 2.
Also if any number is of the form 2k . 3, it will result into 3 because in step (ii) it will keep getting half and the power of 2 will exhaust at one point, leaving behind 3.
So if output is 3, it has be of the form 2k . 3m where m > 0 and k >= 0
(b) Disprove the claim “Given any natural number n as input, this program will eventually stop” by finding a counterexample.
As shown in the output table, for numbers which are multiple of 5, the program doesn't stop.
e.g. 5
(i) n = 5 -> (ii)
(ii) n is odd so -> (iii)
(iii) n = n+5 = 10 -> (i)
(i) n > 3 -> (ii)
(ii) n is even so n = n/2 = 10/2 = 5 -> (i)
(i) n = 5 -> (ii)
and it keep getting repeated.
(c) Prove by construction the claim “There is some input to this program that causes it to output 0.”
If input is 0, the output will 0.
other than 0, there is no input which will result into output as 0.
(d) Prove that “the input to this program is 1” and “the output of this program is 1” are equivalent statements (that is, do an A B proof.)
to be proved
1. if input of the program is 1, output is 1
2. if output of the program is 1, input is 1
1. if input of the program is 1, output is 1
for input 1, clearly step (i) will output as 1
2. if output of the program is 1, input is 1
There can be only following output possible for this program
(0), (1), (2), (3), (never stops)
Let's say there is a number k, which has output as 1.
This number k is not equal to 1, and has to be >3 to pass the first step (i).
now since this number can be either even or odd
case 1: k is even
k > 3 so k/2 > 1 so output can not be 1
case 2: k is odd
k > 3 so k+5 > 8, and it will be referred to step (i) and then (ii)
Since now it as become even, it will again be divided by 2. and (k+5)/2 > 4.
(Reason - Program won't stop after passing through step(iii), and step(ii) will never produce n = 1}
Input Output 0 0 1 1 2 2 3 3 4 2 5 infinite loop 6 3 7 3 8 2 9 3 10 infinite loop 11 2 12 3Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.