Können aus Primzahlen quadratische Baumringe erzeugt werden?

33

Anscheinend ja! In drei einfachen Schritten.

Schritt 1

Sei f ( n ) die Primzahlfunktion (Anzahl der Primzahlen kleiner oder gleich n ).

Definieren der ganzzahlige Sequenz s ( n ) wie folgt. Für jede positive ganze Zahl n ,

  • Initiiere t zu n .
  • Solange t weder Primzahl noch 1 ist, ersetzen Sie t durch f ( t ) und iterieren Sie.
  • Die Anzahl der Iterationen ist s ( n ).

Es ist garantiert, dass der iterative Prozess endet, da f ( n ) < n für alle n .

Betrachten Sie zum Beispiel n = 25. Wir initialisieren t = 25. Da dies weder eine Primzahl noch eine 1 ist, berechnen wir f (25), was 9 ist. Dies wird der neue Wert für t . Dies ist weder eine Primzahl noch eine 1, also fahren wir fort: f (9) ist 4. Wir fahren erneut fort: f (4) ist 2. Da dies eine Primzahl ist, hören wir hier auf. Wir haben 3 Iterationen durchgeführt (von 25 bis 9, dann bis 4, dann bis 2). Somit ist s (25) 3.

Die ersten 40 Terme der Sequenz lauten wie folgt. Die Sequenz ist nicht in OEIS.

0 0 0 1 0 1 0 2 2 2 0 1 0 2 2 2 0 1 0 3 3 3 0 3 3 3 3 3 0 3 0 1 1 1 1 1 0 2 2 2

Schritt 2

Gegeben eine ungerade positive ganze Zahl N , bauen eine N × N - Matrix (Matrix) durch die endliche Sequenz Wicklung s (1), s (2), ..., s ( N 2 ) ein Quadrat nach außen bilden Spirale . Zum Beispiel ist die Spirale bei N = 5

s(21)   s(22)   s(23)   s(24)   s(25)
s(20)   s(7)    s(8)    s(9)    s(10)
s(19)   s(6)    s(1)    s(2)    s(11)
s(18)   s(5)    s(4)    s(3)    s(12)
s(17)   s(16)   s(15)   s(14)   s(13)

oder durch Ersetzen der Werte

 3       3       0       3       3
 3       0       2       2       2
 0       1       0       0       0
 1       0       1       0       1
 0       2       2       2       0

Schritt 3

Stellen Sie das N × N-Array als Bild mit einer grauen Farbkarte oder einer anderen Farbkarte nach Ihrem Geschmack dar. Die Karte sollte graduell sein, damit die Reihenfolge der Zahlen einer visuell offensichtlichen Reihenfolge der Farben entspricht. Die folgenden Testfälle zeigen einige Beispiele für Farbkarten.

Die Herausforderung

Erzeugen Sie bei einer ungeraden positiven ganzen Zahl N das oben beschriebene Bild.

Regeln

  • Die Spirale muss nach außen zeigen, kann jedoch im oder gegen den Uhrzeigersinn verlaufen und sich nach rechts (wie im obigen Beispiel), links, unten oder oben bewegen.

  • Die Maßstäbe der horizontalen und vertikalen Achse müssen nicht identisch sein. Auch Achsenbeschriftungen, Farbbalken und ähnliche Elemente sind optional. Solange die Spirale gut sichtbar ist, ist das Bild gültig.

  • Bilder können mit jedem der Standardmittel ausgegeben werden . Insbesondere kann das Bild auf dem Bildschirm angezeigt werden, oder es kann eine Grafikdatei erzeugt werden, oder es kann ein Array von RGB-Werten ausgegeben werden. Wenn Sie eine Datei oder ein Array ausgeben, veröffentlichen Sie bitte ein Beispiel dafür, wie es bei der Anzeige aussieht.

  • Eingabemittel und Format sind wie gewohnt flexibel . Ein Programm oder eine Funktion kann bereitgestellt werden . Standardlücken sind verboten .

  • Kürzester Code in Bytes gewinnt.

Testfälle

Die folgenden Bilder (Klicken für volle Auflösung) entsprechen mehrere Werte von N . Eine im Uhrzeigersinn nach rechts gerichtete erste Spirale wird wie im obigen Beispiel verwendet. Die Bilder veranschaulichen auch mehrere gültige Farbkarten.

  • N = 301: Bildbeschreibung hier eingeben

  • N = 501: Bildbeschreibung hier eingeben

  • N = 701: Bildbeschreibung hier eingeben

Luis Mendo
quelle
Wenn ein Array von Werten von in eine Zeichenfunktion s(n)/ ein Paket imshoweingegeben werden kann, ohne dass dies geändert wird (ich denke, dass matplotlib dies zum Beispiel handhaben könnte), ist dies eine akzeptable Ausgabeform?
Dylnan
@dylnan Sicher, solange das Bild auf dem Bildschirm gezeichnet oder eine Datei erstellt wird, ist es gültig. Tatsächlich habe ich die Beispiele mit etwas ähnlichem erzeugt, was Sie erwähnen. Seien Sie vorsichtig mit der Skalierung von Werten. Zum Beispiel ist es nicht akzeptabel, wenn alle Werte über 1 die gleiche Farbe haben, wie es Matlabs (und möglicherweise Matplotlibs) imshowtun
Luis Mendo
guter Punkt. Ich bin mir nicht sicher, ob imshowdas so ist.
Dylnan
1
@ kamoroso94 Bitte sehen Sie hier
Luis Mendo
1
Ja, sehr klar
Christopher

