# fcycle.py 
# Fig. 27.2 


MOD = 2**31 - 1   # a prime number 
CONST = 16807     # an integer between 1 and MOD-1
'''
MOD = 13   # a prime number 
CONST = 7  # an integer between 1 and MOD-1
'''

def dLoop(x):
  if x < 17:
    return x+1
  else:
    return (x%17)+6


def bLoop(x):
  if x < 6:
    return x+1
  else:
    return (x%6)+2



def lehmer(r):
  # Compute pseudo-random number using a Lehmer PRNG
  return (CONST * r) % MOD
  '''
   after a long wait, it reports:
     pure cycle
     lehmer. Cycle len: 2147483646  tail len: 0
     which is 2^31-2
  '''



def findCycle(fn, start):
  slow = start
  fast = start
  cycleLen = 0
  tailLen = 0
  # let fast catch up to slow
  while True:
    slow = fn(slow)
    fast = fn(fn(fast))
    cycleLen += 1
    if slow == fast:
      break
  
  if slow == start:  # there's no tail
    print("pure cycle")
  else:  # slow is sent once more round cycle
    cycleLen = 0
    while True:
      slow = fn(slow)
      cycleLen += 1
      if slow == fast:
        break
    # finished calculating cycle len

    # set fast back to start to calculate tail
    fast = start
    tailLen = 0
    while True:
      fast = fn(fast)
      slow = fn(slow)
      tailLen += 1
      if fast == slow:
        break
  return cycleLen, tailLen


c, t = findCycle( dLoop, 0)
print("dLoop. Cycle len:", c, " tail len:", t)

c, t = findCycle( bLoop, 0)
print("bLoop. Cycle len:", c, " tail len:", t)

c, t = findCycle( lehmer, 6)
print("lehmer. Cycle len:", c, " tail len:", t)