Berechnung von Collatz Cousins

21

Definieren Sie die Funktion f (n) für eine positive ganze Zahl n wie folgt:

  • n / 2 , wenn n gerade ist
  • 3 * n + 1 , wenn n ungerade ist

Wenn Sie diese Funktion wiederholt auf n größer als 0 anwenden , scheint das Ergebnis immer auf 1 zu konvergieren (obwohl dies noch niemand beweisen konnte). Diese Eigenschaft wird als Collatz-Vermutung bezeichnet .

Definieren Sie die Stoppzeit einer Ganzzahl als die Häufigkeit, mit der Sie die Collatz-Funktion f durchlaufen müssen, bevor sie 1 erreicht. Hier sind die Stoppzeiten der ersten 15 Ganzzahlen:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Nennen wir einen beliebigen Satz von Nummern mit denselben Haltezeiten wie die Cousins ​​von Collatz . Zum Beispiel sind 5 und 32 Cousins ​​von Collatz mit einer Haltezeit von 5.

Ihre Aufgabe: Schreiben Sie ein Programm oder eine Funktion, die eine nicht negative Ganzzahl verwendet und die Menge der Collatz-Cousins ​​generiert, deren Stoppzeit dieser Ganzzahl entspricht.

Eingang

Eine nichtnegative Ganzzahl S, angegeben über STDIN, ARGV oder Funktionsargument.

Ausgabe

Eine Liste aller Zahlen , deren Stoppzeit ist S, sortiert in aufsteigender Reihenfolge. Die Liste kann von Ihrem Programm ausgegeben oder von Ihrer Funktion zurückgegeben oder ausgegeben werden. Das Ausgabeformat ist flexibel: Durch Leerzeichen oder Zeilenumbrüche getrennt oder jedes Standard-Listenformat Ihrer Sprache ist in Ordnung, solange die Zahlen leicht voneinander zu unterscheiden sind.

Bedarf

Ihre Einreichung muss für S ≤ 30 korrekte Ergebnisse liefern. Sie sollte in Sekunden oder Minuten und nicht in Stunden oder Tagen abgeschlossen sein.

Beispiele

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Hier ist eine Zusammenfassung der Ausgabe für S = 30 .

Das ist : Das kürzeste Programm in Bytes gewinnt. Viel Glück!

DLosc
quelle
Was ist mit Zyklen? Ich habe keine Erwähnung von Zyklusvermeidung gesehen. Denn für S = 5 gibt es 3 Werte [4, 5, 32], weil Sie "1 - 2 - 4 - 1 - 2 - 4"
JPMC
1
@JPMC Die Vermeidung von Zyklen wird durch die Definition der Stoppzeit impliziert. Die Stoppzeit von 4 ist 2, nicht 5, da 2 "die Anzahl der Durchgänge durch die Collatz-Funktion ist, bevor 1 erreicht wird".
DLosc
Ah, vergib mir. Ich dachte, dass eine Zahl mehrere Stoppzeiten haben könnte, da mehrere Pfade zu ihr führen können. Aber das war in Bezug auf den Aufbau von 1, nicht von N. Sorry darüber.
JPMC
1
@ DLosc Pyth natürlich.
isaacg
1
Verwandte, aber nicht golfen: math.stackexchange.com/q/470782/20792 und math.stackexchange.com/q/1243841/20792
Pureferret

Antworten:

7

Pyth, 26 24 21 Bytes

Su+yMG-/R3fq4%T6G1Q]1

Dieser Code läuft sofort für S=30. Probieren Sie es aus: Demonstration

Vielen Dank an @isaacg für das Speichern von 5 Bytes.

Erläuterung

Mein Code beginnt mit 1und macht die Collatz-Funktion rückgängig. Es ordnet alle Nummern ddes S-1Schritts 2*dund zu (d-1)/3. Der letzte ist jedoch nicht immer gültig.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print
Jakube
quelle
Das ist eine schöne Verwendung von -F.
isaacg
1
Wenn Sie - ... 1die Summe innerhalb des Reduzierers umrunden, muss der Reduzierer .uweder ein noch das -FÄußere sein. Speichert 2 Zeichen.
isaacg
@isaacg Danke. Ich hatte dies tatsächlich in einer früheren Version, entfernte es aber während des Debuggens eines Fehlers.
Jakube
3
Ich habe @ isaacg's für meine eigene Antwort ausgeliehen. Ich habe stundenlang versucht, den kürzesten Code zum Entfernen von Duplikaten zu finden, aber dies ist bei weitem die eleganteste Lösung. Außerdem mag ich die Verwendung eines Tupels, um ungültige Quotienten zu verwerfen, sehr. Leider hat CJam keine Tupel, aber ich habe es geschafft, ungültige Quotienten auf 1 abzubilden.
Dennis
@Jakube q4%d6entspricht !%hhd6, aber 1 Zeichen kürzer.
isaacg
8

