Espiral triangular de Ulam

21

Hemos tenido un par de desafíos sobre la espiral de Ulam. Pero eso no es suficiente.

En este desafío, trazaremos una espiral de Ulam triangular (en oposición a la espiral de Ulam cuadrada habitual). Aquí hay un bosquejo de cómo se ve la espiral.

ingrese la descripción de la imagen aquí

Como sabemos, la espiral de Ulam organiza todos los números naturales en una espiral externa, y marca solo aquellos que son primos. Entonces, en el boceto anterior, solo se mostrarán los números que aparecen en negro (los primos).

El reto

Acepte un número N como entrada y muestre la espiral triangular de Ulam hasta ese número.

  • La entrada puede ser stdin o argumento de función.
  • La espiral debe girar en la dirección positiva (es decir, en sentido antihorario), como en la figura anterior.
  • Cualquiera de los giros de 120 grados de la figura anterior sería válido, y el giro puede ser diferente para diferentes entradas. Pero el lado más bajo de los triángulos implícitos debe ser horizontal, ya que los únicos giros permitidos son (múltiplos de) 120 grados.
  • El código debería ejecutarse teóricamente (con suficiente tiempo y memoria) para cualquier N hasta lo permitido por cualquier cálculo intermedio que realice con su tipo de datos predeterminado. doublees suficiente; sin necesidad de tipos enteros grandes.
  • Todas las funciones incorporadas permitidas.
  • No aceptaré mi propia respuesta (no creo que sea la más corta de todos modos ...).

Formatos de salida

Elija cualquiera de los siguientes.

  1. Muestre un gráfico con un marcador (punto, círculo, cruz, lo que prefiera) en números primos y nada en números no primos. La escala no necesita ser la misma para los dos ejes. Es decir, los triángulos implícitos no necesitan ser equiláteros. Los ejes, las líneas de cuadrícula y las etiquetas de eje son opcionales. Solo se requieren los marcadores en los números primos.

    Un resultado de ejemplo para N = 12 sería el siguiente (compárelo con el bosquejo anterior). El segundo gráfico es un ejemplo más interesante, correspondiente a N = 10000.

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

  1. Produzca un archivo de imagen con lo anterior, en cualquier formato de imagen conocido (como png, tiff, bmp).
  2. Muestre la espiral como arte ASCII , utilizando un solo carácter de su elección para primos y espacio en blanco para no primos, con un espacio en blanco para separar las posiciones numéricas en la misma fila. Se permiten espacios iniciales o finales o nuevas líneas. Por ejemplo, el caso N = 12 usando ocomo carácter sería

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

    donde, por supuesto, solo ose mostrará la marca en los números primos. El ·al no primos se muestra aquí sólo por referencia.

Criterio ganador

La recompensa real es ver por ti mismo esos increíbles patrones. Código de golf, el código más corto gana.

Luis Mendo
fuente
2
En el futuro, recomendaría elegir solo uno de [salida gráfica] y [ascii-art] ya que hace que las presentaciones sean menos comparables. Pero buen desafío de todos modos. :)
Alex A.
@AlexA. ¡Gracias! Lo tendré en cuenta. Entonces ... ¿habrá una respuesta de Julia? ;-)
Luis Mendo
Wow, gracias por la recompensa, pero deberías aceptar tu propia respuesta. Que es la más corta. :)
Martin Ender
¡Es bien merecido! En cuanto a aceptar una respuesta, una de las reglas del desafío era "No aceptaré mi propia respuesta". Cuando pensé en este desafío, inevitablemente tenía en mente a MATL, con su número complejo y sus funciones gráficas, así que fue un poco como hacer trampa :-)
Luis Mendo

Respuestas:

13

CJam, 49 42 bytes

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

Ingrese como un entero entero en STDIN. Salida como una cuadrícula ASCII con 0primos. La rotación de la espiral no es consistente: el mayor número de la espiral siempre estará en la fila inferior.

Pruébalo aquí.

Explicación

La idea básica es representar el triángulo como una matriz 2D irregular mientras se realiza el cálculo. Obtiene esta matriz invirtiendo las líneas y alineando todas las filas a la izquierda:

   4
  5 3
 6 1 2
7 8 9 A

Sería representado como

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

Como hemos reflejado la línea, queremos enrollar la espiral en sentido horario . Eso es conveniente, porque todo lo que tenemos que hacer es rotar el triángulo en sentido antihorario y anteponer la siguiente sublista en orden. Podemos rotar la matriz irregular invirtiendo todas las líneas y transponiéndola:

                                                           [[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]]

Entonces aquí está el código. Un detalle al que me gustaría llamar la atención es el último bit que crea el diseño triangular. Creo que es bastante ingenioso. :)

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
fuente
1
¡Sabía que serías el primero!
Luis Mendo
@LuisMendo En realidad iba a omitir este, porque pensé que el cálculo de los índices de la cuadrícula sería tedioso, pero luego me di cuenta de que podía rotar todo el triángulo mientras agregaba líneas.
Martin Ender
1
Siempre me encantan sus explicaciones de los programas de CJam porque puedo entenderlos , y me sorprende lo complejos, pero cortos, que pueden ser estos programas.
ETHproductions
10

MATL , 48 36 bytes

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

Utiliza la versión actual (9.3.0) .

Pruébalo en línea! No tengo idea de cómo el compilador en línea logra traducir la salida gráfica a ASCII, pero lo hace. ¡ Esto produce un diagrama ASCII aproximado gracias a una característica de octava que es compatible con el compilador en línea!

