Consider a set of functions:

  • head(l) returns first bit from list l, e.g.

    head([0,1,0]) = 0, 
    head([1]) = 1
  • tail(l) returns a list by removing first element from l, e.g.

    tail([0,1,0]) = [1,0],
    tail([1]) = []
  • a:l appends bit a to beginning of list l, e.g.

    1:[0,1,0] = [1,0,1,0].
  • xor takes takes as input two bits and returns a bit.

    if (a == b) 
  • f1 takes as input a list and returns another list.

    if (s == []) then 
    else if (head(s) == 0) then  
    else if (head(s) == 1) then 
    • f2 takes as input a bit and a list and returns a bit.

      f2(b,s) if (s == []) then return(b) else if (head(s) == 0) then return(f2(xor(b,1),tail(s))) else if (head(s) == 1) then return(xor(b,1)) endif

  • g1 takes as input a nonnegative number and returns a list.

    if (n == 0) then 
      return f1(g1(n-1))
  • g2 takes as input a nonnegative number and returns a bit.

    if (n == 0) then 
      return f2(g2(n-1),g1(n))

Can anyone explain what the function g2() returns?

I am able to find out g1() returns a list in binary for example

g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]
  • 1
    $\begingroup$ Welcome! I am not sure this question suits this site; you are asking to figure out what a program computes without offering much of your own thought. What does g1 compute in general. $\endgroup$ – Raphael Nov 27 '12 at 11:46
  • $\begingroup$ btw, what programming language is this? At first it looked like Python, but the endif statements and missing colons after the if statements clearly indicate it's not. $\endgroup$ – Daniel Eberts Nov 27 '12 at 12:57
  • $\begingroup$ You are wrong : g1(n) = [ n mod 2 ] $\endgroup$ – Anton Nov 27 '12 at 13:50
  • 1
    $\begingroup$ @DanielEberts this could be valid LUA code. $\endgroup$ – John Dvorak Nov 27 '12 at 14:11


  • g1(0) = [0] so you can see that f1 for [0] returns [1] and for [1] returns [0]. From here g1 must be clear.

  • f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)

  • after you know that g2(0) = 0 and the above hints it is easier to calculate g2

I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.

  • $\begingroup$ Hi All, Thanks for your inputs. I am able to find what g2() returns. g2(n)= 0 if n is even and 1 if n is odd. $\endgroup$ – akshay Nov 28 '12 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.