Nous définissons une séquence de type Collatzs avec 4 entiers positifs:

• n valeur de départ
• d > 1 diviseur
• m > 1 multiplicateur
• i incrément

(Dans la séquence originale de Collatz d = 2 m = 3eti = 1 .)

Étant donné ces entiers sseront créés de la manière suivante:

• s(0) = n
• si k > 0ets(k-1) mod d = 0alorss(k) = s(k-1) / d
• si k > 0et s(k-1) mod d != 0alorss(k) = s(k-1) * m + i

Un exemple de séquence avec d = 2, m = 3, i = 5et n = 80seras = 80, 40, 20, 10, 5, 20, 10, 5, 20, ... .

Chaque séquence atteindra des valeurs plus élevées que toute limite donnée (c'est-à-dire que la séquence est divergente) ou entrera dans une boucle infinie si pour certains tet u( t!=u) l' s(t) = s(u)égalité sera vraie.

Dans notre problème si la valeur d'un élément de séquence est supérieure à 10^9 ou s'il n'y a pas de répétition d'élément avant le 1000e élément, la séquence est considérée comme divergente.

La tâche

Vous devez écrire un programme ou une fonction qui prend les entiers positifs d met icomme entrées et sorties tous les différents types de fin des séquences (boucles infinies et divergence) dont les valeurs de départn = 1, 2, 3, ... 999, 1000 peuvent produire.

Détails d'entrée

• L'entrée est une chaîne ou une liste (ou son équivalent le plus proche dans votre langue) représentant (de la manière habituelle) trois entiers positifs d, met idans cet ordre. det msont au moins 2. Aucun de ces nombres n'est supérieur à 100.

Détails de sortie

La spécification de sortie est un peu verbeuse. Cela pourrait valoir la peine de consulter les exemples en premier.

• Vous devez sortir vers la sortie standard (ou l'alternative la plus proche) ou renvoyer une chaîne.
• Si une séquence divergente est possible, la première ligne doit l'être DIVERGENT.
• Une représentation unique de la boucle d'une séquence est sa rotation où le plus petit nombre est le dernier séparé par des espaces. Par exemple, si s = 2 1 4 2 1 4 2 1la boucle est 4 2 1.
• Dans chaque ligne suivante, vous devez sortir chaque boucle unique exactement une fois précédée du mot LOOP. Par exempleLOOP 4 2 1
• Les boucles doivent être en ordre croissant par rapport à leur dernier élément.
• Le retour à la ligne est facultatif.

Exemples:

Les premières lignes sont les entrées et les suivantes jusqu'à ce qu'une ligne vierge soit les sorties.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

Implémentation de référence en Python 3 sur Ideone.

C'est le golf de code, donc l'entrée la plus courte l'emporte.

Python 3, 269 254 252 246 octets

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

(Maintenant 10 fois plus lent pour économiser quelques octets. Code de golf typique.)

Entrez une liste via STDIN (par exemple [2, 3, 1]). Je pense qu'il doit y avoir une meilleure façon de standardiser les cycles ...

L'approche est assez simple - testez les 1000 numéros et ne prenez que les sorties uniques. Cependant, il y a deux petites astuces là-dedans:

• Les boucles sont représentées par des tuples non vides, mais plus important encore, la divergence est représentée par un tuple vide . C'est bien parce que:

  • Il ne casse pas sortedet apparaîtra même avant tous les tuples de boucle
  • Il nous permet de sélectionner une chaîne via x and"LOOP"or"DIVERGENT"
  • *()[::-1] n'affecte pas print
• Les boucles sont construites vers l'arrière pour transformer "trier par ordre croissant par le dernier élément" en "trier par ordre croissant par premier élément", ce qui élimine le besoin de passer un lambda sorted.

Soumission précédente, 252 octets

d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

Celui-ci est beaucoup plus rapide.