Editar (4 de abril de 2016): la función Y[ha cambiado de nombre kdesde la versión 13.0.0. El enlace al compilador en línea incorpora este cambio, de modo que el código se puede probar.

Ejemplo

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

produce la salida gráfica (se muestra la versión de MATLAB):

ingrese la descripción de la imagen aquí

Explicación

El código usa números complejos para trazar la ruta seguida por la espiral. Como se puede ver en la primera figura del desafío, cada tramo recto de la espiral es un segmento con una longitud creciente 1, 2, 3, 4 ... y una orientación que aumenta cíclicamente 120 grados, 240 grados, 0 grados, 120 grados. ..

El código primero genera los desplazamientos complejos individuales de cada número entero al siguiente. Estos desplazamientos complejos tienen magnitud 1 y ángulo 2*pi/3, 4*pi/3o 0(en radianes). Por lo tanto, se pueden generar fácilmente como exponenciales imaginarios. Para eso, la secuencia entera 0,1,2,2,3,3,3,4,4,4,4 ... se usa primero.

Esta secuencia entera es casi como la secuencia "n aparece n veces" ( OEIS A002024 ), y se puede obtener como floor(sqrt(2*n)+.5)donde nes 0,1,2,3, .... Multiplicar por 2j*pi/3, donde jestá la unidad imaginaria, produce los desplazamientos complejos deseados.

Los desplazamientos se acumulan para calcular las posiciones correspondientes a los números enteros en la espiral. El primer número entero en la espiral, que es 1, está ubicado arbitrariamente en una posición 1en el plano complejo.

Finalmente, las posiciones correspondientes a números no primos se descartan, y el resto se traza en el plano complejo.

: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
fuente
Qué necesito para leer esto más
Brain Guider
¿Lo prueba en línea! admite salida gráfica para MATL?
Alex A.
¿Pensé que TIO no era compatible con la salida gráfica? Si es así, puedo hacer que .pngMATL descargue automáticamente las imágenes en un archivo que se mostrará en la página web @AlexA
Luis Mendo
¡Oye! ¡Hice yo simple test ( plot(1:5)) y produce resultados gráficos de texto! matl.tryitonline.net/#code=NTpYRw&input= @AlexA. ¿¿Cómo es esto??
Luis Mendo
44
Whoa! ¡Eso es genial!
Alex A.
8

El dibujo debe hacerse con

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 es el documento completo como arriba, es decir, incluye preámbulo y parámetro (aquí 4000, entonces ~ 523 sin parámetro). Produce un archivo PDF.

Idea básica: bueno, solo dibuja. Utiliza una transformación matricial para una cuadrícula triangular. El único problema es que también los puntos se ven afectados (y estirados) por la transformación. Así que elijo los marcadores de elipse :) lo que quiero decir con eso está claro en la segunda imagen (n = 250, 5pt).

Otra advertencia: solo puede manejar hasta un poco menos de 5000 debido al tamaño máximo de pila de TeX. La primera imagen es para n = 4000. Aparentemente es posible aumentar el tamaño de la pila , no lo intenté.

Utiliza PGF's isprime().

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Sin golf:

\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}
Comunidad
fuente
1
Guau. Nunca se me habría ocurrido hacer esto en LaTeX
Luis Mendo
Usar lualatexu otro compilador de asignación dinámica debería permitirle omitir el tamaño de la pila, si entiendo su comentario correspondiente correctamente. Por lo tanto, no es una limitación de su respuesta, solo de la mayoría de las implementaciones donde la ejecutaría.
Andras Deak
Lo siento, lo he comprobado y el límite de tamaño de la pila de entrada no está relacionado con la asignación de memoria que abordé en mi comentario anterior :(
Andras Deak
@AndrasDeak está bien, gracias por buscarlo. Encontré un método que aparentemente aumenta el tamaño de la pila, pero no lo probé yo mismo (todavía).
@CamilStaps gracias, he encontrado otras publicaciones similares, pero tampoco las probé. De todos modos, tomo las publicaciones de Christian Feuersänger como canon :)
Andras Deak
2

Mathematica, 94 bytes

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

Resultado

%[10000]

ingrese la descripción de la imagen aquí

njpipeorgan
fuente
2

Python, 263 bytes

Siendo nuevo en Python, seguramente hay margen de mejora :)

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

Ejemplo:

f(100000)

ingrese la descripción de la imagen aquí

lambruscoAcido
fuente
Puede acortar s=[];X=[];Y=[];i=1;x=0;y=0as=X=Y=[];i=1;x=y=0;
rp.beltran el
Ignora ese punto y coma extra al final. Debería ahorrarte 8 bytes.
rp.beltran
@ rp.beltran. Esto no funciona. Creo que está relacionado con el hecho de que los objetos comparten los mismos valores. Solo se pudo agregar x=y=0.
lambruscoAcido
Mi mal, tienes razón. Olvidé que Python pasa las listas por referencia. Los números son inmutables, por lo que es seguro hacerlo con enteros.
rp.beltran
1

R, 137 bytes

Utiliza solo funciones integradas, incluso para números primos. Dado su enfoque vectorizado en lugar de iterativo, es rápido, pero no puede manejar grandes cantidades.

Golfizado:

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

Sin golf:

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
}

Ejemplo:

g(10000)

ingrese la descripción de la imagen aquí

lambruscoAcido
fuente
¿Puedes agregar un resultado de ejemplo?
Luis Mendo
@LuisMendo. Seguro. Solo tenía que descubrir cómo agregar una trama.
lambruscoAcido