Primes von Ulams Spirale

17

Ulams Spirale ist ein wirklich faszinierendes und dennoch rätselhaftes Thema in der Mathematik. Wie es im Detail funktioniert, können Sie hier nachlesen , aber eine kurze Zusammenfassung kann so erklärt werden:

Ich schreibe zuerst eine Eins, dann eine Zwei rechts daneben. Über den beiden schreibe ich eine Drei, und links davon schreibe ich vier. Ich setze dieses Muster des Kreisens um 1 (und alle Zahlen zwischen mir und 1) fort und bilde ein spiralförmiges Muster. (siehe Beispiel unten)

Das Ziel

Erstellen Sie ein Programm, das n (immer eine ungerade Zahl größer als Null) als Eingabe akzeptiert , die mit der Anzahl der Zeilen korreliert, und drucken Sie dann die Werte der Primzahlen Zeile für Zeile der Ulam-Spirale aus. Die Formatierung kann beliebig sein, muss jedoch für den Menschen lesbar und offensichtlich sein.

Wenn Sie beispielsweise die Eingabe 3 eingeben, sollte Ihr Programm eine Ausgabe durchführen 5,3,2,7, da 3 Zeilen die folgende Spirale erzeugen:

5 4 3 <-- first row has the primes 5 and 3
6 1 2 <-- second row has the prime 2
7 8 9 <-- third row has the prime 7

Da dies ein Codegolf ist, gewinnt die Antwort mit den wenigsten Bytes (egal wie ineffizient)! Standardlücken sind nicht akzeptabel.

Addison Crump
quelle
Darf ein Komma nachgestellt werden? Oder besser noch, durch Leerzeichen getrennt, zB `` 5 3 2 7```
Tom Carpenter
5
Solange es für Menschen lesbar ist und mir die Primzahlen mitteilen kann, fühlen Sie sich frei.
Addison Crump

Antworten:

8

Pyth, 20 Bytes

f}TPTsuC+R=hZ_GtyQ]]

Probieren Sie es online aus: Demonstration

Dieser Code generiert die vollständige Ulam-Spirale, verbindet alle Linien und Filter für Primzahlen.

Erläuterung:

f}TPTsuC+R=hZ_GtyQ]]   implicit: Z = 0
      u           ]]   reduce, start with G = [[]]
               tyQ     for H in [0, 1, ..., 2*input-2] do:
             _G           reverse the order of the lines
        +R=hZ             append Z + 1 at the end of each line, 
                          updating Z each time with the new value Z + 1
       C                  update G with the transposed of ^
                       this gives the Ulam's spiral
     s                 combine all lines to a big list of numbers
f                      filter for numbers T, which satisfy:
 }TPT                    T appears in the prime-factorization of T
                         (<==> T is prime)
Jakube
quelle
6

MATLAB, 48

a=fliplr(spiral(input(''))');disp(a(isprime(a)))

Grundsätzlich wird eine Spirale der erforderlichen Größe erstellt (vom Benutzer angefordert) und dann so angeordnet, dass sie in der richtigen Zeilenreihenfolge angezeigt wird. Dies ist in einem gespeichert. Als nächstes werden alle Werte in a angezeigt, die Primzahlen sind.

Wie Sie bereits gesagt haben, habe ich ein Byte gespeichert und die Standardausgabe von disp () gewählt, nämlich (in Ihrem Testfall n = 3):

 5
 3
 2
 7

Als zusätzlichen Bonus funktioniert dies für jedes n> 0, einschließlich gerader Zahlen. Die Ausgabe für n = 10 lautet beispielsweise:

97
61
59
37
31
89
67
17
13
 5
 3
29
19
 2
11
53
41
 7
71
23
43
47
83
73
79
Tom Carpenter
quelle
1
Sehr schön! Gut zu wissen, dass die spiralFunktion
Luis Mendo
6

CJam, 42 33 Bytes

Xali(2*{_W%zY@,Y+:Y,>a+}*e_{mp},`

Probieren Sie es online aus

Die neueste Version enthält wesentliche Verbesserungen, die von @Martin vorgeschlagen wurden.

Die Methode zum Aufbau der Spirale besteht darin, in jedem Schritt die bisherige Matrix um 90 Grad zu drehen und eine Zeile mit zusätzlichen Zahlen hinzuzufügen. Dies wird mehrfach wiederholt (n / 2) * 4.

Die Werte in der resultierenden Matrix werden dann als Primzahlen gefiltert.

Erläuterung:

