50

Die "Primameise" ist ein hartnäckiges Tier, das durch die ganzen Zahlen navigiert und sie teilt, bis nur noch Primzahlen übrig sind!

Anfangs haben wir ein unendliches Array A, das alle ganzen Zahlen> = 2 enthält: [2,3,4,5,6,.. ]

Sei pdie Position der Ameise auf dem Array. Anfangs p = 0(Array ist 0-indiziert)

In jeder Runde bewegt sich die Ameise wie folgt:

Wenn A[p]es Prim ist, bewegt sich die Ameise zur nächsten Position:p ← p+1
andernfalls, wenn A[p]es sich um eine zusammengesetzte Zahl handelt, sei qihr kleinerer Teiler> 1. Wir teilen A[p]durch qund addieren qzu A[p-1]. Die Ameise bewegt sich zur vorherigen Position:p ← p-1

Hier sind die ersten Züge für die Ameise:

 2  3  4  5  6  7  8  9  ... 
 ^
 2  3  4  5  6  7  8  9  ... 
    ^
 2  3  4  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
    ^
 2  5  2  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
          ^
 2  5  2  5  6  7  8  9  ... 
             ^
 2  5  2  7  3  7  8  9  ... 
          ^

Ihr Programm sollte nach nZügen die Position der Ameise ausgeben . (Sie können davon ausgehen n <= 10000)

Testfälle:

0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512

Bearbeiten. Sie können auch 1-indizierte Listen verwenden. Es ist akzeptabel, die Ergebnisse 1, 7, 10, 275, 513 für den obigen Testfall anzuzeigen.

Das ist Code-Golf, also gewinnt der Code mit dem kürzesten Code in Bytes.

code-golf sequence primes Arnaud
quelle

32

Ehrlich gesagt dachte ich, dass eine Ameise auf meinem Bildschirm war, als ich dies in den Hot Network Questions sah.

Kodos Johnson

14

Ich frage mich, ob die Sequenz für beliebig große gut definiert ist n(oder ob der zusammengesetzte Fall die Ameise jemals nach links von der Initiale schieben könnte 2).

Martin Ender

1

@SuperChafouin also Ausgaben für die Testfälle können sein: 1,7,10,275,513Wird 1-Indizierung angegeben? Oder müssten sie noch mit Ihren Ausgaben übereinstimmen.

Tom Carpenter

12

@MartinEnder Eine andere offene Frage ist, ob eine Primzahl> 7 endgültig zurückgelassen werden kann.

Arnauld

2

