In der Collatz-Sequenz (auch als 3x + 1-Problem bezeichnet) beginnen Sie mit einer beliebigen positiven Ganzzahl. In diesem Beispiel verwenden wir 10 und wenden diese Schritte darauf an:

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

10 ist gerade, also dividieren wir durch 2, um 5 zu erhalten. 5 ist ungerade, also multiplizieren wir mit 3 und addieren 1, um 16 zu erhalten. 16 ist gerade, also halbieren Sie es, um 8 zu erhalten. Die Hälfte von 8 ist 4, die Hälfte von 4 ist 2 und die Hälfte von 2 ist 1. Da dies 6 Schritte dauerte, sagen wir, dass 10 einen Bremsweg von 6 hat.

Eine Super-Collatz-Zahl ist eine Zahl, deren Bremsweg größer ist als der Bremsweg jeder kleineren Zahl. Beispielsweise ist 6 eine Super-Collatz-Zahl, da 6 einen Bremsweg von 8 hat, 5 einen Bremsweg von 5 hat, 4 2 hat, 3 7 hat, 2 1 hat und 1 0 hat. ( A006877 im OEIS) Sie müssen Nimm eine Zahl n als Eingabe und gib alle Super Collatz-Zahlen bis n aus .

Regeln

• Volles Programm oder Funktion ist annehmbar.

• Sie können die Super Collatz-Sequenz nicht vorberechnen oder hart codieren.

• Sie können Eingaben in jedem vernünftigen Format vornehmen.

• Die Ausgabe kann als Liste von der Funktion zurückgegeben oder in STDOUT oder eine Datei gedruckt werden. Was auch immer am bequemsten ist.

• Ungültige Eingaben (Nichtzahlen, Dezimalzahlen, negative Zahlen usw.) führen zu undefiniertem Verhalten.

Probieren Sie ungolfed Python

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

Beispiel IO:

#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

Auch hier sind die ersten 44 Super Collatz-Nummern:

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 Bytes

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

Demonstration

Dies funktioniert, indem das Maximum des Bereichs bis zu jeder Zahl anhand ihres Collatz-Bremswegs ermittelt und überprüft wird, ob dieses Maximum die fragliche Zahl ist.

Python 2, 104 Bytes

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)))]

cist eine Hilfsfunktion, die den Collatz-Abstand für eine bestimmte Ganzzahl berechnet. Das unbenannte Lambda ist die Hauptfunktion, die die Super-Collatz-Zahlen bis zur Eingabe berechnet (aber nicht mit einbezieht).

Dyalog APL , 41 Bytes

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

Eine unbenannte Funktion. Name oder Klammer, um sich zu bewerben.

Testfälle:

       ((∪⊢⍳⌈\)≢∘{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 führt zu undefiniertem Verhalten.

ES6, 86 83 Bytes

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])

Bearbeiten: 3 Bytes durch Umschalten filterauf ein Array-Verständnis gespeichert .

Haskell, 84 Bytes

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]]

Das ist natürlich massiv langsam, aber es funktioniert!

Oracle SQL 11.2, 329 Byte

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;

Golflose Version

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;

Die q-Ansicht ist eine echte rekursive Ansicht (keine hierarchische Abfrage mit CONNECT BY), die für jede ganze Zahl zwischen 1 und: 1 alle Schritte in Richtung 1 berechnet.

Die v-Ansicht berechnet die Bremswege.

In der Ansicht m wird die analytische Version von MAX verwendet, um sie auf alle vorhergehenden Zeilen anzuwenden, mit Ausnahme der aktuellen Zeile. Auf diese Weise wissen wir, dass es sich bei jeder Ganzzahl um den Bremsweg und den aktuell größten Bremsweg handelt.

Die letzte Abfrage prüft, ob der Bremsweg größer ist als der größte Bremsweg. Und fügt ein paar Tricks hinzu, um mit 1 und dem Sonderfall 1 mit dem Wert 0 umzugehen.

MATL , 37 Bytes

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

Probieren Sie es online!

:         % 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 Zeichen / 38 Byte

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

Try it here (Firefox only).

Der einzige Grund, warum ich dies nicht früher gepostet habe, war, dass mir die Spezifikationen nicht klar waren. Verwendet eine benutzerdefinierte Codierung, die 10-Bit-Zeichen codiert.

Erläuterung

⩥ïⓜErstellt einen Bereich [0,input), über den eine Karte erstellt werden soll. МȬ⧺$,a=[])generiert Collatz-Zahlen in einem leeren Array und ⋎⟮aꝈ-1⟯>ɐverwendet das Array von Collatz-Zahlen, um den Bremsweg abzurufen und zu überprüfen, ob dieser größer als der vorherige maximale Bremsweg ist. In diesem Fall ⅋(ɐ=Ⅰ,ᵖ$wird der aktuelle Bremsweg zum maximalen Bremsweg und der aktuelle Gegenstand im Bereich zum Stapel verschoben. Danach werden die Elemente des Stapels implizit gedruckt.

Gelee , 17 Bytes

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

Probieren Sie es online!

Vielleicht überraschend, das sind nur 3 Links! Sie sind ×3‘µHḂ?µÐĿL$€, <Ṫ$und Ạ.