Espiral Ulam triangular

21

Nós tivemos um par de desafios sobre a espiral Ulam. Mas isso não basta.

Neste desafio, traçaremos uma espiral Ulam triangular (em oposição à espiral Ulam quadrada usual). Aqui está um esboço de como é a espiral.

insira a descrição da imagem aqui

Como sabemos, a espiral de Ulam organiza todos os números naturais em uma espiral externa e marca apenas aqueles que são primos. Portanto, no esboço acima, apenas os números que aparecem em preto (os números primos) seriam mostrados.

O desafio

Aceite um número N como entrada e exiba a espiral triangular Ulam até esse número.

  • A entrada pode ser stdin ou argumento de função.
  • A espiral deve girar na direção positiva (ou seja, no sentido anti-horário), como na figura acima.
  • Qualquer uma das curvas de 120 graus da figura acima seria válida e a curva pode ser diferente para diferentes entradas. Mas o lado mais baixo dos triângulos implícitos deve ser horizontal, pois as únicas curvas permitidas são (múltiplos de) 120 graus.
  • O código deve ser executado teoricamente (com tempo e memória suficientes) para qualquer N até o permitido por qualquer cálculo intermediário que você faça com o tipo de dados padrão. doublebasta; não há necessidade de tipos inteiros grandes.
  • Todas as funções internas são permitidas.
  • Não aceitarei minha própria resposta (não que eu ache que seria a mais curta de qualquer maneira ...).

Formatos de saída

Escolha uma das seguintes opções.

  1. Exiba um gráfico com um marcador (ponto, círculo, cruz, o que você preferir) em números primos e nada em números não primos. A escala não precisa ser a mesma para os dois eixos. Ou seja, os triângulos implícitos não precisam ser equilaterais. Eixos, linhas de grade e rótulos de eixo são opcionais. Apenas os marcadores nos números primos são necessários.

    Um exemplo de saída para N = 12 seria o seguinte (compare com o esboço acima). O segundo gráfico é um exemplo mais interessante, correspondendo a N = 10000.

insira a descrição da imagem aqui

insira a descrição da imagem aqui

  1. Produza um arquivo de imagem com o descrito acima, em qualquer formato de imagem conhecido (como png, tiff, bmp).
  2. Exiba a espiral como arte ASCII , usando um único caractere de sua escolha para números primos e espaço em branco para não números primos, com um espaço em branco para separar as posições numéricas na mesma linha. Espaços iniciais ou finais ou novas linhas são permitidos. Por exemplo, o caso N = 12 usando ocomo caractere seria

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

    onde é claro que apenas a omarca nos números primos seria realmente exibida. Os ·números não primos são mostrados aqui apenas para referência.

Critério de vitória

A recompensa real é ver por si mesmo esses incríveis padrões de código, o código mais curto vence.

Luis Mendo
fonte
2
No futuro, eu recomendaria escolher apenas uma das [saídas gráficas] e [ascii-art], pois isso torna as submissões menos comparáveis. Mas bom desafio de qualquer maneira. :)
Alex A.
@AlexA. Obrigado! Vou levar isso em conta. Então ... haverá uma resposta de Julia? ;-)
Luis Mendo
Uau, obrigado pela recompensa, mas você deve aceitar sua própria resposta. Ele é o mais curto. :)
Martin Ender
É bem merecido! Quanto à aceitação de uma resposta, uma das regras do desafio era "Não aceitarei minha própria resposta". Quando eu pensei que este desafio que inevitavelmente teve MATL em mente, com seu complexo de números e funções gráficas, por isso foi um pouco como fazer batota :-)
Luis Mendo

Respostas:

13

CJam, 49 42 bytes

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

Entrada como um único inteiro em STDIN. Saída como uma grade ASCII com 0para números primos. A rotação da espiral não é consistente: o maior número de espiral estará sempre na linha inferior.

Teste aqui.

Explicação

A idéia básica é representar o triângulo como uma matriz 2D irregular durante o cálculo. Você obtém essa matriz revertendo as linhas e alinhando todas as linhas à esquerda:

   4
  5 3
 6 1 2
7 8 9 A

Seria representado como

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

Como espelhamos a linha, queremos enrolar a espiral no sentido horário . Isso é conveniente, porque tudo o que precisamos fazer é girar o triângulo no sentido anti-horário e preceder a próxima sub-lista em ordem. Podemos girar o array irregular, invertendo todas as linhas e transpondo-o:

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

Então aqui está o código. Um detalhe que eu gostaria de chamar a atenção é o último bit que cria o layout triangular. Eu acho isso bastante bacana. :)

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
fonte
11
Eu sabia que você seria o primeiro!
Luis Mendo
@LuisMendo Na verdade, eu ia pular esse aqui, porque achei que o cálculo dos índices da grade seria tedioso, mas então percebi que era possível girar o triângulo inteiro acrescentando linhas.
Martin Ender
11
Sempre adoro suas explicações sobre os programas CJam porque posso entendê- las e fico impressionado com a complexidade e a curiosidade desses programas.
ETHproductions
10

MATL , 48 36 bytes

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

Usa a versão atual (9.3.0) .

Experimente online! Não faço ideia de como o compilador online consegue converter a saída gráfica em ASCII, mas isso produz um gráfico ASCII aproximado, graças a um recurso Octave suportado pelo compilador online!