Antworten:

3

Dyalog APL, 94 Bytes

'P2'
2⍴n←⎕
9
(⍪0){×≢⍵:(≢⍺)((⍉∘⌽⍺,↑)∇↓)⍵⋄⍺}2↓{⍵⌊1+⍵[+\p]}⍣≡9×~p←1=⊃+/(≠⍨,≠⍨,~⍴⍨(×⍨n)-2×≢)¨,\×⍳n

geht davon aus ⎕IO=0

Ausgabe für n = 701 (konvertiert von .pgm nach .png):

Bildbeschreibung hier eingeben

ngn
quelle
10

MATLAB - 197 185 178 175 184 163 162 148 142 140 Bytes

Dank Ander und Andras 12 Bytes rasiert, und vielen Dank an Luis für die Zusammenstellung der beiden. Rasiert 16 dank Remco, 6 dank flawr

function F(n)
p=@primes
s=@isprime
for a=2:n^2
c=0
if~s(a)
b=nnz(p(a))
while~s(b)
b=nnz(p(b))
c=c+1
end
end
d(a)=c
end
imagesc(d(spiral(n)))

Ergebnis für N=301( F(301)):

Bildbeschreibung hier eingeben

Erläuterung:

function F(n)
p=@primes % Handle
s=@isprime % Handle
for a=2:n^2 % Loop over all numbers
    c=0 % Set initial count
    if~s(a) % If not a prime
        b=nnz(p(a)) % Count primes
        while~s(b) % Stop if b is a prime. Since the code starts at 2, it never reaches 1 anyway
            b=nnz(p(b)) % count again
            c=c+1 % increase count
        end
    end
    d(a)=c % store count
end
imagesc(d(spiral(n))) % plot
Adriaan
quelle
8

Wolfram Language (Mathematica) , 124 Byte

Vielen Dank an Martin Ender für das Speichern von 12 Bytes!

Image[#/Max@#]&[Array[(n=0;Max[4#2#2-Max[+##,3#2-#],4#
#-{+##,3#-#2}]+1//.x_?CompositeQ:>PrimePi[++n;x];n)&,{#,#},(1-#)/2]]&

Probieren Sie es online!


Das erzeugte Bild ist:

Spiral

Geschlossene Formel des Spiralwertes, der direkt aus meiner Antwort entnommen wurde .

user202729
quelle
5
#/2-.5Speichert ein Byte.
user202729
8
Haha, schlagen Sie sich das vor?
Luis Mendo
6
@ user202729 Scheint nicht zu funktionieren.
user202729
18
Ich wollte deinen inneren Dialog nicht unterbrechen :-P
Luis Mendo
Verschieben Sie die Definition von, pbis Sie es brauchen:...,{y,p=(1-#)/2,-p},{x,p,-p}
Martin Ender
7

MATLAB: 115 114 110 Bytes

Ein Liner (ausgeführt in R2016b + als Funktion im Skript ) 115 Bytes

I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end;end

Platzieren Sie die Funktion in einer separaten Datei, wie von flawr vorgeschlagen, und verwenden Sie die Regel 1 zusätzliches Byte pro zusätzlicher Datei

In der Datei s.m64 + 1 Byte für Code + Datei

function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end

Befehlsfenster zu definieren I, 45 Bytes

I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)))

Gesamt: 110 Bytes


Dies verwendet eine Rekursion, anstatt whilewie die anderen MATLAB-Implementierungen ( gnovice , Adriaan ) eine Schleife auszuführen . Führen Sie es als Skript aus (in R2016b oder neuer), dies definiert die Funktion, Idie ausgeführt werden kann I(n).

Strukturierte Version:

% Anonymous function for use, i.e. I(301)
% Uses arrayfun to avoid for loop, spiral to create spiral!
I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));

% Function for recursively calculating the s(n) value
function k=s(n,k)
    % Condition for re-iterating. Otherwise return k unchanged
    if n>1 && ~isprime(n)
        % Increment k and re-iterate
        k = s( nnz(primes(n)), k+1 );
    end
end

Beispiel:

I(301)

Handlung