Xa    Push initial matrix [1].
li    Get input and convert to int.
(2*   Calculate 2*(n-1), which is the number of rotations and row additions needed.
{     Start rotation loop.
  _     Copy current matrix for getting number of rows later.
  W%    Reverse the order of the rows...
  z     ... and transpose the matrix. The combination produces a 90 degree rotation.
  Y     Get next value from variable Y (which is default initialized to 2).
  @,    Rotate previous matrix to top, and get number of rows. This is the number
        of columns after the 90 degree rotation, meaning that it's the length of
        the row to be added.
  Y+    Add first value to row length to get end value.
  :Y    Save it in Y. This will be the first value for next added row.
  ,     Create list of values up to end value.
  >     Slice off values up to start value, leaving only the new values to be added.
  a+    Wrap the new row and add it to matrix.
}*    End of rotation loop.
e_    Flatten matrix into list.
{mp}, Filter list for primes.
`     Convert list to string for output.
Reto Koradi
quelle
Könnte 2/4*durch ersetzt werden 2*, oder haben Sie es absichtlich so belassen?
ETHproductions
@ETHproductions Das ist nicht äquivalent, weil es eine Ganzzahldivision ist. Beispiel: Für Eingabe 3 muss das Ergebnis 4 sein. Jetzt, da ich darüber nachdenke, glaube ich, dass ein Byte gespeichert werden muss. (2*sollte richtig sein.
Reto Koradi
5

Mathematica 223

Dies entspricht Kubas Code für eine Ulam-Spirale. Deshalb reiche ich es als Community-Wiki ein. Ich habe nur Golf gespielt und die Primzahlen ausgewählt, die in der Zeile aufgelistet sind, in der sie sich befinden.

r=Range;i=Insert;t=Transpose;s@n_:=#~Select~PrimeQ&/@Nest[With[{d=Length@#,l=#[[-1,-1]]},
Composition[i[#,l+3d+2+r[d+2],-1]&,t@i[t@#,l+2d+1+r[d+1],1]&,i[#,l+d+r[d+1,1,-1],1]&,
t@i[t@#,l+r[d,1,-1],-1] &][#,15]]&,{{1}},(n-1)/2]

Beispiel

 s{15]

{{197, 193, 191}, {139, 137}, {199, 101, 97, 181}, {61, 59, 131}, {103, 37, 31, 89, 179}, {149, 67} 17, 13}, {5, 3, 29}, {151, 19, 2, 11, 53, 127}, {107, 41, 7}, {71, 23}, {109, 43, 47, 83} 173}, {73, 79}, {113}, {157, 163, 167}, {211, 223}}

So verbessern Sie die Anzeige:

 %// MatrixForm

Matrix

DavidC
quelle
4

Mathematica, 118 Bytes

f=Permute[Range[#*#],Accumulate@Take[Join[{#*#+1}/2,Flatten@Table[(-1)^j i,{j,#},{i,{-1,#}},{j}]],#*#]]~Select~PrimeQ&

Dies erzeugt die Ulam-Spirale in linearer Form, indem bemerkt wird, dass die Position jeder nachfolgenden Zahl als akkumuliert werden kann

{(n*n + 1)/2, +1, -n, -1, -1, +n, +n, +1, +1, +1, -n, -n, -n, ...}

dh von der Mitte aus starten, dann 1 nach rechts, 1 nach oben, 2 nach links, 2 nach unten, 3 nach rechts, 3 nach oben, ...

Ausgabe:

In[515]:= f[5]
Out[515]= {17,13,5,3,19,2,11,7,23}

quelle
1

Javascript, 516 363 304 276 243 240 Bytes

Meine Lösung erstellt mit der Spirale keine dichte Matrix, sondern gibt den Index zurück, der der angegebenen Zahl in der Ulam-Matrix der angegebenen Reihenfolge entspricht. Es durchläuft also die Zahlen zwischen 2 und M * M und erzeugt ein Array von Primzahlen mit der durch die fn ulamIdx gegebenen idx

M=15;
$=Math;
_=$.sqrt;
/**
 * Return M*i+j (i.e. lineal or vector idx for the matrix) of the Ulam Matrix for the given integer
 * 
 * Each Segment (there are 4 in each round) contains a line of consecutive integers that wraps the 
 * inner Spiral round. In the foCowing example Segments are: {2,3}, {4,5},
 * {6,7}, {8,9}, {a,b,c,d}, {e,f,g,h}, {i,j,k,l}, {m,n,o,p}  
 *            
 *    h g f e d
 *    i 5 4 3 c
 *    j 6 1 2 b
 *    k 7 8 9 a 
 *    l m n o p
 * 
 * @param n integer The integer which position in the Matrix we want.
 * @param M integer Matrix Order. 
 */
/*
 * m: modulus representing step in segment in current spirtal round
 * v: Step in current spiral round, i.e. n - (inner spirals greatest num.)
 * s: the current Segment one of [1, 2, 3, 4] that represents the current spiral round 
 * L: Segment Length (Current spiral round Order - 1)
 * B: inner Spiral Order, for trib¿vial case 1 it's -1 special case handled differently.
 * C: relative line (row or column) corresponding to n in current spiral Round 
 * R: relative line (column or row) corresponding to n in current spiral Round
 * N: Curren (the one that contains n) Spiral (matrix) round Order
 * D: Difference between M and the current Spiral round order.
 */

/**
 * Runs the loop for every integer between 2 and M*M
 * Does not check sanity for M, that should be odd.
 */
r=[];
for (x = 2; x < M * M; x++) {
    p=1;
    // Is Prime?
    for (k = 2; p&&k <= _(x); k++)
        if (x % k==0) p=0;
    if (p) {
        B = $.floor(_(x - 1));
        B=B&1?B:B-1;
        N = B + 2;
        D = (M - N) / 2;
            v = x - B * B;
            L = B + 1;
            s = $.ceil(v / L);
            m = v % L || L;
            C = D + (s < 3 ? N - m : 1 + m);
            R = s&2 ? D + 1 : D + N;
            w= s&1 ? M * C + R : M * R + C;
        // /*uncomment to debug*/ console.log("X:" + x + ": " + ((s&1) ? [C, R].join() : [R, C].join()));
        r[w] = x;
    }
}
alert(r);

Minimiert sieht so aus:

for(M=15,$=Math,_=$.sqrt,r=[],x=2;x<M*M;x++){for(p=1,k=2;p&&k<=_(x);k++)x%k==0&&(p=0);p&&(B=$.floor(_(x-1)),B=1&B?B:B-1,N=B+2,D=(M-N)/2,v=x-B*B,L=B+1,s=$.ceil(v/L),m=v%L||L,C=D+(s<3?N-m:1+m),R=2&s?D+1:D+N,w=1&s?M*C+R:M*R+C,r[w]=x)}alert(r);

Für Eingang 15 ist der Ausgang:

,,,,,,,,,,,,,,, 197 ,,,, 193, 191 ,,,,,,,,,,,,,,, 139, 137 ,,,,, , 199,, 101 ,,,, 97 ,,,,,,, 181 ,,,,,, 61, 59 ,,, 131 ,,, 103, 37 ,,,,, 31,, 89,, 179,, 149,, 67,, 17 ,,,, 13 ,,,,,,,,,, 5 ,,, 3 ,,, 29 ,,,,, 151 ,,, , 19 ,,, 2,11,, 53,, 127 ,,,, 107, 41,, 7 ,,,,,,,,,,, 71 ,,,, 23 ,,,,,, ,,, 109,, 43 ,,,, 47 ,,,, 83,, 173 ,,,, 73 ,,,,, 79 ,,,,,,,,, 113 ,,,,,,, ,,,,, 157 ,,,,,, 163 ,,,, 167 ,,,, 211 ,,,,,,,,,,, 223

juanmf
quelle
Das war eine ziemliche Komprimierung. Können Sie Ihren ursprünglichen Code und Ihre Änderungen erklären?
Addison Crump
Ich habe ein paar nutzlose Klammern entfernt. Und erkannte, dass uI () 4 Bedingungen mit ähnlichen Blöcken hatte. Mit jeweils 3 Zeilen, die Zeile und Spalte für das aktuelle Segment generiert haben (siehe Hauptdokumentblock), ersetze ich diese 4 Blöcke durch ll & llt-Zeilen, und die Rückgabezeile entscheidet, ob llt Zeile oder Spalte ist. S & 2 ist wahr für s in (3,2) (obere und linke Segmente); s <3, für s in (1,2) rechts und oben. S & 1 bestimmt für s in (1,3), ob die Werte in ll & llt row & col oder col & row sind, und M (Spiralreihenfolge) × row + col verhindert überlappende Indizes (wie bei der Berichtigung einer Matrix, jedoch mit falschem linearen Idx) brauche ll-1
juanmf
In der Hauptschleife (run ()) wird nur dann nach dem Index (ll, llt) in der Spirale gefragt, wenn i eine Primzahl ist (die fn wurde reduziert, da sie nie auf <2 oder% 1 getestet werden musste). Dann drucken Sie einfach das Ergebnis-Array.
Juanmf
Es gibt 3 konzeptionell wichtige Matrizen. Inner, curret & M. Nützlich für die Berechnung der absoluten Zeile & col. Das Subtrahieren von innerem zu n lässt uns mit einem relativen int im Strom (demjenigen, in den n fällt) spiralförmig herum. Und der Unterschied zwischen der M- und der aktuellen Reihenfolge wird in der aktuellen Runde als Offset für Zeile und Spalte gespielt, um absolute Werte zu erhalten.
Juanmf
364 -> 240 durch Inline-Schreiben von fn-Logik und Entfernen nicht verwendeter Tests.
Juanmf