HW3 Due Wed Oct 14th

1. At time \(t = 0\) you turn on a light switch. After half a second you turn it off. After another quarter second you turn it back on, then turn it of after \(1/8\) seconds, and so on. Is the light on or off at time t = 1?

2. Write out the truth tables for the following statements.

   1. P and Q
   2. P ⇒ Q
   3. (P and not P ) ⇒ Q

3. Diophantus’s epigram is: His boyhood lasted for \(\tfrac{1}{6}\) of his life, his beard grew after \(\tfrac{1}{12}\) more; after \(\tfrac{1}{7}\) more he married, and his son was born \(5\) years later; the son lived to half his father’s age and the father died four years after his son. How old was Diophantus when he died?

4. Consider numbers of the form \(n^2 + 1\). How many of them are prime? Spend about twenty minutes looking this up on the internet and write a summary of what you found. How easy did you find it to find this information?

5. Find an (elementary) estimate for the complexity of the Euclidean algorithm, i.e. if you start with two numbers \(a\) and \(b\), what is the maximum number of operations/steps you need? What would you need to know to find an average complexity estimate?

6. As I was going to St Ives, I met a man with seven wives, Each wife had seven sacks, Each sack had seven cats, Each cat had seven kits: Kits, cats, sacks, and wives, How many were there going to St Ives?