Rekursive Collatz-Vermutung

21

Die Collatz-Vermutung geht davon aus , dass Sie den folgenden Algorithmus genügend oft wiederholen sollten, wenn Sie eine positive ganze Zahl verwenden:

if number is odd, then multiply by three and add one
if number is even, then divide by two

Sie werden schließlich bei 1 enden. Es scheint immer zu funktionieren, aber es ist nie bewiesen worden, dass es immer funktioniert.

Sie haben bereits damit gerechnet, wie lange es dauert, bis 1 erreicht ist , und ich dachte, ich würde die Dinge ein wenig auf den Kopf stellen .

Berechnen Sie ausgehend von einer bestimmten positiven Ganzzahl, wie lange es dauert, bis 1 erreicht ist (die "Stoppzeit"). Finden Sie dann die Stoppzeit dieser Zahl.

Wiederholen Sie diesen Vorgang, bis Sie 1 erreichen oder bis Sie das völlig willkürliche Limit von 100 Iterationen erreichen. Geben Sie im ersten Fall an, wie viele Iterationen erforderlich waren. In letzterem Fall geben Sie "Fail" oder eine andere konsistente Ausgabe Ihrer Wahl aus, sofern es sich nicht um eine Ganzzahl handelt 1≤n≤100. Sie können für diese Option keine leere Zeichenfolge ausgeben. Die Ausgabe einer Ganzzahl außerhalb des Bereichs [1, 100] ist jedoch zulässig.

Beispiele:

Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6

Da ich eine Sprache berechnet 10^100und 12345678901234567890verwendet habe, die nur Real für diese Größe unterstützt, erhalten Sie bei genauerer Sprache möglicherweise unterschiedliche Ergebnisse für diese.

Wertung

Da es sich um , die Antwort mit der kürzesten Menge von Bytes gewinnt.

DonielF
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Cole

Antworten:

9

Python 2 , 70 Bytes

f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)

Gibt 199 für hundert oder mehr Iterationen zurück.

Probieren Sie es online!

Dennis
quelle
6

Attache , 40 Bytes

`-&3@`#@PeriodicSteps[CollatzSize@Max&1]

Probieren Sie es online!

Dies ist eine neue Sprache, die ich gemacht habe. Ich wollte herumkommen, um eine richtige Infix-Sprache zu erstellen, und das ist das Ergebnis: ein Mathematica-Knock-off. Hurra?

Erläuterung

Dies ist eine Zusammenstellung einiger Funktionen. Diese Funktionen sind:

  • PeriodicSteps[CollatzSize@Max&1]Dies ergibt eine Funktion, die ihr Argument anwendet, bis die Ergebnisse ein doppeltes Element enthalten. Diese Funktion CollatzSize@Max&1gilt CollatzSizefür die größere der Eingaben und 1, um ungültige Eingaben 0in CollatSize zu vermeiden.
  • `#ist ein börsennotierter Betreiber; in diesem Sinne monadisch angewandt, erhält es die Größe seines Arguments
  • `-&3ist eine gebundene Funktion, die das Argument 3an die Funktion bindet `-, die "minus 3" lautet. Dies liegt daran, dass die PeriodicSteps-Anwendung 0s ergibt , die berücksichtigt werden müssen. (Es handhabt auch ordentlich out-of-bounds Zahlen wie 5, denen zuordnen -1.)
Conor O'Brien
quelle
1
Ist die Verwendung Ihrer eigenen Sprache wirklich erlaubt? Kannst du nicht einfach eine Sprache für jeden Codegolf erstellen, der nur einige Bytes verwendet?
Tweakimp
2
@Tweakimp Natürlich ist es erlaubt, eine eigene Sprache zu erstellen (und zu verwenden). Es ist jedoch eine Standardlücke, eine Aufgabe so zu ändern, dass sie nur ein einziger Befehl ist (nachdem die Herausforderung veröffentlicht wurde).
Caird Coinheringaahing
2
@Tweakimp Wenn es dich besser fühlen lässt, hatte ich diese Funktion entworfen, bevor ich diese Herausforderung sah. Ich bin ein Sprachdesigner, also mache ich das auch.
Conor O'Brien
Es war eher eine allgemeine Frage, ob selbst erstellte Sprachen erlaubt sind, und keine negative Aussage, dass Sie Ihre eigenen verwendet haben.
Tweakimp
4

J , 49 45 Bytes

-4 Bytes dank kürzerem Collatz Sequence Code aus dem Kommentar von @ randomra hier .

(2-~[:#(>&1*-:+2&|*+:+>:@-:)^:a:)^:(<101)i.1:

Ausgaben 101für ungültige Ergebnisse.

Probieren Sie es online!

Erläuterung

Es überrascht nicht, dass diese Erklärung schnell veraltet ist. Ich lasse es in Bezug auf die alte 49-Byte-Antwort, die ich hatte, die ich unten einschließe. Wenn Sie ein Update wünschen, lassen Sie es mich einfach wissen. Die Art und Weise, wie die Länge der rekursiven Sequenz ermittelt wird, bleibt gleich. Ich habe gerade eine kürzere Collatz-Sequenzmethode verwendet.

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)^:(<101)i.1:

Ermitteln der Länge der Collatz-Sequenz

Dieser Abschnitt des Codes ist der folgende

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)

Hier ist die Erklärung:

(1 -~ [: # %&2`(1+3&*)@.(2&|) ^: (1&<) ^: a:)  Given an input n
                                       ^: a:   Apply until convergence, collecting
                                                each result in an array.
                              ^: (1&<)         If n > 1 do the following, else
                                                return n.
                        (2&|)                  Take n mod 2.
           %&2                                 If n mod 2 == 0, divide by 2.
               (1+3&*)                         If n mod 2 == 1, multiply by 3 
                                                and add 1.
         #                                     Get the length of the resulting
                                                array.
 1 -~                                          Subtract 1.