Editar (4 de abril de 2016): a função Y[foi renomeada kdesde o release 13.0.0. O link para o compilador online incorpora essa alteração, para que o código possa ser testado.

Exemplo

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

produz a saída gráfica (versão MATLAB mostrada):

insira a descrição da imagem aqui

Explicação

O código usa números complexos para rastrear o caminho seguido pela espiral. Como pode ser visto na primeira figura do desafio, cada perna reta da espiral é um segmento com comprimento crescente 1, 2, 3, 4 ... e ciclicamente aumentando a orientação 120 graus, 240 graus, 0 graus, 0 graus, 120 graus. ..

O código primeiro gera os deslocamentos complexos individuais de cada número inteiro para o próximo. Esses deslocamentos complexos têm magnitude 1 e ângulo 2*pi/3, 4*pi/3ou 0(em radianos). Assim, eles podem ser facilmente gerados como exponenciais imaginários. Para isso, a sequência inteira 0,1,2,2,3,3,3,4,4,4,4 ... é usada primeiro.

Essa sequência inteira é quase como a sequência "n aparece n vezes" ( OEIS A002024 ) e pode ser obtida como floor(sqrt(2*n)+.5)onde nestá 0,1,2,3, .... A multiplicação por 2j*pi/3, onde jestá a unidade imaginária, produz os deslocamentos complexos desejados.

Os deslocamentos são acumulados para calcular as posições correspondentes aos números inteiros na espiral. O primeiro número inteiro na espiral, ou seja 1, está arbitrariamente localizado na posição 1no plano complexo.

Finalmente, as posições correspondentes a números não primos são descartadas e o restante é plotado no plano complexo.

: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
fonte
Oo Oo eu preciso ler isso mais #
Brain Guider
Experimente Online! suporta saída gráfica para MATL?
Alex A.
Eu pensei que o TIO não suportava saída gráfica? Se isso acontecer, eu posso facilmente ter MATL despejar automaticamente imagens para um .pngarquivo a ser mostrado pelo @AlexA página web
Luis Mendo
Ei! Eu fiz teste simples ( plot(1:5)) e produz saída de texto e gráfico !! matl.tryitonline.net/#code=NTpYRw&input= @AlexA. Como é isso??
Luis Mendo 15/01
4
UAU! Fantástico!
Alex A.
8

O desenho deve ser feito com

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 é o documento completo como acima, ou seja, incluindo preâmbulo e parâmetro (aqui 4000, então ~ 523 sem parâmetro). Produz um arquivo PDF.

Idéia básica: bem, basta desenhar. Usa uma transformação de matriz para uma grade triangular. O único problema é que também os pontos são afetados (e esticados) pela transformação. Então, eu escolho marcadores de elipse :) o que quero dizer com isso é claro na segunda imagem (n = 250, 5pt).

Outra ressalva: só pode lidar com um pouco menos de 5000 por causa do tamanho máximo da pilha do TeX. A primeira imagem é para n = 4000. Aparentemente, é possível aumentar o tamanho da pilha , eu não tentei.

Usa PGFs isprime().

insira a descrição da imagem aqui

insira a descrição da imagem aqui

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}
Comunidade
fonte
11
Uau. Nunca me ocorreu fazer isso no LaTeX
Luis Mendo
Usar lualatexou algum outro compilador de alocação dinâmica deve permitir que você ignore o tamanho da pilha, se eu entender corretamente o seu comentário correspondente. Portanto, não é uma limitação da sua resposta, apenas da maioria das implementações em que você a executaria.
Andras Deak
Desculpe, verifiquei e o limite de tamanho da pilha de entrada não tem relação com a alocação de memória, abordada no meu comentário anterior :(
Andras Deak
@AndrasDeak está tudo bem, obrigado por procurar. Encontrei um método que aparentemente aumenta o tamanho da pilha, mas ainda não o testei.
@CamilStaps obrigado, encontrei outros posts semelhantes, mas também não os experimentei. De qualquer forma, eu tomo posts 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]

insira a descrição da imagem aqui

njpipeorgan
fonte
2

Python, 263 bytes

Sendo novo no Python, certamente há espaço para melhorias :)

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

Exemplo:

f(100000)

insira a descrição da imagem aqui

lambruscoAcido
fonte
Você pode encurtar s=[];X=[];Y=[];i=1;x=0;y=0paras=X=Y=[];i=1;x=y=0;
rp.beltran
Ignore esse ponto e vírgula extra no final. Deve poupar 8 bytes.
precisa saber é o seguinte
@ rp.beltran. Isso não funciona. Eu acho que está relacionado ao fato de os objetos compartilharem os mesmos valores. Só foi possível adicionar x=y=0.
precisa saber é o seguinte
Meu mal, você está certo. Esqueci que o Python passa listas por referência. Os números são imutáveis ​​e, portanto, é seguro relacionar números inteiros.
precisa saber é o seguinte
1

R, 137 bytes

Usa apenas funções internas, mesmo para números primos. Dada sua abordagem vetorizada em vez de iterativa, é rápida, mas não pode lidar com grandes números.

Golfe:

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
}

Exemplo:

g(10000)

insira a descrição da imagem aqui

lambruscoAcido
fonte
Você pode adicionar um resultado de exemplo?
Luis Mendo
@LuisMendo. Certo. Eu só tinha que descobrir como adicionar um enredo.
usar o seguinte código