# cycles-q11
# Exs for Section 10, Q.11

from collections import Counter

SIZE = 10000
MAX_ITERS = 500

def f(n):
  if n%2 == 1:
    return 3*n-1
  else:
    return n//2

def genCycleSeq(v):
  global numTooLong
  seq = [v]
  iters = 0
  i = v
  while (not f(i) in seq) and (iters < MAX_ITERS):
    i = f(i)
    seq.append(i)
    iters += 1
  if iters == MAX_ITERS:
    seq = -1
    numTooLong += 1
  return seq

cycleSeqs = [-1 for i in range(SIZE+1)]
setCycles = []   # each unique sequence as a set
cycleIDs = [-1 for i in range(SIZE+1)]
                 # cycle ID assigned to each number
numTooLong = 0
for v in range(1, SIZE+1):
  cycleSeqs[v] = genCycleSeq(v)

# assign a cycle ID to the numbers in the seq
cycleID = 0
for v in range(1, SIZE+1):
  if cycleSeqs[v] != -1:
    isNewCycle = True
    cycSet = set(cycleSeqs[v])
    for cs in setCycles:
      if cycSet.intersection(cs) != set():
        isNewCycle = False
        elem = next(iter(cs))
        cycleNo = cycleIDs[elem]
        for el in cycSet:
          if el < SIZE+1:
            cycleIDs[el] = cycleNo
        # print(*cycleSeqs[v], "; cycle", cycleNo)
        break;
    if isNewCycle:
      for el in cycSet:
        if el < SIZE+1:
          cycleIDs[el] = cycleID
      # print(*cycleSeqs[v], "; cycle", cycleID)
      cycleID += 1
    setCycles.append(cycSet)

print("No. of cycleSeqs:", cycleID)
print("No. of seqs >", MAX_ITERS, ":", numTooLong)
for c in range(cycleID):
  for i in range(1, SIZE+1):
    if cycleIDs[i] == c:
      print(c, ":", *cycleSeqs[i])
      break
cycTots = Counter(cycleIDs)
print(cycTots)