Leider ^:speichert das Verb apply ( ) beim Speichern von Ergebnissen auch den Anfangswert, was bedeutet, dass wir (wie immer) um eins versetzt sind. Deshalb subtrahieren wir 1.

Ermitteln der Länge der rekursiven Sequenz

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:) ^: (< 101) i. 1:  Given an input n.
                                      ^: (< 101)        Apply 100 times,
                                                         collecting results
                                                         in an array.
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)                   Collatz sequence length.
                                                 i. 1:  Index of first 1 (returns
                                                         101, the length of the
                                                         array if 1 not found).
cole
quelle
1
Wenn es Ihnen nichts ausmacht, den Header-Bereich zu verwenden, wird dies Ihre Antwort möglicherweise genauer wiedergeben
Conor O'Brien,
@ ConorO'Brien Ich weiß überhaupt nicht - ich wusste nicht wirklich, wie ich es als solches formatieren sollte (aber ich werde von nun an deins stehlen). Danke
Cole
1
Und ich bin es!
Conor O'Brien
1
38 Bytes mit *i.~(<101)1&(#@}.a:2&(<*|{%~,*+1+])])]sollten äquivalent sein
Meilen
3

JavaScript (ES6), 57 Byte

Gibt zurück, truewenn es fehlschlägt. Rückgabe 0für 1.

f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

Testfälle

Arnauld
quelle
Ich bin skeptisch, ob Ihr Programm das richtige Ergebnis abgesehen von Überlauf / Ungenauigkeit berechnet oder ob das OP seine Ergebnisse in einer Sprache mit ähnlichen Zahlenimplementierungen ableitet (ich gehe davon aus, dass nicht alle Testfälle von Hand berechnet wurden).
Jonathan Frech
@ JonathanFrech In der Tat. Es stellte sich heraus, dass beide Ergebnisse gleichermaßen ungültig waren.
Arnauld
3

APL (Dyalog Unicode) , 39 60 53 52 49 Bytes

-3 Bytes dank @ngn

0∘{99<⍺:⋄1=⍵:01+(⍺+1)∇{1=⍵:01+∇⊃⍵⌽0 1+.5 3×⍵}⍵}

Probieren Sie es online!

Verwendet @ngn-Code für Collatz, zuvor jedoch @Uriels Code.

Hier ist die alte Version, die der Spezifikation nicht entsprach:

{1=⍵:01+∇{1=⍵:02|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}⍵}
Zacharý
quelle
2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2->1+∇⊃⍵⌽0 1+.5 3×⍵
ngn
2

Perl 6 , 56 Bytes

{($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}

Probieren Sie es online!

Gibt 101für eine nicht terminierende Sequenz zurück.

Sean
quelle
2

Schale , 21 Bytes

←€1↑101¡ȯ←€1¡?½o→*3¦2

Probieren Sie es online! Gibt -1bei Fehlern und 0Eingaben zurück 1.

Erläuterung

←€1↑101¡ȯ←€1¡?½o→*3¦2  Implicit input (a number).
             ?½o→*3¦2  Collatz function:
             ?     ¦2   if divisible by 2,
              ½         then halve,
               o→*3     else multiply by 3 and increment.
        ȯ←€1¡?½o→*3¦2  Count Collatz steps:
            ¡           iterate Collatz function and collect results in infinite list,
          €1            get 1-based index of 1,
        ȯ←              decrement.
       ¡               Iterate this function on input,
   ↑101                take first 101 values (initial value and 100 iterations),
←€1                    get index of 1 and decrement.
Zgarb
quelle
2

C (GCC) , 70 73 Bytes

g(x){x=x-1?g(x%2?3*x+1:x/2)+1:0;}f(x,m){for(m=0;(x=g(x))&&100>m++;);x=m;}

Probieren Sie es online!

Gibt zurück, 101wenn die Anzahl der Iterationen 100 überschreitet.


quelle
1
Willkommen bei PPCG! Diese Antwort ist nicht ganz gültig, da alle Funktionsübermittlungen wiederverwendbar sein müssen . Ich denke, Sie können dieses Problem beheben, indem Sie es m=0in Ihr einfügen f(wahrscheinlich sogar mit dem derzeit leeren forIntiailiser, um einen zu speichern ;).
Martin Ender
2

Sauber , 146 ... 86 Bytes

-11 Bytes dank Ørjan Johansen

import StdEnv
?f l n=hd[u\\1<-iterate f n&u<-l]

?(?(\b|isOdd b=3*b+1=b/2)[0..])[0..99]

Als Teilfunktion wörtlich.

Probieren Sie es online!

Bricht mit ab, hd of []wenn die Anzahl der Iterationen 100 überschreitet.
Beendet mit Heap Fullfür Eingaben über ~, es 2^23sei denn, Sie geben eine größere Heap-Größe an.

Οurous
quelle
1
Ich fange an, einige saubere Syntax (wie es von Haskell unterscheidet) von Ihren Antworten zu verstehen ... Sie können das mit einer Hilfsfunktion verkürzen j f l n=hd[u\\1<-iterate f n&u<-l].
Ørjan Johansen
@ ØrjanJohansen Danke!
Οurous
Du brauchst das \a=...aTeil nicht, es kommt drauf an. (Oder eta reduziert.)
Ørjan Johansen
@ ØrjanJohansen oh, habe das verpasst, danke!
Urous
1

Python 2 , 99 98 97 Bytes

  • Mit c and t or fanstelle von ein Byte gespeichert t if c else f.
  • Ein Byte wurde durch Ausgabe -1anstelle von foder 'f'für nicht unterbrechende Eingaben gespeichert .
exec"f,F="+"lambda n,i=0:n<2and i or %s"*2%("f([n/2,3*n+1][n%2],-~i),","i>99and-1or F(f(n),-~i)")

Probieren Sie es online!

Jonathan Frech
quelle
1

BiwaScheme , 151 Zeichen

(define(f n i s)(if(= s 0) 'F(if(= n 0)i(f(letrec((c(lambda(m k)(if(= m 1)k(c(if(=(mod m 2)0)(/ m 2)(+(* m 3)1))(+ k 1))))))(c n 0))(+ i 1)(- s 1)))))

Sie können es hier ausprobieren .

Andrea Ciceri
quelle
1

R , 119 107 Bytes

Verwendet teilweise den Collatz-Code von Jarko Dubbeldam von hier . Gibt 0für> 100 Iterationen zurück (Fehler).

pryr::f(x,{N=n=0
while(x-1){while(x-1){x=`if`(x%%2,3*x+1,x/2);n=n+1}
x=n
n=0
N=N+1
if(N==100)return(0)}
N})

Probieren Sie es online!

rturnbull
quelle
1

APL NARS, 115 Byte, 63 Zeichen

{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}

Wahrscheinlich mit Schleifen wäre es klarer ... Es gibt 4 Funktionen, 2 verschachtelt und rückwirkend, und die erste nur zum Definieren und Initialisieren von = 0, der Variablen d, gesehen von der 2. Funktion als globaler Variablenzähler.

q←{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}

Diese 3. Funktion wäre die Funktion, die zurückgibt, wie viele Aufrufe es gibt, um die Collatz-Vermutung für ihr Argument aufzulösen

{⍵=1:d⋄99<d+←1:¯1⋄∇q⍵}

Dies ist die 2. Funktion, wenn ihr Argument = 1 ist, stoppen Sie ihre Rekursion und geben Sie d zurück, wie oft sie sich selbst nennt-1; Wenn else selbst mehr als 99 Mal aufgerufen wird, wird die Rekursion gestoppt und -1 (fail) zurückgegeben. else berechnet die Collatz-Vermutung für das Argument und ruft sich selbst für den Längenwert der Collatz-Sequenz auf. Für mich, auch wenn dies alles so aussieht, als würde es ein großes Problem sein, wenn eine globale Variable und eine Variable in einer Funktion mit demselben Namen definiert werden, wenn der Programmierer sie nur als lokale Variable ansieht.

  f←{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}     
  f 2
1
  f 3
5
  f 5
¯1
  f 10
8
  f 100
13
  f 12313
7
  f 1
0
RosLuP
quelle
1

(Emacs, Common, ...) Lisp, 105 Bytes

Gibt t für Iterationen> 100 zurück

(defun f(n k c)(or(> c 100)(if(= n 1)(if(= k 0)c(f k 0(1+ c)))(f(if(oddp
n)(+ n n n 1)(/ n 2))(1+ k)c))))

Erweitert:

(defun f (n k c)
  (or (> c 100)
      (if (= n 1)
          (if (= k 0) c
            (f k 0 (1+ c)))
        (f (if (oddp n) (+ n n n 1) (/ n 2))
           (1+ k) c))))
(f (read) 0 0)
user84207
quelle