¿Se pueden generar anillos de árbol cuadrados a partir de primos?

33

¡Aparentemente sí! En tres sencillos pasos.

Paso 1

Supongamos que f ( n ) denota la función de recuento de primos (número de primos menor o igual que n ).

Defina la secuencia entera s ( n ) de la siguiente manera. Para cada entero positivo n ,

  • Iniciar t to n .
  • Mientras t no sea primo ni 1, reemplace t por f ( t ) e itere.
  • El número de iteraciones es s ( n ).

Se garantiza que el proceso iterativo finalizará porque f ( n ) < n para todo n .

Considere por ejemplo n = 25. Iniciamos t = 25. Como esto no es un primo ni 1, calculamos f (25), que es 9. Esto se convierte en el nuevo valor para t . Esto no es primo ni 1, por lo que continuamos: f (9) es 4. Continuamos nuevamente: f (4) es 2. Como es primo, nos detenemos aquí. Hemos realizado 3 iteraciones (de 25 a 9, luego a 4, luego a 2). Así s (25) es 3.

Los primeros 40 términos de la secuencia son los siguientes. La secuencia no está en 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

Paso 2

Dado un número entero positivo impar N , construya una matriz N × N (matriz) enrollando la secuencia finita s (1), s (2), ..., s ( N 2 ) para formar una espiral cuadrada hacia afuera . Por ejemplo, dado N = 5, la espiral es

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)

o, sustituyendo los valores,

 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

Paso 3

Representa la matriz N × N como una imagen con un mapa de color gris, o con algún otro mapa de color de tu gusto. El mapa debe ser gradual, de modo que el orden de los números corresponda a un orden visualmente obvio de los colores. Los casos de prueba a continuación muestran algunos mapas de colores de ejemplo.

El reto

Dado un número entero positivo impar N , produzca la imagen descrita anteriormente.

Reglas

  • La espiral debe estar hacia afuera, pero puede estar en sentido horario o antihorario, y puede comenzar a moverse hacia la derecha (como en el ejemplo anterior), hacia la izquierda, hacia abajo o hacia arriba.

  • Las escalas de los ejes horizontal y vertical no necesitan ser las mismas. También las etiquetas de eje, la barra de colores y elementos similares son opcionales. Mientras se pueda ver claramente la espiral, la imagen es válida.

  • Las imágenes pueden emitirse por cualquiera de los medios estándar . En particular, la imagen puede mostrarse en la pantalla, o puede producirse un archivo de gráficos, o puede emitirse una matriz de valores RGB. Si genera un archivo o una matriz, publique un ejemplo de cómo se ve cuando se muestra.

  • Los medios de entrada y el formato son flexibles como de costumbre . Se puede proporcionar un programa o una función . Las lagunas estándar están prohibidas .

  • El código más corto en bytes gana.

Casos de prueba

Las siguientes imágenes (clic para una resolución total) corresponden a varios valores de N . Se utiliza una espiral en sentido horario, hacia la derecha, como en el ejemplo anterior. Las imágenes también ilustran varios mapas de colores válidos.

  • N = 301: ingrese la descripción de la imagen aquí

  • N = 501: ingrese la descripción de la imagen aquí

  • N = 701: ingrese la descripción de la imagen aquí

Luis Mendo
fuente
Si una matriz de valores de s(n)se puede alimentar a alguna función / paquete de trazado sin ser modificado (creo que imshowen matplotlib podría manejar esto, por ejemplo) ¿es esta una forma de salida aceptable?
dylnan
@dylnan Claro, siempre que trace la imagen en la pantalla o produzca un archivo, es válida. De hecho, generé los ejemplos con algo similar a lo que mencionas. Solo tenga cuidado con la escala de valores. Por ejemplo no es aceptable si todos los valores por encima de 1 se les da el mismo color, como Matlab de (y posiblemente Matplotlib de) imshowhace
Luis Mendo
buen punto. No estoy seguro si imshowhace eso.
dylnan
1
@ kamoroso94 Por favor vea aquí
Luis Mendo
1
Sí, muy claro
Christopher el

Respuestas:

3

Dyalog APL, 94 bytes

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

asume ⎕IO=0

salida para n = 701 (convertido de .pgm a .png):

ingrese la descripción de la imagen aquí

ngn
fuente
10

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

