Zahlen der Reinheit

27

Heute schauen wir uns eine Sequenz a an , die mit der Collatz-Funktion f zusammenhängt :

Bildbeschreibung hier eingeben

Wir nennen eine Folge der Form z, f (z), f (f (z)), ... eine Collatz-Folge .

Die erste Zahl in unserer Sequenz, a (1) , ist 0 . Bei wiederholter Anwendung von f fällt es in einen Zyklus 0 → 0 →…

Die kleinste Zahl, die wir noch nicht gesehen haben, ist 1, was a (2) = 1 ergibt . Bei wiederholter Anwendung von f fällt es in einen Zyklus 1 → 4 → 2 → 1 →…

Jetzt haben wir die Zahl 2 im obigen Zyklus gesehen, also ist die nächstkleinere Zahl a (3) = 3 und fällt in den Zyklus 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 →…

In allen obigen Zyklen haben wir bereits 4 und 5 gesehen , die nächste Zahl ist also a (4) = 6 .

Inzwischen sollten Sie auf die Idee kommen. a (n) ist die kleinste Zahl, die nicht Teil einer Collatz-Sequenz für alle a (1),…, a (n - 1) war .

Schreiben Sie ein Programm oder eine Funktion, die bei einer positiven Ganzzahl n a (n) zurückgibt . Kürzester Code in Bytes gewinnt.


Testfälle:

1  -> 0
2  -> 1
3  -> 3
4  -> 6
5  -> 7
6  -> 9
7  -> 12
8  -> 15
9  -> 18
10 -> 19
50 -> 114

(Dies ist die OEIS-Sequenz A061641 .)

orlp
quelle
1
Obligatorische OEIS
FryAmTheEggman
3
Kann die Eingabe n0-basiert sein?
Luis Mendo
a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2
Karl Napf
@ LuisMendo Sorry, ich habe deine Nachricht irgendwie verpasst. Nein, reproduzieren Sie die genaue Reihenfolge wie bei der Challenge.
Orlp
Wenn anicht 0-basiert Ich verstehe nicht, warum Sie hier zu "sprechen 0-basiert" scheinen:a(n) is the smallest number that was not part of any Collatz sequences for all a(0), …, a(n − 1).
Daniero

Antworten:

5

Jelly , 20 bis 19 Bytes

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ
Ç¡Ṫ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Ç¡Ṫ              Main link. No explicit arguments. Default argument: 0
 ¡               Read an integer n from STDIN and do the following n times.
Ç                  Call the helper link.
  Ṫ              Tail; extract the last element of the resulting array.


ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ  Helper link. Argument: A (array)

  J              Yield all 1-based indices of A, i.e., [1, ..., len(A)]. Since 0
                 belongs to A, there is at least one index that does belong to A.
ḟ@               Filter-false swapped; remove all indices that belong to A.
   Ḣ             Head; extract the first index (i) that hasn't been removed.
           ÐĿ    Call the quicklink to the left on i, then until the results are no
                 longer unique. Collect all unique results in an array.
         Ḃ?      If the last bit of the return value (r) is 1:
       $           Apply the monadic 3-link chain to the left to r.
    ×3‘              Yield 3r + 1.
        H        Else, halve r.
              Ṛ  Yield A, reversed.
             ;   Concatenate the results array with reversed A.

Nach n Iterationen steht der Wert von a (n + 1) am Anfang des Arrays. Da wir das neue Array mit einer umgekehrten Kopie des alten verketten, bedeutet dies, dass a (n) am Ende steht.

Dennis
quelle
9

Haskell, 93 92 Bytes

c x|x<2=[[0,2]!!x]|odd x=x:c(3*x+1)|1<2=x:c(div x 2)
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!)

Anwendungsbeispiel: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10-> 19.

c xist der Collatz-Zyklus für xmit ein bisschen Schummeln für x == 1. Die Hauptfunktionen durchlaufen alle ganzen Zahlen und halten diejenigen, die nicht in c xfür xin [0..y-1]. Ziemlich direkte Umsetzung der Definition. Da der Haskell-Indexoperator auf !!0 basiert, beginne ich mit -1dem Voranstellen einer (ansonsten nutzlosen) Zahl, um den Index zu reparieren.

nimi
quelle
4

MATL , 46 40 Bytes

Oiq:"tX>Q:yX-X<`t0)to?3*Q}2/]h5M1>]Pv]0)

Probieren Sie es online!

Erläuterung

