Dreieckige Ulam-Spirale

21

Wir haben einen hatten Paar von Herausforderungen über die Ulam Spirale. Aber das reicht nicht.

In dieser Herausforderung zeichnen wir eine dreieckige Ulam-Spirale (im Gegensatz zur üblichen quadratischen Ulam-Spirale). Hier ist eine Skizze, wie die Spirale aussieht.

Bildbeschreibung hier eingeben

Wie wir wissen, ordnet die Ulam-Spirale alle natürlichen Zahlen in einer äußeren Spirale an und markiert nur diejenigen, die Primzahlen sind. In der obigen Skizze werden also nur die Zahlen angezeigt, die in Schwarz (die Primzahlen) erscheinen.

Die Herausforderung

Akzeptieren Sie eine Zahl N als Eingabe und zeigen Sie die dreieckige Ulam-Spirale bis zu dieser Zahl an.

  • Die Eingabe kann stdin oder ein Funktionsargument sein.
  • Die Spirale sollte sich in die positive Richtung drehen (dh gegen den Uhrzeigersinn), wie in der obigen Abbildung.
  • Jede der 120-Grad-Kurven der obigen Abbildung wäre gültig, und die Kurve kann für verschiedene Eingaben unterschiedlich sein. Die unterste Seite der implizierten Dreiecke sollte jedoch horizontal sein, da die einzigen zulässigen Windungen (Vielfache von) 120 Grad sind.
  • Der Code sollte theoretisch (bei genügend Zeit und Speicher) für alle N ausgeführt werden, bis zu dem, was von Zwischenberechnungen, die Sie mit Ihrem Standarddatentyp durchführen, zugelassen wird. doubleist genug; Keine Notwendigkeit für große Integer-Typen.
  • Alle eingebauten Funktionen erlaubt.
  • Ich werde meine eigene Antwort nicht akzeptieren (nicht, dass ich denke, es wäre sowieso die kürzeste ...).

Ausgabeformate

Wählen Sie eine der folgenden Möglichkeiten.

  1. Zeigen Sie ein Diagramm mit einem Marker (Punkt, Kreis, Kreuz, was auch immer Sie bevorzugen) an Primzahlen und nichts an Nicht-Primzahlen an. Der Maßstab muss für beide Achsen nicht identisch sein. Das heißt, die implizierten Dreiecke müssen nicht gleichseitig sein. Achsen, Gitterlinien und Achsenbeschriftungen sind optional. Es werden nur die Marker bei den Primzahlen benötigt.

    Eine Beispielausgabe für N = 12 wäre wie folgt (vergleiche mit der obigen Skizze). Das zweite Diagramm ist ein interessanteres Beispiel, das N = 10000 entspricht.

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

  1. Erstellen Sie eine Bilddatei mit dem oben genannten Format in einem bekannten Bildformat (z. B. png, tiff, bmp).
  2. Zeigen Sie die Spirale als ASCII-Grafik an , wobei Sie ein einzelnes Zeichen Ihrer Wahl für Primzahlen und ein Leerzeichen für Nicht-Primzahlen verwenden und ein Leerzeichen, um die Nummernpositionen in derselben Zeile zu trennen. Führende oder nachfolgende Leerzeichen oder Zeilenumbrüche sind zulässig. Zum Beispiel wäre der Fall N = 12 mit oals Zeichen

                 o
                · ·
               · o ·
                o · ·
               · o · o
    

    Wobei natürlich nur die oMarkierung bei Primzahlen tatsächlich angezeigt würde. Die ·bei Nicht-Primzahlen ist hier nur als Referenz gezeigt.

Gewinnkriterium

Die eigentliche Belohnung ist es, sich selbst von diesen erstaunlichen Mustern zu überzeugen.

