Primes de la espiral de Ulam

17

La espiral de Ulam es un tema realmente fascinante, pero desconcertante, en matemáticas. Aquí se puede encontrar cómo funciona en detalle , pero se puede explicar un breve resumen de la siguiente manera:

Comienzo escribiendo un uno, luego escribo dos a la derecha. Sobre los dos, escribo un tres, y a la izquierda escribo cuatro. Continúo este patrón de dar vueltas alrededor de 1 (y cualquier número entre yo y 1) infinitamente (o hasta que se me indique que pare), formando un patrón en espiral. (ver ejemplo a continuación)

El objetivo

Haga un programa que acepte n (siempre será un número impar mayor que cero) como una entrada que se correlaciona con el número de filas, luego imprime los valores de los primos fila por fila de la espiral de Ulam. El formato puede ser de cualquier manera, pero debe ser legible y obvio.

Por ejemplo, dada la entrada 3, su programa debería salir 5,3,2,7, porque 3 filas producen la siguiente espiral:

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

Como se trata de un código de golf, ¡la respuesta con la menor cantidad de bytes gana (no importa cuán ineficiente)! Las lagunas estándar no son aceptables.

Addison Crump
fuente
¿Se permite una coma final? O mejor aún, espacio separado, por ejemplo, `` `5 3 2 7```
Tom Carpenter
55
Mientras sea legible para los humanos y me pueda decir los números primos, siéntase libre.
Addison Crump

Respuestas:

8

Pyth, 20 bytes

f}TPTsuC+R=hZ_GtyQ]]

Pruébelo en línea: demostración

Este código genera la espiral completa de Ulam, conecta todas las líneas y filtros para primos.

Explicación:

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

MATLAB, 48

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

Básicamente, esto crea una espiral del tamaño requerido (solicitado por el usuario), luego lo organiza de modo que aparezca en el orden de fila correcto. Esto se almacena en a. A continuación, muestra todos los valores en a que son primos.

Como dijiste en cualquier formato legible, guardé un byte y busqué la salida predeterminada de disp () que es (en tu caso de prueba, n = 3):

 5
 3
 2
 7

Como una ventaja adicional, esto funciona para cualquier n> 0, incluidos los números pares. Por ejemplo, la salida para n = 10 es:

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
fuente
1
¡Muy agradable! Es bueno saber esa spiralfunción
Luis Mendo
6

CJam, 42 33 bytes

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

Pruébalo en línea

La última versión incluye mejoras sustanciales sugeridas por @Martin.

El método para construir la espiral es, en cada paso, rotar la matriz que tenemos hasta ahora en 90 grados, y agregar una fila con números adicionales. Esto se repite (n / 2) * 4veces.

Los valores en la matriz resultante se filtran para ser primos.

Explicación:

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
fuente
¿Podría 2/4*ser reemplazado por 2*, o lo ha dejado así a propósito?
ETHproductions
@ETHproductions Eso no es equivalente porque es una división entera. Por ejemplo, para la entrada 3, el resultado debe ser 4. En realidad, ahora que lo pienso, creo que hay un byte para guardar. (2*Debe ser correcto.
Reto Koradi
5

Mathematica 223

Esto se apropia del código de Kuba para una espiral de Ulam. Es por eso que lo envío como wiki comunitario. Simplemente lo jugué y seleccioné los números primos, que se enumeran por la fila en la que residen.

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]

Ejemplo

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

Para mejorar la pantalla:

 %// MatrixForm

matriz

revs DavidC
fuente
4

Mathematica, 118 bytes

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

Esto genera la espiral de Ulam en forma lineal al observar que la posición de cada número posterior se puede acumular como

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

es decir, comenzar desde el centro, luego moverse 1 derecha, 1 arriba, 2 izquierda, 2 abajo, 3 derecha, 3 arriba, ...

Salida:

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

fuente
1

Javascript, 516 363 304 276 243 240 Bytes

Mi solución no crea una matriz densa con la espiral, sino que devuelve el índice que corresponde al número dado en la matriz de Ulam del orden dado. Por lo tanto, itera a través de los números entre 2 y M * M y crea una matriz de primos con el idx dado por el fn ulamIdx

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

Minified se ve así:

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

Para la entrada 15, la salida es:

,,,,,,,,,,,,,,,, 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
fuente
Eso fue un poco de compresión. ¿Puedes explicar tu código original y tus cambios?
Addison Crump
Quité algunos soportes inútiles. Y me di cuenta de que uI () tenía 4 condicionales con bloques similares. Cada uno con 3 líneas que generaron Fila y Columna para el segmento actual (vea el bloque de documentos principal), por lo que reemplazo esos 4 bloques por líneas ll & llt y la línea de retorno decide si llt es fila o columna. S & 2 es verdadero para s en (3,2) (segmentos superior e izquierdo); s <3, para s en (1,2) derecha y superior. S & 1, para s en (1,3) determinará si los valores en ll & llt son row & col o col & row y M (espiral) × row + col evita índices superpuestos (como matriz rectificadora pero con idx lineal incorrecto, la corrección sería necesita ll-1
juanmf
En el bucle principal (run ()) solo si i es primo (que fn se redujo ya que nunca necesita probar <2 ni% 1), solicita el índice de i (ll, llt) en la espiral, que se rectifica. Luego simplemente imprima la matriz de resultados.
juanmf
Hay 3 matrices conceptualmente importantes. Interior, curret y M. Útil para calcular la fila absoluta y col. Restar interior a n nos deja con un relativo int en la corriente (en la que n cae) en espiral. Y la diferencia entre el orden de M y el actual se juega como compensación para la fila y la columna en la ronda actual para obtener los absolutos.
juanmf
364 -> 240 escribiendo la lógica fn en línea y eliminando las pruebas no utilizadas.
juanmf