Der Code hat eine äußere forSchleife, die nCollatz-Sequenzen erzeugt , eine in jeder Iteration. Jede Sequenz wird von einer inneren do...whileSchleife generiert , die neue Werte berechnet und in einem Sequenzvektor speichert, bis ein 1oder 0erhalten wird. Wenn wir mit der Sequenz fertig sind, wird der Vektor umgekehrt und zu einem globalen Vektor verkettet , der die Werte aller vorherigen Sequenzen enthält. Dieser Vektor kann wiederholte Werte enthalten. Die Umkehrung des Sequenzvektors stellt sicher, dass am Ende der äußeren Schleife das gewünschte Ergebnis (der Startwert der letzten Sequenz) am Ende des globalen Vektors liegt.

Pseudocode :

1  Initiallization
2  Generate n sequences (for loop):
3    Compute initial value for the k-th sequence
4    Generate the k-th sequence (do...while loop)
5      Starting from latest value so far, apply the Collatz algorithm to get next value
6      Update sequence with new value 
7      Check if we are done. If so, exit loop. We have the k-th sequence
8    Update vector of seen values
9  We now have the n sequences. Get final result

Kommentierter Code :

O           % Push 0                                                          1
iq:         % Input n. Generate [1 2 ... n-1]                                 ·
"           % For loop: repeat n-1 times. Let k denote each iteration         2
  t         %   Duplicate vector of all seen values                           · 3
  X>Q       %   Take maximum, add 1                                           · ·
  :         %   Range from 1 to that: these are potential initial values      · ·
  y         %   Duplicate vector of all seen values                           · ·
  X-X<      %   Set difference, minimum: first value not seen                 · ·
  `         %   Do...while: this generates the k-th Collatz sequence          · 4
    t0)     %     Duplicate, push last value of the sequence so far           · · 5
    to      %     Duplicate, parity: 1 if odd, 0 if even                      · · ·
    ?       %     If odd                                                      · · ·
      3*Q   %       Times 3, plus 1                                           · · ·
    }       %     Else                                                        · · ·
      2/    %       Half                                                      · · ·
    ]       %     End if                                                      · · ·
    h       %     Concatenate new value of the sequence                       · · 6
    5M      %     Push the new value again                                    · · 7
    1>      %     Does it exceed 1? This is the loop condition                · · ·
  ]         %   End do...while. The loops ends when we have reached 0 or 1    · ·
  P         %   Reverse the k-th Collatz sequence                             · 8
  v         %   Concatenate with vector of previously seen values             · ·
]           % End for                                                         ·
0)          % Take last value. Implicitly display.                            9
Luis Mendo
quelle
3

Brachylog , 70 67 65 63 62 Bytes

,[]:?:1ih.
,0<=X=,?'eXg{t{:2/.*?|:3*+.}gB,(?.sB;?:Bc:2&.)}:?c.

Probieren Sie es online!

Undichte Nonne
quelle
3

Python 2, 97 96 Bytes

r,=s={-1}
exec'n=r=min({r+1,r+2,r+3}-s)\nwhile{n}-s:s|={n};n=(n/2,3*n+1)[n%2]\n'*input()
print r

Nutzt die Tatsache aus, dass alle Vielfachen von 3 rein sind. Teste es auf Ideone .

Wie es funktioniert

In der ersten Zeile r,=s={-1}setzen Sie s = {-1} (set) und r = -1 .

Als nächstes lesen wir eine Ganzzahl aus STDIN, wiederholen einen bestimmten String so oft wie möglich und führen ihn dann aus. Dies entspricht dem folgenden Python-Code.

for _ in range(input())
    n=r=min({r+1,r+2,r+3}-s)
    while{n}-s:
        s|={n}
        n=(n/2,3*n+1)[n%2]

In jeder Iteration beginnen wir damit, das kleinste Mitglied von {r + 1, r + 2, r + 3} zu finden , das nicht zu s gehört . In der ersten Iteration initialisiert dies r als 0 .

In allen nachfolgenden Läufen kann (und wird) s einige von r + 1 , r + 2 und r + 3 enthalten , jedoch niemals alle, da alle Vielfachen von 3 rein sind. Beachten Sie zur Überprüfung dieser Aussage, dass kein Vielfaches m von 3 die Form 3k + 1 hat . Somit verbleiben 2 m als einzig mögliches Vorbild, was ebenfalls ein Vielfaches von 3 ist . Daher kann m in der Collatz-Folge nicht mit einer Zahl vorkommen, die kleiner als m ist , und ist daher rein.

Nachdem wir r identifiziert und n initialisiert haben , wenden wir die Collatz-Funktion mit an n=(n/2,3*n+1)[n%2]und addieren jeden Zwischenwert von n zu der Menge s mit s|={n}. Sobald wir auf eine Zahl n stoßen , die bereits in s enthalten ist , erhalten wir {n}-seine leere Menge, und die Iteration stoppt.

Der letzte Wert von r ist das gewünschte Element der Sequenz.

Dennis
quelle
1
Hinzu kommt der Beweis, dass alle Vielfachen von 3 rein sind. Betrachten Sie eine beliebige Collatz-Sequenz modulo 3. Nach jeder Anwendung der 3x + 1-Regel ist das Modulo 1. Nach der Anwendung der x / 2-Regel wird mod 1 zu 2 und mod 2 zu 1. Keine der beiden Regeln kann ein Vielfaches erzeugen von 3, es sei denn, der Startwert war bereits ein größeres Vielfaches von 3, das halbiert wurde. Aber das sind größere Werte, die noch nicht generiert wurden, also ist n = 0 (mod 3) => n rein.
Orlp
1

Pyth , 32 Bytes

VtQ=+Y.u?%N2h*3N/N2Z)=Zf!}TYhZ)Z

Testsuite.

Undichte Nonne
quelle
1

Java, 148 Bytes

int a(int n){if(n<2)return 0;int f=a(n-1),b,i,c;do{f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}while(b<1);return f;}

Ideone es! (Warnung: Exponentielle Komplexität durch Nulloptimierung.)

Das Umwandeln von einer do...whileSchleife in eine forSchleife wäre golfer, aber ich habe Probleme damit.

Golftipps sind wie gewohnt willkommen.

Undichte Nonne
quelle
Nicht viel, aber Sie können Golf 1 Byte aus , indem Sie for(b=1,i=1;i<n;i++)auf for(b=1,i=0;++i<n;). Übrigens, ich verstehe, warum Ihrer Ideone der Testfall für 50 fehlt, aber warum fehlen auch die 10? Es kann problemlos damit umgehen.
Kevin Cruijssen
@ KevinCruijssen Da wäre die Formatierung schlecht.
Undichte Nonne
Nicht die beste Verbesserung, aber ich habe nicht zu viel Zeit damit verbracht ... (147 Bytes)int a(int n){if(n<2)return 0;int f=a(n-1),b=0,i,c;for(;b<1;){f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}return f;}
Poke
1

Perl6, 96

my @s;my $a=0;map {while ($a=@s[$a]=$a%2??3*$a+1!!$a/2)>1 {};while @s[++$a] {}},2..slurp;$a.say;

Basierend auf der Perl 5-Antwort . Etwas länger, da die Perl6-Syntax weniger verzeihend ist als die Perl5-Syntax, aber damit werde ich mich vorerst abfinden.

bb94
quelle
0

PHP, 233 124 Bytes

<?$n=$argv[1];for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}echo$v;

+4 für Funktion:

function a($n){for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}return$v;}
Titus
quelle
0

Perl 5 - 74 Bytes

map{0 while 1<($a=$c[$a]=$a%2?$a*3+1:$a/2);0 while$c[++$a]}2..<>;print$a+0

Dies ist eine ziemlich einfache Lösung. Die Collatz-Funktion wird wiederholt auf die Variable angewendet $aund im Array gespeichert, @cdass der Wert gesehen wurde. Nach Erreichen von 0 oder 1 wird inkrementiert, $abis es sich um eine Zahl handelt, die noch nicht gesehen wurde. Dies wird eine Anzahl von Malen wiederholt, die der Eingabe minus 2 entsprechen, und schließlich wird der Wert von $aausgegeben.

faubi
quelle
0

Mathematica, 134 Bytes

f=If[EvenQ@#,#/2,3#+1]&;a@n_:=(b={i=c=0};While[i++<n-1,c=First[Range@Max[#+1]~Complement~#&@b];b=b~Union~NestWhileList[f,c,f@#>c&]];c)

Einfacher zu lesendes Format:

f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
  b = {i = c = 0};                                   initializations
                                                       b is the growing sequence
                                                       of cycles already completed
  While[i++ < n - 1,                                 computes a(n) recursively
    c = First[Range@Max[# + 1]~Complement~# & @b];   smallest number not in b
    b = b~Union~NestWhileList[f, c, f@# > c &]       apply f to c repeatedly
                                                       until the answer is smaller
                                                       than c, then add this new
                                                       cycle to b
    ]
  ; c)                                                 output final value of c
Greg Martin
quelle