Mathematica, 98 92 89 Bytes

Diese Lösung löst S = 30sofort:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

Dies ist eine unbenannte Funktion, die Sals einzigen Parameter eine Liste der Cousins ​​von Collatz zurückgibt.

Der Algorithmus ist eine einfache Breitensuche. Die Collatz-Cousins ​​für eine bestimmte SZahl sind alle Ganzzahlen, die von den Collatz-Cousins ​​für eine S-1Via 2*noder ungerade Zahlen, die über eine Via erreicht werden können, erreicht werden können (n-1)/3. Wir müssen auch sicherstellen, dass wir nur die Ganzzahlen produzieren, die zum ersten Mal nach SSchritten erreicht wurden, also behalten wir alle vorherigen Cousins ​​im Auge pund entfernen diese aus dem Ergebnis. Da wir das sowieso tun, können wir ein paar Bytes sparen, indem wir die Schritte aller vorherigen Cousins ​​(nicht nur die von S-1) berechnen , um ein paar Bytes zu sparen (das macht es etwas langsamer, aber nicht merklich für die erforderlichen S).

Hier ist eine etwas besser lesbare Version:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &
Martin Ender
quelle
5

Python 2, 86 83 75 73 71 Bytes

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Rufen Sie gerne an f(30). n = 30ist ziemlich augenblicklich.

(Vielen Dank an @DLosc für die Idee, dass kes sich um eine Zahl statt um eine Liste von Cousins ​​handelt, und ein paar Bytes. Vielen Dank an @isaacg für das Löschen ~-.)

Diese Variante ist viel kürzer, dauert aber aufgrund der exponentiellen Verzweigung leider zu lange:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
Sp3000
quelle
Interessant - meine ursprüngliche Lösung ist sehr ähnlich, aber (ein paar Optimierungen von Ihnen nehmen) kommt aus 2 Bytes kürzer: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. Es ist weniger effizient mit den Funktionsaufrufen, tut es aber n = 30in weniger als einer Sekunde.
DLosc
1
@ DLosc Ich mochte Ihre Idee und machte es besser :)
Sp3000
Nett! Hier sind noch 2 Bytes f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
übrig
@ DLosc Ahaha danke. Ich schwöre immer noch, dass es einen besseren Kurzschluss geben muss ...
Sp3000
Ich denke, das ~-ist unnötig, weil Sie die Ganzzahldivision verwenden.
isaacg
5

CJam, 29 26 Bytes

Xari{{2*_Cmd8=*2*)}%1-}*$p

Dank geht an @isaacg für seine Idee, Einsen nach jeder Iteration zu entfernen, wodurch mir zwei Bytes direkt und ein weiteres indirekt erspart wurden.

Probieren Sie es online im CJam-Interpreter aus (sollte in weniger als einer Sekunde beendet sein).

Wie es funktioniert

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
Dennis
quelle
4

CJam, 35 Bytes

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Erklärung folgt in Kürze. Dies ist eine viel schnellere Version als der "ziemlich direkte" Ansatz (siehe im Bearbeitungsverlauf).

Probieren Sie es hier online aus, N = 30was in Sekundenschnelle in der Online-Version und sofort im Java Compiler ausgeführt wird

Optimierer
quelle
Wie lange dauert dies für die größeren Eingaben? It should finish in seconds or minutes, not hours or days.
DLosc
Ah ich sehe. Die von mir geschriebene Python-Version
brauchte
Die neueste Version läuft fast sofort.
Optimierer
6
Ihr Code enthält einen Fehler. Der Testfall S=15funktioniert nicht.
Jakube
3

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Bei x30 dauert das Programm 15 Minuten und 29 Sekunden.

Erweitert

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}
Ypnypn
quelle
Nur neugierig, wie lange dauert das für S = 30?
Geobits
Dies funktioniert nur in Java 8, richtig? Unter javac 1.7.0_79Ubuntu gab es viele Syntaxfehler.
DLosc
@ DLosc Correct; Ich werde das in der Post erwähnen.
Ypnypn
Die Beschränkung der Loop-Terminal-Bedingung auf i > 1 && ++n <= x(Sie können auch ablegen n++) scheint für nur 5 weitere Zeichen noch schneller zu sein ... für mich ungefähr 3 Minuten für S = 30. Das wird sicher unter einer Minute rasiert, wenn ich .parallel()auch, aber da dies Code-Golf ist ...
HJK
1

