#-------------------------------------------------------------------------------
#  Generators.py
#  Functions that return generators.
#-------------------------------------------------------------------------------
import math as m

def integer_generator():
   """Generates all non-negative integers."""
   k = 0
   while True:
      yield k
      k +=1
   # end
# end

def odd_square_generator():
   """Generates the squares of all odd positive integers."""
   k = 1
   while True:
      yield k**2
      k += 2
   # end
# end

def fibonacci_generator():
   """Generates all Fibonacci numbers."""
   a = 0
   b = 1
   yield a
   yield b
   while True:
      c = a+b
      yield c
      a = b
      b = c
   # end
# end

def prime_generator():
   """Generates all prime numbers"""
   yield 2
   k = 3
   while True:
      isPrime = True
      for d in range(3, m.floor(m.sqrt(k))+1):
         if k%d==0:
            isPrime = False
            break
      # end
      if isPrime: yield k
      k += 2
      # end
   # end
#end

def gcd(a, b):
   """Returns the GCD of a and b"""
   if a%b==0:
      return b
   else:
      return gcd(b, a%b)
   # end
# end

def relative_prime_generator(n):
   """ Generates all positive integers relatively prime to n"""
   k = 1
   while True:
      if gcd(k, n)==1:
         yield k
      k += 1
   # end
# end
   

# end

def phi(n):
   """
   Returns the value of the Euler Totient function, which is the number of
   numbers in the range 1...n that are relatively prime to n.
   """
   L = []
   for k in relative_prime_generator(n):
      if k<n:
         L.append(k)
      else:
         break
   # end
   return len(L)
# end

def list_generator():
   """
   Returns a sequence of lists, each being the 'successor' of the last, 
   starting with the empty list []. The 'successor' of a list L is the
   list L+[L].
   """
   L = []
   while True:
      yield L
      L = L+[L]
   # end
# end


#------------------------------------------------------------------------------
if __name__=='__main__':
   
   #"""
   print()
   for k in integer_generator():
      if k<30:
         print(k, end=' ')
      else:
         break
      # end
   # end
   print()
   #"""

   """
   print()
   count = 0
   for k in odd_square_generator():
      if count<20:
         print(k, end=' ')
         count += 1
      else:
         break
      # end
   # end
   print()
   """

   """
   print()
   for n in fibonacci_generator():
      if n<100:
         print(n)
      else:
         break
      # end
   # end
   """

   """
   print()
   for n in prime_generator():
      if n<1000000:
         print(n)
      else:
         break
   # end for
   """

   """
   print()
   for n in relative_prime_generator(100):
      if n<100:
         print(n)
      else:
         break
   # end for
   """

   """
   print()
   print("phi(",1368,") = ", phi(1368))
   """

   """
   print()
   for L in list_generator():
      if len(L)<10:
         print(len(L), "=", L)
      else:
         break
      # end
      print()
   # end
   """

   print()
# end