Afeitado 12 bytes, gracias a Ander y Andras, y muchas gracias a Luis por poner los dos juntos. Afeitado 16 gracias a Remco, 6 gracias a 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)))

Resultado para N=301( F(301)):

ingrese la descripción de la imagen aquí

Explicación:

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
fuente
8

Wolfram Language (Mathematica) , 124 bytes

¡Gracias a Martin Ender por guardar 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]]&

Pruébalo en línea!


La imagen generada es:

Espiral

Fórmula de forma cerrada del valor espiral tomado directamente de esta respuesta mía.

usuario202729
fuente
55
#/2-.5guarda un byte.
user202729
8
Jaja, ¿te lo estás sugiriendo?
Luis Mendo
66
@ user202729 Parece que no funciona.
user202729
18
No quise interrumpir tu diálogo interno :-P
Luis Mendo
Aplaza la definición de phasta que la necesites:...,{y,p=(1-#)/2,-p},{x,p,-p}
Martin Ender
7

MATLAB: 115 114 110 bytes

One liner (ejecutado en R2016b + como función en script ) 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

Poner la función en un archivo separado, como sugiere flawr, y usar el 1 byte adicional por regla de archivo adicional

En el archivo s.m, 64 + 1 bytes para código + archivo

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

Ventana de comando para definir I, 45 bytes

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

Total: 110 bytes


Esto utiliza la recursividad en lugar de whilebucle como lo hacen las otras implementaciones de MATLAB ( gnovice , Adriaan ). Ejecútelo como un script (en R2016b o posterior), esto define la función Ique se puede ejecutar comoI(n) .

Versión estructurada:

% 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

Ejemplo:

I(301)

plot

Notas:

  • Traté de hacer la sfunción anónima también, por supuesto, eso reduciría el recuento significativamente. Sin embargo, hay 2 problemas:

    1. La recursión infinita es difícil de evitar cuando se utilizan funciones anónimas, ya que MATLAB no tiene un operador ternario para ofrecer una condición de interrupción. Crear un tipo de operador ternario (ver más abajo) también cuesta bytes, ya que necesitamos la condición dos veces.

    2. Debe pasar una función anónima a sí misma si es recursiva (ver aquí ) que agrega bytes.

    Lo más cerca que llegué a esto fue usar las siguientes líneas, tal vez se pueda cambiar para que funcione:

    % 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
fuente
6

MATLAB - 126 121 * bytes

Intenté un enfoque más vectorizado que Adriaan y pude eliminar más bytes. Aquí está la solución de una sola línea:

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)))

Y aquí está la solución bien formateada:

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)))

* Nota: si usted está dispuesto a permitir que un crapton métrica de iteraciones innecesarias, puede cambiar la línea while any(i), a for m=v, y guardar 5 bytes.

gnovice
fuente
¡Agradable! Me gusta cómo usas cumsumpara vectorizar y evitarnnz(primes(...)
Luis Mendo
1
Si entiendo correctamente, no hace daño repetir más veces de lo necesario (a costa de la velocidad). Para que pueda reemplazar while any(i)por for m=M. A quién le importa si el código tarda horas en ejecutarse :-)
Luis Mendo
2
@LuisMendo: Claro, ¿por qué no? Ya itera una vez más de lo necesario, ¿qué otra n^2o más iteraciones van a doler? ;)
gnovice
1
¡Ese es el espíritu! También puede mantener la versión más rápida, pero el recuento de bytes es el más corto
Luis Mendo el
2

Python 3, 299 265 bytes

Saved 5 bytes thanks to formatting suggestions from Jonathan Frech and NoOneIsHere. Removed an additional 34 bytes by removing a function definition that was only called once.

This is a little longer than some others, due to python not having a command to determine primeness, or spiral an array. It runs relatively quickly however, around a minute for 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

Test it with

n = 7
x = S(n)
imshow(x, interpolation='none')
colorbar()
show(block=False)
user2699
fuente
1
Possible 294 bytes (untested).
Jonathan Frech
1
One quick thing: you can remove the space between import and *.
NoOneIsHere
2

J, 121 Bytes

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

Defines a function:

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
fuente
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)}

Slightly less golfed:

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
}

Anonymous function. Output in a graphic window. Scale is on the red-scale with darkest shade equals to 0 and clearer shades increasing values.

Result for n=101:

n=101

plannapus
fuente