load "LsPrime.rb"
# Calcule la décomposition en facteurs premiers
# ------------------------------------------------
def decomposition(n)
  # Quels sont les facteurs premiers  de n ?
  dec=[]
  ind=0
  while n>1
    while (n%LsPrime[ind]) != 0
      ind=ind+1
      # S'il n'y a plus de premiers disponibles 
      # on en calcule d'autres
      LsPrime.calcule(n) if ind>=LsPrime.size
    end
    compte=0
    # Pour chaque facteur premier, on cherche sa multiplicité
    while n%LsPrime[ind]==0
      compte=compte+1
      n=n/LsPrime[ind]
    end
    # Pour chaque facteur premier, on cherche sa multiplicité
    # Ajout du facteur premier avec sa multiplicité à la liste
    dec << [LsPrime[ind],compte]
  end
  return dec
end

# Somme des diviseurs stricts de n 
# ---------------------------------
def suivant_aliquote(n)
  return 0 if n==1
  dec=decomposition(n)
  s=1
  dec.each do |f|
    # f[0] est le facteur premier 
    # f[1] est son exposant
    s=s*(f[0]**(f[1]+1)-1)/(f[0]-1)
  end
  # On enleve le nombre n de la somme des diviseurs
  return s-n
end

# Calcule k termes de la suite issue de n
# -----------------------------------------
def suite_aliquote(n,k)
  t=[n]
  for i in 1..(k-1)
    n=suivant_aliquote(n)
    t<<n
  end
  return t
end

# Calcule jusuqu'à k termes de la suite issue de n.
# S'arrête avant si 1 ou un cycle est atteint
# --------------------------------------------------
def analyse_suite(n,k)
  t=[n]
  for i in 1..(k-1)
    n=suivant_aliquote(n)
    if (n==1 || t.rindex(n)!=nil)
      t<<n
      return t
    end
    t<<n
  end
  return t
end

# Indique si la suite calculée tombe sur 1, 
# sur un cycle ou est indéterminée
# ------------------------------------------
def statut_suite(t)
  result=-1
  if t.last==1
    result=0
  else
    i=t[0..t.size-2].rindex(t.last)
    if i!=nil
      result=t.size-i-1
    end
  end
  return result
end

# Recherche de cycles
# ------------------------
def cherche_cycle(deb,fin,lg)
  for n in deb..fin
    t=analyse_suite(n,lg+1)
    if statut_suite(t)==lg
      puts "Trouvé cycle de longueur #{lg} pour #{n} :"
      p t
    end
  end
end