@Arnauld Bis zu einer Bewegung von n = 1,000,000,000 (wobei p = 17156661 ist) ist die Beziehung zwischen n und p sehr nahe an p = n / (ln (n) · ln (ln (n)).

Penguino

11

Alice , 45 Bytes

/o
\i@/.&wqh!]k.&[&w;;?c]dt.n$k&;[.?~:![?+!kq

Probieren Sie es online!

Meist unkomplizierte Implementierung.

Die Schleifenzeiten nin Alice werden in der Regel durch Drücken einer Rücksprungadresse n-1und anschließendes Zurückkehren am Ende jeder Iteration mit ausgeführt k. Beim letzten Durchlauf der Schleife kann der kBefehl nicht mehr zurückgegeben werden, und die Ausführung wird fortgesetzt.

Dieses Programm verwendet den gleichen kBefehl, um vorzeitig anzuhalten, wenn die Zahl eine Primzahl ist. Infolgedessen bewegt die letzte Iteration die Ameise immer nach links. Um diesen Fehler zu kompensieren, führen wir n+1Iterationen in einem 1-indizierten Array durch, das genau das gewünschte Ergebnis liefert (und den Fall n=0kostenlos zur Verfügung stellt).

Nitrodon
quelle

7

Python 2 , 120 Bytes

p=0
A=range(2,input()+2)
for _ in A:
 for q in range(2,A[p]):
	if A[p]%q<1:A[p]/=q;p-=1;A[p]+=q;break
 else:p+=1
print p

Probieren Sie es online!

Ah, die selten for- elseSchleife! Die elseKlausel wird nur ausgeführt, wenn der forBody nicht über beendet wird break. In unserem Fall bedeutet dies, dass wir alle qs überprüft haben und keine gefunden haben, die sich teilen p.

Lynn
quelle

7

Oktave , 109 103 101 94 Bytes

function i=a(n)i=1;for l=z=2:n+1
if nnz(q=factor(z(i)))>1
z(i--)/=p=q(1);z(i--)+=p;end
i++;end

Probieren Sie es online!

Dieser Code gibt die Position in 1-Indizierung aus, sodass die Ausgaben für Testfälle wie folgt lauten:

0 => 1
10 => 7
47 => 10
4734 => 275
10000 => 513

Diese Version verwendet einige Octave-Optimierungen und ist daher nicht mit MATLAB kompatibel. Der folgende Code ist eine MATLAB-kompatible Version.

MATLAB, 130 123 118 117 Bytes

function i=a(n)
z=2:n+1;i=1;for l=z
q=factor(z(i));if nnz(q)>1
z(i)=z(i)/q(1);i=i-1;z(i)=z(i)+q(1);else
i=i+1;end
end

Verwendet 1-Indexierung wie bei der Octave-Version. Ich habe es mit allen Testfällen in MATLAB getestet. Als Beispiel ist die Ausgabe bei 100000 3675 (eine Indizierung).

Eine kommentierte Version des obigen Codes:

function i=a(n)
    z=2:n+1;                %Create our field of numbers
    i=1;                    %Start of at index of 1 (MATLAB uses 1-indexing)
    for l=1:n               %For the required number of iterations
        q=factor(z(i));     %Calculate the prime factors of the current element
        if nnz(q)>1         %If there are more than one, then not prime
            z(i)=z(i)/q(1); %So divide current by the minimum
            i=i-1;          %Move back a step
            z(i)=z(i)+q(1); %And add on the minimum to the previous.
        else
            i=i+1;          %Otherwise we move to the next step
        end
    end

Interessanterweise sind dies die Ameisenpositionen im Verhältnis zur Anzahl der Iterationen für die ersten 10000 Werte von n.

Scheint wahrscheinlich, dass die Ameise wahrscheinlich zur Unendlichkeit tendiert, aber wer weiß, das Aussehen kann täuschen.

MATLAB: Gespeichert 6 Bytes mit foranstelle von whileund Entfernen von Klammern aus if- Danke @ Giuseppe
MATLAB: Speichere 2 Bytes - Danke @Sanchises
Octave: Sparen Sie 10 Bytes mit Octave \=und +=Operationen - Danke @Giuseppe
Oktave: Speichere 2 Bytes mit i++und i--- Danke @LuisMendo
Oktave: 7 Bytes sparen - Danke @Sanchises

Tom Carpenter
quelle

Damit es mit TIO endfunktioniert, muss die Funktionssignatur übereinstimmen

Giuseppe,

@ Giuseppe Ah, ok. In MATLAB ist das Nachziehen endoptional.

Tom Carpenter

Sie können anonyme Funktionen

erstellen,

@Michthan kann das in MATLAB nicht. Ich glaube nicht, dass es in Octave möglich ist, da es Loops gibt.

Tom Carpenter

1

Das Trailing endist auch in Octave optional. Hier wird es nur benötigt, weil Sie Code nach der Funktion haben

Luis Mendo

6

JavaScript (ES6), 91 Byte

f=(n,a=[p=0])=>n--?f(n,a,(P=n=>++x<n?n%x?P(n):a[a[p]/=x,--p]+=x:p++)(a[p]=a[p]||p+2,x=1)):p

Demo

NB: Möglicherweise müssen Sie die Standardstapelgröße Ihres Motors erhöhen, um alle Testfälle zu bestehen.

Probieren Sie es online!

Arnauld
quelle

6

Haskell , 108 106 94 Bytes

([0]#[2..]!!)
(a:b)#(p:q)=length b:([b#(a+d:div p d:q)|d<-[2..p-1],mod p d<1]++[(p:a:b)#q])!!0

Probieren Sie es online! Anwendungsbeispiel: ([0]#[2..]!!) 10Renditen 6(0-indiziert).

Die Funktion #arbeitet mit zwei Listen, der umgekehrten Vorderseite des Arrays [p-1, p-2, ..., 1]und dem unendlichen Rest des Arrays [p, p+1, p+2, ...]. Es wird eine unendliche Liste von Positionen erstellt, von denen die nth-Position bei einer Eingabe zurückgegeben wird n.

Das Muster ist ((a:b)#(p:q))an pden Wert der aktuellen Position der Ameise und aan den Wert der vorherigen Position gebunden. bist das Präfix des Arrays von Position 1 bis p-2und qdie unendliche Pause ab Position p+1.

Wir konstruieren eine Liste von rekursiven Aufrufen auf folgende Weise: Wir betrachten jeden Divisor dvon p(der größer als eins und kleiner als p) in aufsteigender Reihenfolge und addieren b#(a+d:div p d:q)für jeden von ihnen, dh der aktuelle Wert pwird durch dividiert dund die Ameise bewegt sich einen Schritt nach links, wo dhinzugefügt wird a. Dann hängen wir (p:a:b)#qan das Ende dieser Liste an, die angibt, dass sich die Ameise einen Schritt nach rechts bewegt.

Wir nehmen dann den ersten dieser rekursiven Aufrufe aus der Liste und stellen die aktuelle Position voran, die mit der Länge der Präfixliste übereinstimmt b. Da die Teiler in aufsteigender Reihenfolge sind, wird durch Auswahl des ersten aus der Liste der rekursiven Aufrufe sichergestellt, dass der kleinste verwendet wird. Da (p:a:b)#qes am Ende der Liste hinzugefügt wird, wird es außerdem nur ausgewählt, wenn es keine Teiler gibt, und pist daher Primzahl.

Bearbeitungen:
-2 Bytes durch Umschalten der Liste der Funktionen von absteigend nach aufsteigend.
-12 Bytes dank Zgarbs Idee, in eine unendliche Liste zu indizieren, anstatt einen Zähler zu behandeln, und durch Umschalten auf 0-Indizierung.

Laikoni
quelle

2

96 Bytes durch Erstellen einer unendlichen Liste und Indizieren, anstatt den Zähler herumzutragen.

Zgarb

1

@ Zgarb Vielen Dank! Beim Umschalten auf 0-Indizierung sind es sogar nur 94 Bytes.

Laikoni

5

TI-BASIC, 108 103 102 98 Bytes

Eingabe und Ausgabe werden in gespeichert Ans. Die Ausgabe ist 1-indiziert.

Ans→N
seq(X,X,2,9³→A
1→P
For(I,1,N
1→X:∟A(P→V
For(F,2,√(V
If X and not(fPart(V/F:Then
DelVar XV/F→∟A(P
P-1→P
F+∟A(P→∟A(P
End
End
P+X→P
End

kamoroso94
quelle

Sie können ein Byte starten von fPart(∟A(P)/F:mit fPart(F¹∟A(P:. Gleiches in der nächsten Zeile.

Scott Milner

@ScottMilner Das funktioniert nicht immer. not(fPart(7⁻¹7ist 0, aber not(fPart(7/7ist 1.

kamoroso94

5

MATL , 41 Bytes

:Q1y"XHyw)Zp?5MQ}1MtYf1)/H(8MyfHq=*+9M]]&

Die Ausgabe ist 1-basiert. Das Programm läuft für den letzten Testfall im Online-Interpreter ab.

Probieren Sie es online!

Erläuterung

Das Programm wendet das in der Challenge beschriebene Verfahren an. Zu diesem Zweck werden die manuellen und automatischen Zwischenablagen von MATL ungewöhnlich häufig verwendet.

Der kleinste Divisor wird als erster Eintrag in der Primfaktorzerlegung erhalten.

Das "Teilen" -Update wird durchgeführt, indem der entsprechende Eintrag von Array A überschrieben wird . Das "Hinzufügen" -Update erfolgt durch elementweises Hinzufügen eines Arrays, das außer an der gewünschten Position Nullen enthält , zu A.

:Q        % Implicitly input n. Push array [2 3 ... n+1]. This is the initial array A. 
          % It contains all required positions. Some values will be overwritten
1         % Push 1. This is the initial value for p
y         % Duplicate from below
"         % For each loop. This executes the following n times.
          %   STACK (contents whosn bottom to top): A, p
  XH      %   Copy p into clipboard H
  y       %   Duplicate from below. STACK: A, p, A
  w       %   Swap. STACK: A, A, p
  )       %   Reference indexing. STACK: A, A[p]
  Zp      %   Isprime. STACK: A, false/true
  ?       %   If true (that is, if A[p] is prime)
    5M    %     Push p from automatic clipboard. STACK: A, p
    Q     %     Add 1. STACK: A, p+1
  }       %   Else (that is, if A[p] is not prime)
    1M    %     Push A[p] from automatic clipboard. STACK: A, A[p]
    t     %     Duplicate. STACK: A, A[p], A[p]
    Yf    %     Prime factors, with repetitions. STACK: A, A[p], prime factors of A[p]
    1)    %     Get first element, d. STACK: A, A[p], d
    /     %     Divide. STACK: A, A[p]/d
    H     %     Push p from clipboard H. STACK: A, A[p]/d, p
    (     %     Assignment indexing: write value. STACK: A with A[p] updated
    8M    %     Push d from automatic clipboard.
    y     %     Duplicate from below. STACK: A with A[p] updated, d, A with A[p] updated
    f     %     Find: push indices of nonzero entries.
          %     STACK: A with A[p] updated, d, [1 2 ... n]
    Hq    %     Push p from clipboard H, subtract 1.
          %     STACK: A with A[p] updated, d, [1 2 ... n], p-1
    =     %     Test for equality, element-wise.
          %     STACK: A with A[p] updated, d, [0 ... 0 1 0 ... 0]
    *     %     Multiply, element-wise. STACK: A with A[p] updated, [0 ... 0 d 0 ... 0]
    +     %     Add, element-wise. STACK: A with A[p-1] and A[p] updated
    9M    %     Push p-1 from automatic clipboard.
          %     STACK: A with A[p-1] and A[p] updated, p-1
  ]       %   End if. The stack contains the updated array and index
]         % End for each. Process the next iteration
&         % Specify that the following implicit display function should display only
          % the top of the stack. Implicitly display

Luis Mendo
quelle

3

Pyth - 44 Bytes

Einfache prozedurale Umsetzung.

K}2hhQVQJ@KZIP_J=hZ).?=GhPJ XKZ/JG=tZ XZKG;Z

Test Suite .

Maltysen
quelle

3

PARI / GP, 87 Bytes

f(n)=A=[2..9^5];p=1;for(i=1,n,q=factor(A[p])[1,1];if(A[p]-q,A[p]/=q;p--;A[p]+=q,p++));p

Ziemlich selbsterklärend (nicht so golfig). Wenn Sie den f(n)=Teil nicht zählen , sind das 82 Byte. Sie können auch mit n->(85 Byte) beginnen.

Es ist eine 1-indizierte Sprache.

Bearbeiten: Die Änderung illustrate(n,m)=A=[2..m+1];p=1;for(i=1,n,for(j=1,m,printf("%5s",if(j==p,Str(">",A[j],"<"),Str(A[j]," "))));print();q=factor(A[p])[1,1];if(A[p]!=q,A[p]/=q;p--;A[p]+=q,p++))druckt eine Illustration des Laufens der Ameise (mit einem ausreichend breiten Terminal). Zum Beispiel illustrate(150,25)werden die ersten 150 Schritte auf 25 Spalten wie folgt angegeben:

  > 2 <3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 3 <4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 3> 4 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 5 <2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 2 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 5 <6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 5> 6 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 7 <3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 3 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 7 <8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3 7> 8 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 9 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 6 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 9 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 5 <3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 3 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 3 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 3 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 3> 4 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 5 <2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 2 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 2> 9 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 5 <3 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 3 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 3> 10 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 5 <5 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 5 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 11 <12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 11> 12 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 13 <6 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 13> 6 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 15 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 8 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 7 <4 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 7> 4 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 9 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 8 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 7 <4 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 7> 4 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 9 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 6 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 5 <3 3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5> 3 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3> 3 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3> 2 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2> 3 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 2 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 5 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 3 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 13 <14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3 13> 14 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 15 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 6 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 7 <3 5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 3 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 5 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 7 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5 7> 15 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 10 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 7 <5 5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 5 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 5 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 5> 16 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 7 <8 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 7> 8 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 9 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 8 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 9 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 6 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 9 <3 3 4 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 5 <3 3 3 4 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5> 3 <3 3 4 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3> 3 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 3 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 3> 4 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 5 <2 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5> 2 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 3 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 3> 4 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 5 <2 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 2 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 17 <18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 17> 18 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 19 <9 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 19> 9 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 22 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 4 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 7 <2 11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 2 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 11 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 3 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 19 <20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3 19> 20 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 21 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 6 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 13 <3 7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 3 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 7 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3 7> 10 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 9 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 6 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 15 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 5 <5 3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 5 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 3 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 3 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 5 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3 5> 21 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 8 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 5 <4 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 5> 4 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 7 <2 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 2 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 7 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2 7> 22 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 9 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 5 <3 11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 3 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 11 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 23 <24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11 23> 24 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 25 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 16 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 5 <8 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 5> 8 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 7 <4 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 7> 4 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 9 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 8 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 9 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 6 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 7 <3 3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7> 3 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 3 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 3> 4 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 5 <2 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5> 2 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2> 3 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 2 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 5 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 5> 12 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 7 <6 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 7> 6 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 9 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 5 <3 3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 3 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 3 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3 3> 25 <26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 8 <5 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 5 <4 5 26

Jeppe Stig Nielsen
quelle

2

Python 2 , 142 127 Bytes

Dank Sherlock9 wurden fünfzehn Bytes gespeichert .

T=range(2,input()+2);p=0
for _ in T:
 m=T[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:T[p-1]/=d;p-=2;T[p]+=d
print p

Probieren Sie es online!

Jonathan Frech
quelle

127 Bytes, wenn Sie nicht verwendenP(n)

Sherlock9

126 Bytes

Felipe Nardi Batista

@FelipeNardiBatista Leider scheint Ihr Vorschlag für Testfälle nicht zu funktionierenn<=4

Sherlock9

2

Mathematica, 118 103 Bytes

(s=Range[2,5^6];t=1;Do[If[PrimeQ@s[[t]],t++,s[[t]]/=(k=#2&@@ Divisors@s[[t]]);s[[t-1]]+=k;t--],#];t-1)&

Probieren Sie es online!

Martin Ender sparte 15 Bytes

J42161217
quelle

Sie hatten ein streunendes Leerzeichen vor sich Divisors, für das Sie die Infixnotation verwenden können Do, und Sie können tstatt t-1(1-basiertes Ergebnis) einfach zurückkehren .

Martin Ender

2

Python 3 , 158 149 133 Bytes

Dies ist eine einfache prozedurale Implementierung mit ein oder zwei Macken, um sicherzustellen, dass der Code für alle Testfälle funktioniert. Ich stelle [*range(2,n+9)]damit sicher, dass A groß genug ist (außer n<3, dass n+9es mehr als genug ist). Die elseKlausel teilt das Alte A[p]durch dDekremente pund fügt ddann das Neue hinzu A[p], was definitiv eine schlechte Codierungspraxis ist. Ansonsten ziemlich unkompliziert. Golfvorschläge willkommen!

Edit: -9 Bytes ohne sympyDank an Halvard Hummel. -14 Bytes von Felipe Nardi Batista, -6 Bytes von einigen Hinweisen aus Jonathan Frechs Python 2-Antwort

p,_,*A=range(int(input())+2)
for _ in A:
 m=A[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:A[p-1]//=d;p-=2;A[p]+=d
print(p)

Probieren Sie es online!

Sherlock9
quelle

145 Bytes

Halvard Hummel

148 Bytes, indem es ein volles Programm

Felipe Nardi Batista

if d-m:A[p]...und else:p+=1um ein Byte zu speichern

Felipe Nardi Batista

143 Bytes durch Entfernen der elseAnweisung

Felipe Nardi Batista

Nach dem Entfernen der elseAnweisung gibt es keinen Unterschied in Bytes zur Funktionsversion

Felipe Nardi Batista

2

PHP, 102 + 1 Bytes

for($a=range(2,$argn);$argn--;$d<$a[+$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[+$p]%++$d;);echo$p;

Laufen Sie als Pipe mit -Roder versuchen Sie es online .

Leere Ausgabe für Eingabe 0; Einfügen +nach echofür ein Literal0

oder verwenden Sie diese 1-indizierte Version (103 + 1 Byte):

for($a=range($p=1,$argn);$argn--;$d<$a[$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[$p]%++$d;);echo$p;

Titus
quelle

2

R , 123 Bytes

Eine unkomplizierte Implementierung. Es wird als eine Funktion bereitgestellt, die die Anzahl der Züge als Eingabe nimmt und die Position p zurückgibt.

Es durchläuft die Sequenz und bewegt den Zeiger gemäß den Regeln vor und zurück. Die Ausgabe ist 0-basiert.

Eine Anmerkung: Um den kleinsten Primfaktor einer Zahl x zu finden, wird der Modul von x relativ zu allen ganzen Zahlen von 0 bis x berechnet. Dann werden die Zahlen mit dem Modul 0 extrahiert, die immer [0,1, ..., x] sind. Wenn die dritte solche Zahl nicht x ist, dann ist es der kleinste Primfaktor von x.

p=function(l){w=0:l;v=w+1;j=1;for(i in w){y=v[j];x=w[!y%%w][3]
if(x%in%c(NA,y))j=j+1
else{v[j]=y/x;j=j-1;v[j]=v[j]+x}}
j-2}

Probieren Sie es online!

NofP
quelle

2

C (GCC), 152 148 Bytes

Minimiert

int f(int n){int*A=malloc(++n*4),p=0,i,q;for(i=0;i<n;i++)A[i]=i+2;for(i=1;i<n;i++){for(q=2;A[p]%q;q++);if(A[p++]>q){A[--p]/=q;A[--p]+=q;}}return p;}

Mit einigen Kommentaren formatiert

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  // Initialize array A
  for (i = 0; i < n; i++)
    A[i] = i + 2;
  // Do n step (remember n was incremented)
  for (i = 1; i < n; i++) {
    // Find smallest divisor
    for (q = 2; A[p] % q; q++)
      ;
    if (A[p++] > q) {
      A[--p] /= q;
      A[--p] += q;
    }
  }
  return p;
}

Hauptfunktion zum Testen

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
  if (argc != 2)
    return 2;
  int n = atoi(argv[1]);
  int p = f(n);
  printf("%d => %d\n", n, p);
  return 0;
}

Zum Anzeigen jedes Schritts

Deklariere display () innerhalb von f ()

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  void display(void) {
    for (int i=0; i < p; i++) {
      printf(" %d", A[i]);
    }
    printf(" \033[1;31m%d\033[m", A[p]);
    if (p+1 < n)
      printf(" %d", A[p+1]);
    printf("\n");
  }
  ...

Anrufanzeige()
```
  A[i] = i + 2;
display();
```
Anrufanzeige()
```
  }
  display();
}
```

user285259
quelle

Sie können einige Bytes abschneiden, indem Sie A als Array deklarieren und Ihre Schleifensteuerelemente vor den Schleifen initialisieren, wo dies möglich ist, oder?

Setzen Sie Monica

1

Clojure, 185 Bytes

#(loop[[n p][(vec(range 2 1e3))0]i %](if(= i 0)p(recur(if-let[q(first(for[i(range 2(n p)):when(=(mod(n p)i)0)]i))][(assoc n p(/(n p)q)(dec p)(+(n(dec p))q))(dec p)][n(inc p)])(dec i))))

Aua, das Bearbeiten eines "Status" ist in Clojure nicht ideal. Sie müssen den Exponenten für größere Eingaben erhöhen.

NikoNyrh
quelle

Warum haben Sie Pattern Matching in der verwendet loop? Sie sollten in der Lage sein, ein paar Bytes ohne das zu verlieren.

Clismique

Möglicherweise können Sie die firstSache auch in eine someAnweisung ändern .

Clismique

Ohne Mustererkennung musste ich recurzweimal wiederholen , eine für jeden if-letZweig. Auch (dec i)würde dupliziert werden. somebraucht ein Prädikat, das ich verwenden könnte, +da wir es mit Zahlen zu tun haben, aber dies ist ein Zeichen länger als first. CMIIW

NikoNyrh

1

Java 8, 138 135 Bytes

n->{int a[]=new int[++n],s=0,p=0,j=0;for(;j<n;a[j++]=j+1);for(;++s<n;p++)for(j=1;++j<a[p];)if(a[p]%j<1){a[p--]/=j;a[p--]+=j;}return p;}

Erläuterung:

Probieren Sie es hier aus.

n->{                     // Method with integer as both parameter and return-type
  int a[]=new int[++n],  //  Integer-array with a length of `n+1`
      s=0,               //  Steps-counter (starting at 0)
      p=0,               //  Current position (starting at 0)
      j=0;               //  Index integer (starting at 0)
  for(;j<n;              //  Loop (1) from 0 to the input (inclusive due to `++n` above)
    a[j++]=j+1           //   And fill the array with 2 through `n+2`
  );                     //  End of loop (1)
  for(;++s<n;            //  Loop (2) `n` amount of steps:
      p++)               //    And after every iteration: increase position `p` by 1
    for(j=1;             //   Reset `j` to 1
        ++j<a[p];)       //   Inner loop (3) from 2 to `a[p]` (the current item)
      if(a[p]%j<1){      //    If the current item is divisible by `j`:
        a[p--]/=j;       //     Divide the current item by `j`
        a[p--]+=j;}      //     And increase the previous item by `j`
                         //     And set position `p` two steps back (with both `p--`)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return p;              //  Return the resulting position `p`
}                        // End of method

Kevin Cruijssen
quelle

1

Clojure, 198 193 191 Bytes

Dies muss stark golfen werden ...

#(loop[i(vec(range 2(+ % 9)))c 0 p 0](if(= % c)p(let[d(dec p)u(i p)f(some(fn[n](if(=(mod u n)0)n))(range 2(inc u)))e(= u f)](recur(if e i(assoc i d(+(i d)f)p(/ u f)))(inc c)(if e(inc p)d)))))

Golf 1 : 5 Bytes durch Ändern (first(filter ...))von gespeichert(some ...)

Golf 2 : 2 Bytes durch Ändern (zero? ...)von gespeichert(= ... 0)

Verwendungszweck:

(#(...) 10000) => 512

Ungolfed-Code:

(defn prime-ant [n]
  (loop [counter 0
         pos 0
         items (vec (range 2 (+ n 9)))]
    (if (= n counter) pos
      (let [cur-item (nth items pos)
            prime-factor
            (some #(if (zero? (mod cur-item %)) %)
              (range 2 (inc cur-item)))
            equals? (= cur-item prime-factor)]
        (recur
          (inc counter)
          (if equals? (inc pos) (dec pos))
          (if equals? items
            (assoc items
              (dec pos) (+ (items (dec pos)) prime-factor)
              pos (/ cur-item prime-factor))))))))

Clismique
quelle

Die Hauptameise 🐜

Antworten:

Alice , 45 Bytes

Python 2 , 120 Bytes

Oktave , 109 103 101 94 Bytes

MATLAB, 130 123 118 117 Bytes

JavaScript (ES6), 91 Byte

Demo

Haskell , 108 106 94 Bytes

TI-BASIC, 108 103 102 98 Bytes

MATL , 41 Bytes

Erläuterung

Pyth - 44 Bytes

PARI / GP, 87 Bytes

Python 2 , 142 127 Bytes

Mathematica, 118 103 Bytes

Python 3 , 158 149 133 Bytes

PHP, 102 + 1 Bytes

R , 123 Bytes

C (GCC), 152 148 Bytes

Minimiert

Mit einigen Kommentaren formatiert

Hauptfunktion zum Testen

Zum Anzeigen jedes Schritts

Clojure, 185 Bytes

Java 8, 138 135 Bytes

Clojure, 198 193 191 Bytes

Verwendungszweck:

Ungolfed-Code: