La séquence Collatz (également appelée problème 3x + 1) est l'endroit où vous commencez avec n'importe quel entier positif, pour cet exemple, nous utiliserons 10 et lui appliquerons cet ensemble d'étapes:

if n is even:
    Divide it by 2
if n is odd:
    Multiply it by 3 and add 1
repeat until n = 1

10 est pair, donc nous divisons par 2 pour obtenir 5. 5 est impair, donc nous multiplions par 3 et ajoutons 1 pour obtenir 16. 16 est pair, alors coupez-le en deux pour obtenir 8. La moitié de 8 est 4, la moitié de 4 est 2, et la moitié de 2 est 1. Comme cela nous a pris 6 étapes, nous disons que 10 a une distance d'arrêt de 6.

Un nombre Super Collatz est un nombre dont la distance d'arrêt est supérieure à la distance d'arrêt de chaque nombre inférieur à lui. Par exemple, 6 est un nombre Super Collatz puisque 6 a une distance d'arrêt de 8, 5 a une distance d'arrêt de 5, 4 a 2, 3 a 7, 2 a 1 et 1 a 0. ( A006877 dans l'OEIS) Vous devez prendre un nombre n en entrée et sortir tous les nombres Super Collatz jusqu'à n .

Règles

• Un programme ou une fonction complète est acceptable.

• Vous ne pouvez pas précalculer ou coder en dur la séquence Super Collatz.

• Vous pouvez prendre des entrées dans n'importe quel format raisonnable.

• La sortie peut être renvoyée sous forme de liste à partir de la fonction, ou imprimée sur STDOUT ou un fichier. Celui qui est le plus pratique.

• Les entrées non valides (non-nombres, décimales, nombres négatifs, etc.) entraînent un comportement non défini.

Exemple de python non golfé

def collatzDist(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + collatzDist(n / 2)
    return 1 + collatzDist((n * 3) + 1)

n = input()

max = -1
superCollatz = []
for i in range(1, n + 1):
    dist = collatzDist(i)
    if dist > max:
        superCollatz.append(i)
        max = dist 

print superCollatz

Exemple d'E / S:

#in       #out
 4     --> 1, 2, 3
 50    --> 1, 2, 3, 6, 7, 9, 18, 25, 27
 0     --> invalid
 10000 --> 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171

Voici également les 44 premiers numéros Super Collatz:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799

Pyth, 23 octets

q#eol.u@,/N2h*N3NN)STSQ

Manifestation

Cela fonctionne en prenant le max de la plage jusqu'à chaque nombre par leur distance d'arrêt Collatz, et en vérifiant si ce max est le nombre en question.

Python 2, 104 octets

c=lambda x:x>1and 1+c([x/2,x*3+1][x%2])
lambda n:[1]+[x for x in range(2,n)if c(x)>max(map(c,range(x)))]

cest une fonction d'aide qui calcule la distance de Collatz pour un entier donné. Le lambda sans nom est la fonction principale, qui calcule les nombres super Collatz jusqu'à (mais sans inclure) l'entrée.

Dyalog APL , 41 octets

(∪⊢⍳⌈\)≢∘{1=⍵:⍬⋄2|⊃⌽⍵:⍵,∇1+3×⍵⋄⍵,∇⍵÷2}¨∘⍳

Une fonction sans nom. Nom ou parenthèse à appliquer.

Cas de test:

       ((∪⊢⍳⌈\)≢∘{1=⍵:⍬ ⋄ 2|⊃⌽⍵:⍵,∇ 1+3×⍵ ⋄ ⍵,∇ ⍵÷2}¨∘⍳)¨4 50 10000
┌─────┬────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────┐
│1 2 3│1 2 3 6 7 9 18 25 27│1 2 3 6 7 9 18 25 27 54 73 97 129 171 231 313 327 649 703 871 1161 2223 2463 2919 3711 6171│
└─────┴────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────┘

0 entraîne un comportement indéfini.

ES6, 86 83 octets

n=>(i=m=0,c=n=>n<3?n:c(n&1?n*3+1:n/2)+1,[for(x of Array(n))if(c(++i)>m&&(m=c(i)))i])

Edit: économisé 3 octets en passant d' filterune compréhension de tableau.

Haskell, 84 octets

c 1=0;c x|odd x=1+c(3*x+1)|0<1=1+c(div x 2)
f x=[n|n<-[1..x],all(c n>)$c<$>[1..n-1]]

C'est extrêmement lent, bien sûr, mais ça marche!

Oracle SQL 11.2, 329 octets

WITH q(s,i)AS(SELECT LEVEL s,LEVEL i FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT s,DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE i<>1),v AS(SELECT s,COUNT(*)-1 d FROM q GROUP BY s),m AS(SELECT s,d,MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)m FROM v)SELECT s FROM m WHERE(d>m OR s=1)AND:1>0ORDER BY 1;

Version sans golf

WITH q(s,i) AS 
  (
    SELECT LEVEL s, LEVEL i 
    FROM DUAL CONNECT BY LEVEL <= :1
    UNION ALL 
    SELECT q.s, DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE q.i <> 1
  )
, v AS (SELECT s, COUNT(*)-1 d FROM q GROUP BY s)
, m AS (SELECT s, d, MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) m FROM v)
SELECT * FROM m WHERE (d>m OR s=1) AND :1>0
ORDER BY 1;