Python 2, 118 Bytes

Nun, ich dachte mir, dass ich nicht die beste Python-Punktzahl erreichen würde, wenn ich die Lösung von @ Sp3000 gesehen hätte. Aber es sah nach einem lustigen kleinen Problem aus, deshalb wollte ich trotzdem eine unabhängige Lösung ausprobieren:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

Das Gleiche vor dem Entfernen von Leerzeichen:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Dies ist eine sehr direkte Implementierung einer breiten ersten Suche. In jedem Schritt haben wir die Menge mit der Stoppzeit kund leiten die Menge mit der Stoppzeit ab, k + 1indem wir die möglichen Vorgänger für jeden Wert tin der Menge aus Schritt hinzufügen k:

  • 2 * t ist immer ein möglicher Vorgänger.
  • Wenn tgeschrieben werden kann als 3 * u + 1, wo ueine ungerade Zahl ist 1, uist das auch ein Vorgänger.

N = 30Auf meinem MacBook Pro dauert die Ausführung etwa 0,02 Sekunden .

Reto Koradi
quelle
In der Regel s.add(x)ist das beim Golfen unnötig, da man es in der Regel s|={x}stattdessen machen kann. Verwenden Sie ~-xstatt (x+1)spart auch in Klammern. Aber sonst gute Arbeit :)
Sp3000
@ Sp3000 Danke. Ich kann die Sekunde nicht einfach ersetzen, s.add()da sie zu einer Aufgabe wird und nicht mehr Teil des Ausdrucks ist. Es funktioniert für den ersten. Die forauf Zählern basierenden Schleifen sind immer auch ziemlich ausführlich. Ich dachte, ich könnte es mit einer whileSchlaufe verkürzen , aber es stellte sich heraus, dass es genauso lang war.
Reto Koradi
Anstelle einer forSchleife, da Sie die Eingabe nicht auf andere Weise verwenden, können Sie dies wahrscheinlich auch tun exec"..."*input():)
Sp3000
1

PHP 5.4+, 178 Bytes

Die Funktion

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Test & Ausgabe

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) läuft in 0,24 Sekunden * und gibt 732 Elemente zurück. Ein paar sind

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Um Bytes zu sparen, musste ich ksortund array_keysbei jedem Schritt hinzufügen . Die einzige andere Wahl , die ich war , hatte eine kleine Wrapper - Funktion, dass Anrufe c()und dann Anrufe array_keysund ksortauf dem Ergebnis einmal. Da die Zeit aber noch recht knapp ist, habe ich beschlossen, den Performance-Hit für eine niedrige Byteanzahl zu halten. Ohne die richtige Sortierung und Verarbeitung beträgt die Zeit für S (30) durchschnittlich 0,07 Sekunden .

Wenn jemand clevere Möglichkeiten hat, die ordnungsgemäße Verarbeitung nur einmal ohne zu viele zusätzliche Bytes zu erreichen, lassen Sie es mich bitte wissen! (Ich speichere meine Zahlen als Array-Schlüssel, daher die Verwendung von array_keysund ksort)

JPMC
quelle
0

C Sprache

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
windig
quelle
5
Hallo und willkommen bei PPCG! Da dies ein Code-Golf- Wettbewerb ist, sollten Sie Ihren Code so kurz wie möglich halten. Bitte geben Sie auch den Namen der Sprache in Ihrem Beitrag an.
Alex A.
Sie können den {}Knopf drücken, um Ihren Code zu formatieren, was ich für Sie getan habe. Aber wie Alex sagt, füge bitte den Sprachnamen (C?) Hinzu und probiere es mit Golf :) Aber willkommen!
Sp3000,
@ Sp3000 danke für die Hilfe beim Formatieren des Codes
windig
Die Funktion fverhält sich nicht richtig. Mit s=5bekomme ich eine Reihe von falschen Ergebnissen. if (r == s)return true;sollte sein return (r==s), da fnichts Bedeutungsvolles zurückkommt, wenn (r < s). Außerdem glaube ich , Sie erklären sollten iin fso long, da es ziemlich schnell für einige Werte überlaufen wird.
Dennis
@ Dennis Dank :) sollte es seinreturn (r==s);
windig