Anmerkungen:

  • Ich habe auch versucht, die sFunktion zu anonymisieren, das würde natürlich die Anzahl erheblich reduzieren. Es gibt jedoch zwei Probleme:

    1. Eine unendliche Rekursion ist schwer zu vermeiden, wenn anonyme Funktionen verwendet werden, da MATLAB keinen ternären Operator hat, der eine Unterbrechungsbedingung bietet. Ein ternärer Operator (siehe unten) kostet ebenfalls Bytes, da wir die Bedingung zweimal benötigen.

    2. Sie müssen eine anonyme Funktion an sich selbst übergeben, wenn sie rekursiv ist (siehe hier ), wodurch Bytes hinzugefügt werden.

    Als nächstes habe ich die folgenden Zeilen verwendet, die möglicherweise geändert werden können, um zu funktionieren:

    % Condition, since we need to use it twice 
    c=@(n)n>1&&~isprime(n);
    % This uses a bodged ternary operator, multiplying the two possible outputs by
    % c(n) and ~c(n) and adding to return effectively only one of them
    % An attempt was made to use &&'s short-circuiting to avoid infinite recursion
    % but this doesn't seem to work!
    S=@(S,n,k)~c(n)*k+c(n)&&S(S,nnz(primes(n)),k+1);
Wolfie
quelle
6

MATLAB - 126 121 * Bytes

Ich habe einen vektorisierteren Ansatz als Adriaan versucht und konnte mehr Bytes einsparen. Hier ist die einzeilige Lösung:

function t(n),M=1:n^2;c=0;i=1;s=@isprime;v=cumsum(s(M));while any(i),i=M>1&~s(M);c=c+i;M(i)=v(M(i));end;imagesc(c(spiral(n)))

Und hier ist die schön formatierte Lösung:

function t(n),
  M = 1:n^2;
  c = 0;
  i = 1;
  s = @isprime;
  v = cumsum(s(M));
  while any(i),         % *See below
    i = M > 1 & ~s(M);
    c = c+i;
    M(i) = v(M(i));
  end;
  imagesc(c(spiral(n)))

* Hinweis: Wenn Sie bereit sind, eine Metrik mit unnötigen Iterationen zuzulassen, können Sie die Zeile while any(i), in ändern for m=v, und 5 Bytes sparen.

Gnovice
quelle
Nett! Ich mag, wie Sie verwenden, um cumsumzu vektorisieren und zu vermeidennnz(primes(...)
Luis Mendo
1
Wenn ich das richtig verstehe, tut es nicht weh, mehr als nötig zu iterieren (auf Kosten der Geschwindigkeit). So können Sie ersetzen while any(i)durch for m=M. Wen kümmert es, wenn der Code stundenlang ausgeführt wird :-)
Luis Mendo
2
@ LuisMendo: Klar, warum nicht? Es iteriert schon einmal mehr als nötig, was noch für eine n^2oder mehrere Iterationen wehtun werden! ;)
Gnovice
1
Das ist der Geist! Sie können auch die schneller laufende Version behalten, aber die Byteanzahl ist die der kürzeren
Luis Mendo
2

Python 3, 299 265 Bytes

5 Bytes gespart dank Formatierungsvorschlägen von Jonathan Frech und NoOneIsHere. Zusätzliche 34 Byte wurden entfernt, indem eine Funktionsdefinition entfernt wurde, die nur einmal aufgerufen wurde.

Dies ist etwas länger als bei einigen anderen, da Python keinen Befehl zum Bestimmen der Primzahl oder zum Spiralisieren eines Arrays hat. Es läuft jedoch relativ schnell, etwa eine Minute lang n = 700.

from pylab import*
def S(n):
 q=arange(n*n+1);t=ones_like(q)
 for i in q[2:]:t[2*i::i]=0
 c=lambda i:0 if t[i]else 1+c(sum(t[2:i]));S=[c(x)for x in q]
 t=r_[[[S[1]]]]
 while any(array(t.shape)<n):m=t.shape;i=multiply(*m)+1;t=vstack([S[i:i+m[0]],rot90(t)])
 return t

Testen Sie es mit

n = 7
x = S(n)
imshow(x, interpolation='none')
colorbar()
show(block=False)
user2699
quelle
1
Mögliche 294 Bytes (ungetestet).
Jonathan Frech
1
Eine schnelle Sache: Sie können den Raum zwischen importund entfernen *.
NoOneIsHere
2

J, 121 Bytes

load 'viewmat'
a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1'

Definiert eine Funktion:

a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1' | Full fuction
                                                                     (,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1  | Creates the number spiral
              {:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0                                      | Applies S(n) to each element
       viewmat                                                                                             | View the array as an image
Bolce Bussiere
quelle
2

R, 231 Bytes

function(n){p=function(n)sum(!n%%2:n)<2;M=matrix(0,n,n);M[n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))]=sapply(1:(n^2),function(x){y=0;while(x>2&!p(x)){x=sum(sapply(2:x,p));y=y+1};y});image(M)}

Etwas weniger Golf gespielt:

function(n){
    p=function(n)sum(!n%%2:n)<2 #"is.prime" function
    M=matrix(0,n,n)             #empty matrix
    indices=n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))
    values=sapply(1:(n^2),function(x){
        y=0
        while(x>2&!p(x)){
            x=sum(sapply(2:x,p))
            y=y+1
            }
        y})
    M[indices]=values
    image(M) #Plotting
}

Anonyme Funktion. Ausgabe in einem Grafikfenster. Die Skala ist auf der roten Skala, wobei der dunkelste Farbton gleich 0 ist und klarere Farbtöne die Werte erhöhen.

Ergebnis für n = 101:

n = 101

Plannapus
quelle