Luis Mendo
quelle
2
In Zukunft würde ich empfehlen, nur eine der Optionen [Grafikausgabe] und [ASCII-Kunst] zu wählen, da dies die Vergleichbarkeit der Einsendungen beeinträchtigt. Aber trotzdem nette Herausforderung. :)
Alex A.
@AlexA. Vielen Dank! Ich werde das berücksichtigen. Also ... wird es eine Antwort von Julia geben? ;-)
Luis Mendo
Wow, danke für das Kopfgeld, aber du solltest deine eigene Antwort akzeptieren. Es ist das kürzeste. :)
Martin Ender
Es ist gut verdient! Eine der Herausforderungsregeln für das Akzeptieren einer Antwort lautete "Ich werde meine eigene Antwort nicht akzeptieren". Als ich an diese Herausforderung dachte, dachte ich unweigerlich an MATL mit seinen komplexen Zahlen und grafischen Funktionen, also war es ein bisschen wie Schummeln :-)
Luis Mendo

Antworten:

13

CJam, 49 42 Bytes

Lri{)mp0S?}%{1$,)/(a@Wf%z+\L*}h;eeSff*W%N*

Eingabe als einzelne Ganzzahl in STDIN. Ausgabe als ASCII-Gitter mit 0für Primzahlen. Die Drehung der Spirale ist nicht konsistent: Die größte Anzahl der Spiralen befindet sich immer in der unteren Reihe.

Teste es hier.

Erläuterung

Die Grundidee ist, das Dreieck während der Berechnung als unregelmäßiges 2D-Array darzustellen. Sie erhalten dieses Array, indem Sie die Zeilen umkehren und alle Zeilen nach links ausrichten:

   4
  5 3
 6 1 2
7 8 9 A

Wäre dargestellt als

[[7 8 9 A]
 [6 1 2]
 [5 3]
 [4]]

Da wir die Linie gespiegelt haben, möchten wir die Spirale im Uhrzeigersinn aufrollen . Das ist praktisch, denn wir müssen das Dreieck nur gegen den Uhrzeigersinn drehen und der nächsten Unterliste der Reihe nach voranstellen. Wir können das zerlumpte Array drehen, indem wir alle Zeilen umkehren und transponieren:

                                                           [[B C D E F]
[[7 8 9 A]         [[A 9 8 7]           [[A 2 3 4]          [A 2 3 4]
 [6 1 2]   reverse  [2 1 6]   transpose  [9 1 5]   prepend  [9 1 5]
 [5 3]      ---->   [3 5]      ------>   [8 6]      ---->   [8 6]
 [4]]               [4]]                 [7]]               [7]]

Also hier ist der Code. Ein Detail, auf das ich aufmerksam machen möchte, ist das letzte Bit, das das dreieckige Layout erstellt. Ich denke das ist ziemlich geschickt. :)

L     e# Push an empty array. This will become the spiral.
ri    e# Read input and convert to integer N.
{     e# Map this block over 0 to N-1...
  )   e#   Increment to get 1 to N.
  mp  e#   Test for primality.
  0S? e#   Select 0 or a space correspondingly.
}%
{     e# While the list we just created is not empty yet...
  1$  e#   Copy the spiral so far.
  ,)  e#   Get the number of lines and increment.
  /   e#   Split the list into chunks of that size.
  (a@ e#   Pull off the first chunk, wrap it in an array, pull up the spiral.
  Wf% e#   Reverse the lines of the spiral.
  z   e#   Transpose the spiral.
  +   e#   Prepend the new line.
  \L* e#   Swap with the remaining chunks and join them back together into a single list.
}h
;     e# Discard the empty list that's left on the stack.
ee    e# Enumerate the spiral. This turns each line into a pair of 0-based index
      e# and the line itself.
Sff*  e# Multiply each element of each pair with a space. For the enumeration index i,
      e# this produces a string of i spaces - the required indentation (keeping in
      e# mind that our spiral is still upside down). For the line itself, this
      e# riffles the cells with spaces, creating the required gaps between the cells.
      e# All of this works because we always end the spiral on the bottom edge.
      e# This ensures that the left edge is always complete, so we don't need
      e# different indentation such as in the N=12 example in the challenge.