La vue q est une véritable vue récursive (pas une requête hiérarchique avec CONNECT BY) qui calcule toutes les étapes vers 1 pour chaque entier compris entre 1 et: 1.

La vue v calcule les distances d'arrêt.

La vue m utilise la version analytique de MAX pour l'appliquer à toutes les lignes précédentes, à l'exclusion de la ligne actuelle. De cette façon, pour chaque entier, nous savons que c'est la distance d'arrêt et la plus grande distance d'arrêt actuelle.

La requête finale vérifie si la distance d'arrêt est supérieure à la plus grande distance d'arrêt. Et ajoute quelques astuces pour gérer 1 et le cas spécial de: 1 ayant une valeur de 0.

MATL , 37 octets

:"@tqX`t0)t2\?3*Q}2/]ht0)q]n]N$htY>=f

Essayez-le en ligne!

:         % vector [1,2,...N], where N is implicit input
"         % for each number in that range
  @       %   push that number, k
  tq      %   truthy iff k is not 1
  X`      %   while...do loop
    t0)   %     pick first number of array
    t2\   %     is it odd?
    ?     %     if so:
      3*Q %       multiply by 3 and add 1
    }     %     else
      2/  %       divide by 2
    ]     %     end if
    h     %     concatenate into array with previous numbers
    t0)q  %     duplicate, pick last number, is it 1? Leave that as while condition
  ]       %   end while
  n       %   number of elements of array. This is the stopping distance for k
]         % end for
N$h       % concatenate all stopping distances into an array
tY>       % duplicate and compute cumulative maximum
=f        % indices of matching elements. Implicitly display

𝔼𝕊𝕄𝕚𝕟, 30 caractères / 38 octets

⩥ïⓜМȬ⧺$,a=[])⋎⟮aꝈ-1⟯>ɐ⅋(ɐ=Ⅰ,ᵖ$

Try it here (Firefox only).

La seule raison pour laquelle je n'ai pas posté cela plus tôt était parce que je n'étais pas clair sur les spécifications. Utilise un encodage personnalisé qui encode les caractères 10 bits.

Explication

⩥ïⓜ crée une gamme [0,input) à cartographier. МȬ⧺$,a=[])génère des nombres Collatz dans un tableau vide et ⋎⟮aꝈ-1⟯>ɐutilise le tableau de nombres Collatz pour obtenir la distance d'arrêt et vérifier si elle est supérieure à la distance d'arrêt maximale précédente. Si c'est le cas, ⅋(ɐ=Ⅰ,ᵖ$fait de la distance d'arrêt actuelle la distance d'arrêt maximale et pousse l'élément actuel dans la plage vers la pile. Après, les éléments de la pile sont imprimés implicitement.

Gelée , 17 octets

×3‘µHḂ?µÐĿL$€<Ṫ$Ạ

Essayez-le en ligne!

Étonnamment, ce ne sont que 3 liens! Ils sont ×3‘µHḂ?µÐĿL$€, <Ṫ$et Ạ.