(Each question builds off the previous. #2 is answered already.)

We will guide you through a a proof of Lucas' Theorem. This theorem states that (tis odd if (k)i s (n); for all $i 0,1..s and even otherwise. Here. (n, is the i-th least significant bit of n if written in binary. For example, 11 in binary is 1011 and 3 is 11 (or 0011 to make sure that both have four bits). Now 0011 is bitwise at most 1011, and thus Lucas' Theorem states that (1) is odd. Which it is, since (1) 165. f(n) := max{k E \No such that 2k divides n). For example, f(5-0, f(14) = 1. f(12) 2 Let n ::: 1000101010101010100001010101011 111100110100000, where this is to be read in binary. What is f(n)? Define g(n):f(n!). We want to find a closed formula for g(n). First of all, we want to find a recurrence for gin). If n is odd, then it is pretty easy to see thatg(n) g(n 1). If n is even, try to write g(n) in terms of g(n/2). Once you have figured this out, you will surely be able to answer the following question: What is g(8, 000, 000, 000,000) g 9(4,000,000,000, 000)2 where these numbers are in Please don't use" in your answer! Farn e N, le n) denate the number of isinthe sinary representation of n. Far example, uw(9) 2, since $95 is 1001 in binary. Try to find a closed formula for g(n) in terms of n and u(n). If you succeed, the following question will be very easy. Let n 10000000000000011 in binary notation. What is g(n)? Write your answer in binary! Let n 1152921504606846987. If we compute (E) mod 2 for k..7, which sequence do we get? Write your answer as a simple 0/1 string. For example, if your sequence is (1,0, 1,0,1,0,1,0) ,answer 10101010