W%    e# Reverse the lines to make the spiral point upwards.
N*    e# Join the lines with linefeeds.
Martin Ender
quelle
1
Ich wusste, dass du der Erste sein würdest!
Luis Mendo
@ LuisMendo Eigentlich wollte ich dieses überspringen, weil ich dachte, die Berechnung der Gitterindizes wäre mühsam, aber dann wurde mir klar, dass ich einfach das gesamte Dreieck drehen und dabei Linien anhängen könnte.
Martin Ender
1
Ich liebe Ihre Erklärungen zu CJam-Programmen immer, weil ich sie verstehen kann, und ich bin erstaunt, wie komplex und doch kurz diese Programme sein können.
ETHproductions
10

MATL , 48 36 Bytes

:1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG

Verwendet die aktuelle Version (9.3.0) .

Probieren Sie es online! Keine Ahnung, wie der Online-Compiler es schafft, Grafikausgaben in ASCII zu übersetzen, aber es tut Das erzeugt eine ungefähre ASCII-Darstellung dank einer Octave-Funktion , die vom Online-Compiler unterstützt wird!

Bearbeiten (4. April 2016): Die Funktion Y[wurde kseit Release 13.0.0 in umbenannt. Der Link zum Online-Compiler übernimmt diese Änderung, damit der Code getestet werden kann.

Beispiel

>> matl
 > :1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG
 > 
> 20000

erzeugt die grafische Ausgabe (gezeigte MATLAB-Version):

Bildbeschreibung hier eingeben

Erläuterung

Der Code verwendet komplexe Zahlen, um den Pfad zu verfolgen, dem die Spirale folgt. Wie aus der ersten Figur in der Herausforderung ersichtlich ist, ist jedes gerade Bein der Spirale ein Segment mit zunehmender Länge 1, 2, 3, 4 ... und zyklisch zunehmender Ausrichtung von 120 Grad, 240 Grad, 0 Grad, 120 Grad. ..

Der Code generiert zunächst die einzelnen komplexen Verschiebungen von jeder Ganzzahl zur nächsten. Diese komplexen Verschiebungen haben Größenordnung 1 und Winkel 2*pi/3, 4*pi/3oder 0(in Radiant). Somit können sie leicht als imaginäre Exponentiale erzeugt werden. Dazu wird zuerst die Ganzzahlfolge 0,1,2,2,3,3,3,4,4,4 ... verwendet.

Diese Ganzzahl - Sequenz ist fast wie die „n erscheint n - mal“ -Sequenz ( OEIS A002024 ) und kann , wie sie erhalten werden , in floor(sqrt(2*n)+.5)denen nist 0,1,2,3, .... Multipliziert man durch 2j*pi/3, wo jdie imaginäre Einheit ist , erzeugt die gewünschten komplexen Verschiebungen.

Die Verschiebungen werden akkumuliert, um die Positionen zu berechnen, die den ganzzahligen Zahlen in der Spirale entsprechen. Die erste ganze Zahl in der Spirale, die ist 1, befindet sich willkürlich an der Position 1in der komplexen Ebene.

Schließlich werden die Positionen verworfen, die Nicht-Primzahlen entsprechen, und der Rest wird in der komplexen Ebene aufgetragen.

:1-H*X^.5+Y[     % floor(sqrt(2*n)+.5) for n from 0 to N-1, where N is implicit input
2j3/*YP*Ze       % exp(2j*pi/3* ... )
Ys               % cumulative sum. Produces complex positions
G:               % vector 1,2...,N, where N is previous input
Zp               % logical index to select only prime numbers
)                % use that index to keep only complex positions of primes
'.'2$XG          % plot using marker '.'
Luis Mendo
quelle
Was muss ich noch weiter lesen
Brain Guider
Probiert es online aus! Grafikausgabe für MATL unterstützen?
Alex A.
Ich dachte, TIO unterstützt keine grafische Ausgabe? In diesem Fall kann MATL Bilder automatisch in eine .pngDatei kopieren, die von der Webseite @AlexA
Luis Mendo am
Hallo! Ich habe einfach test ( plot(1:5)) gemacht und es wird eine Textgrafik ausgegeben !! matl.tryitonline.net/#code=NTpYRw&input= @AlexA. Wie ist das??
Luis Mendo
4
WHOA! Das ist großartig!
Alex A.
8

Zeichnen sollte mit erfolgen

LaTeX / PGF, 527 594 Bytes

\documentclass{standalone}\usepackage{pgf}\let\z\let\z\e\advance\z\f\ifnum\z\h\the\z\a\newcount\a\i\a\j\a\l\a\x\a\y\a\p\a\q\a\n\i=1\l=1\p=-1\q=1\def\m#1{\e\i by1\e\j by1\e\x by\h\p\e\y by\h\q\pgfmathparse{isprime(\h\i)}\f\pgfmathresult=1\pgfpathcircle{\pgfpoint{\h\x cm}{\h\y cm}}3pt\fi\f\j=\l\e\l by1\j=0\f\p=1\p=-1\q=1\else\f\p=-1\p=0\q=-1\else\p=1\q=0\fi\fi\fi\f#1>0\e#1by-1\m#1\fi}\begin{document}\begin{pgfpicture}\pgftransformcm10{cos(60)}{sin(60)}\pgfpointorigin\n=4000\m\n\pgfusepath{fill}\end{pgfpicture}\end{document}

527 Bytes ist das vollständige Dokument wie oben, dh einschließlich Präambel und Parameter (hier 4000, also ~ 523 ohne Parameter). Erzeugt eine PDF-Datei.

Grundidee: Nun, zeichne einfach. Verwendet eine Matrixtransformation für ein Dreiecksgitter. Das einzige Problem ist, dass auch die Punkte von der Transformation betroffen (und gestreckt) sind. Also wähle ich für Ellipsen-Marker :) was ich damit meine, wird im zweiten Bild deutlich (n = 250, 5pt).

Eine weitere Einschränkung: Kann aufgrund der maximalen Stapelgröße von TeX nur bis zu etwas weniger als 5000 verarbeiten. Das erste Bild ist für n = 4000. Anscheinend ist es möglich, den Stapel zu vergrößern , ich habe es nicht ausprobiert.

Verwendet PGFs isprime().

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Ungolfed:

\documentclass[border=10cm]{standalone}

\usepackage{pgf}

\newcount\ulami
\newcount\ulamj
\newcount\ulamlen

\newcount\ulamx
\newcount\ulamy
\newcount\ulamdx
\newcount\ulamdy

\ulami=1 %
\ulamj=0 %
\ulamlen=1 %
\ulamdx=-1 %
\ulamdy=1 %
\ulamx=0 %
\ulamy=0 %

\def\ulamplot#1{%
  \advance\ulami by 1 %
  \advance\ulamj by 1 %

  \advance\ulamx by \the\ulamdx %
  \advance\ulamy by \the\ulamdy %

  \pgfpathmoveto{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}

  \pgfmathparse{isprime(\the\ulami)}
  \let\r=\pgfmathresult
  \ifnum\r=1
    \pgfpathcircle{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}{5pt}
  \fi

  \ifnum\ulamj=\the\ulamlen %
    \advance\ulamlen by 1 %
    \ulamj=0 %
    \ifnum\ulamdx=1 %
      \ulamdx=-1 %
      \ulamdy=1 %
    \else%
      \ifnum\ulamdx=-1 %
        \ulamdx=0 %
        \ulamdy=-1 %
      \else%
        \ulamdx=1 %
        \ulamdy=0 %
      \fi
    \fi
  \fi

  \ifnum#1>0 %
    \advance#1 by -1 %
    \ulamplot{#1}%
  \fi
}

\begin{document}

\begin{pgfpicture}
  \pgfmathsetmacro{\x}{cos(60)}
  \pgfmathsetmacro{\y}{sin(60)}
  \pgftransformcm{1}{0}{\x}{\y}{\pgfpointorigin}

  \pgfpathmoveto{\pgfpointorigin}
  \color{blue}
  \newcount\ulamn
  \ulamn=400
  \ulamplot{\ulamn}
  \pgfusepath{stroke,fill}
\end{pgfpicture}

\end{document}
Gemeinschaft
quelle
1
Wow. Es wäre mir nie in den Sinn gekommen, dies in LaTeX
Luis Mendo am
Die Verwendung eines lualatexoder eines anderen dynamisch zuweisenden Compilers sollte es Ihnen ermöglichen, die Stapelgröße zu umgehen, wenn ich Ihren entsprechenden Kommentar richtig verstehe. Es ist also keine Einschränkung Ihrer Antwort, nur der meisten Implementierungen, bei denen Sie sie ausführen würden.
Andras Deak
Tut mir leid, ich habe es überprüft und die maximale Größe des Eingabestapels hat nichts mit der Speicherzuweisung zu tun, die ich in meinem vorherigen Kommentar angesprochen habe :(
Andras Deak
@AndrasDeak das ist okay, danke, dass du es nachgeschlagen hast. Ich habe eine Methode gefunden , die anscheinend den Stapel vergrößert, es aber (noch) nicht selbst ausprobiert.
@CamilStaps danke, ich habe andere ähnliche Beiträge gefunden, aber ich habe sie auch nicht ausprobiert. Jedenfalls nehme ich Christian Feuersängers Beiträge als Kanon :)
Andras Deak
2

Mathematica, 94 Bytes

ListPlot@Accumulate[Join@@Table[ReIm@Exp[2i Pi/3I],{i,2#^.5},{i}]][[Prime@Range@PrimePi@#-1]]&

Ergebnis

%[10000]

Bildbeschreibung hier eingeben

njpipeorgan
quelle
2

Python, 263 Bytes

Als Python-Neuling gibt es sicherlich Verbesserungspotential :)

from matplotlib.pyplot import*
from math import*
def f(m):
 s=[];X=[];Y=[];i=x=y=0
 while len(s)<m:i+=1;s+=[i%3*pi*2/3]*i
 for i in range(m):
  x+=cos(s[i]);y+=sin(s[i]);j=i+2
  if all(map(lambda a:j%a>=1,range(2,int(j**.5+1)))):X+=[x];Y+=[y]
 scatter(X,Y);show()

Beispiel:

f(100000)

Bildbeschreibung hier eingeben

lambruscoAcido
quelle
Sie können s=[];X=[];Y=[];i=1;x=0;y=0biss=X=Y=[];i=1;x=y=0;
rp.beltran
Ignorieren Sie das zusätzliche Semikolon am Ende. Es sollte Ihnen 8 Bytes ersparen.
rp.beltran
@ rp.beltran. Das funktioniert nicht. Ich denke, es hängt damit zusammen, dass die Objekte dieselben Werte haben. Konnte nur hinzufügen x=y=0.
LambruscoAcido
Du hast recht. Ich habe vergessen, dass Python Listen als Referenz weitergibt. Zahlen sind unveränderlich und daher ist es ungefährlich, mit ganzen Zahlen zu arbeiten.
rp.beltran
1

R 137 Bytes

Verwendet nur integrierte Funktionen, auch für Primzahlen. Aufgrund seines vektorisierten Ansatzes anstelle eines iterativen Ansatzes ist es schnell, kann jedoch keine großen Zahlen verarbeiten.

Golf gespielt:

g=function(m){M=1:m;s=rep(M,M)[M]%%3*pi*2/3;k=cumsum;j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1));plot(k(cos(s))[j],k(sin(s))[j])}

Ungolfed:

g=function(m) {
  M = 1:m
  s = rep(M,M)[M] %% 3 * pi * 2/3
  k=cumsum
  j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1)) # primes
  plot(k(cos(s))[j],k(sin(s))[j])    # cumulated coordinates
}

Beispiel:

g(10000)

Bildbeschreibung hier eingeben

lambruscoAcido
quelle
Können Sie ein Beispielergebnis hinzufügen?
Luis Mendo
@ LuisMendo. Sicher. Ich musste nur herausfinden, wie man eine Handlung hinzufügt.
lambruscoAcido