50

¡La "hormiga principal" es un animal obstinado que navega por los enteros y los divide hasta que solo quedan números primos!

Inicialmente, tenemos una matriz infinita A que contiene todos los enteros> = 2: [2,3,4,5,6,.. ]

Deje pser la posición de la hormiga en la matriz. Inicialmente p = 0(la matriz está indexada en 0)

Cada turno, la hormiga se moverá de la siguiente manera:

si A[p]es primo, la hormiga se mueve a la siguiente posición:p ← p+1
de lo contrario, si A[p]es un número compuesto, qsea su divisor más pequeño> 1. Dividimos A[p]entre qy sumamos qa A[p-1]. La hormiga se mueve a la posición anterior:p ← p-1

Aquí están los primeros movimientos para la hormiga:

 2  3  4  5  6  7  8  9  ... 
 ^
 2  3  4  5  6  7  8  9  ... 
    ^
 2  3  4  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
    ^
 2  5  2  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
          ^
 2  5  2  5  6  7  8  9  ... 
             ^
 2  5  2  7  3  7  8  9  ... 
          ^

Su programa debería mostrar la posición de la hormiga después de los nmovimientos. (puedes asumir n <= 10000)

Casos de prueba:

0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512

Editar. también puede usar listas indexadas 1, es aceptable mostrar los resultados 1, 7, 10, 275, 513 para el caso de prueba anterior.

Este es el código de golf, por lo que gana el código con el código más corto en bytes.

code-golf sequence primes Arnaud
fuente

32

Sinceramente, pensé que había una hormiga en mi pantalla cuando vi esto en las Preguntas de la red activa.

Kodos Johnson

14

Me pregunto si la secuencia está bien definida para arbitrariamente grande n(o si el caso compuesto podría empujar la hormiga a la izquierda de la inicial 2).

Martin Ender

1

@SuperChafouin para que los resultados de los casos de prueba puedan ser: 1,7,10,275,513si se indica 1 indexación? O aún tendrían que coincidir con sus resultados.

Tom Carpenter

12

@MartinEnder Otra pregunta abierta es si un primo> 7 eventualmente puede dejarse para siempre.

Arnauld

2

@Arnauld En cuanto al movimiento n = 1,000,000,000 (donde p = 17156661), la relación entre nyp está muy cerca de p = n / (ln (n) * ln (ln (n))).

Penguino

11

Alice , 45 bytes

/o
\i@/.&wqh!]k.&[&w;;?c]dt.n$k&;[.?~:![?+!kq

Pruébalo en línea!

Implementación principalmente directa.

Los ntiempos de bucle en Alice generalmente se realizan presionando los n-1tiempos de una dirección de retorno y luego regresando al final de cada iteración con k. La última vez a través del ciclo, la kinstrucción no tiene a dónde volver, y la ejecución continúa.

Este programa usa la misma kinstrucción para detenerse temprano cuando el número es primo. Como resultado, la iteración final siempre moverá la hormiga a la izquierda. Para compensar este error, hacemos n+1iteraciones en una matriz indexada en 1, lo que da exactamente el resultado que queremos (y da el caso n=0de forma gratuita).

Nitrodon
fuente

7

Python 2 , 120 bytes

p=0
A=range(2,input()+2)
for _ in A:
 for q in range(2,A[p]):
	if A[p]%q<1:A[p]/=q;p-=1;A[p]+=q;break
 else:p+=1
print p

Pruébalo en línea!

Ah, el raro for- elselazo! La elsecláusula solo se ejecuta si no se sale del forcuerpo a través de . En nuestro caso, esto significa que verificamos todos los correos electrónicos y no encontramos ninguno para dividir .breakqp

Lynn
fuente

7

Octava , 109103101 94 bytes

function i=a(n)i=1;for l=z=2:n+1
if nnz(q=factor(z(i)))>1
z(i--)/=p=q(1);z(i--)+=p;end
i++;end

Pruébalo en línea!

Este código generará la posición en 1 indexación, por lo que las salidas para casos de prueba son:

0 => 1
10 => 7
47 => 10
4734 => 275
10000 => 513

Esta versión utiliza algunas optimizaciones de octava, por lo que no es compatible con MATLAB. El siguiente código es una versión compatible con MATLAB.

MATLAB, 130 123 118 117 bytes

function i=a(n)
z=2:n+1;i=1;for l=z
q=factor(z(i));if nnz(q)>1
z(i)=z(i)/q(1);i=i-1;z(i)=z(i)+q(1);else
i=i+1;end
end

Utiliza la indexación 1 como con la versión Octave. Lo probé en todos los casos de prueba en MATLAB. Como ejemplo, la salida en 100000 es 3675 (una indexación).

Una versión comentada del código anterior:

function i=a(n)
    z=2:n+1;                %Create our field of numbers
    i=1;                    %Start of at index of 1 (MATLAB uses 1-indexing)
    for l=1:n               %For the required number of iterations
        q=factor(z(i));     %Calculate the prime factors of the current element
        if nnz(q)>1         %If there are more than one, then not prime
            z(i)=z(i)/q(1); %So divide current by the minimum
            i=i-1;          %Move back a step
            z(i)=z(i)+q(1); %And add on the minimum to the previous.
        else
            i=i+1;          %Otherwise we move to the next step
        end
    end

Como cuestión de interés, esta es la posición de las hormigas frente al número de iteraciones para los primeros 10000 valores de n.

Parece probable que la hormiga tenderá al infinito, pero quién sabe, la apariencia puede ser engañosa.

MATLAB: guardado 6 bytes en forlugar de whiley eliminando corchetes de if- Gracias @Giuseppe
MATLAB: Ahorre 2 bytes - Gracias @Sanchises
Octave: Ahorre 10 bytes usando Octave \=y +=operaciones - Gracias @Giuseppe
Octave: Ahorre 2 bytes con i++y i--- Gracias @LuisMendo
Octave: Ahorre 7 bytes - Gracias @Sanchises

Tom Carpenter
fuente

Para que funcione en TIO, creo que necesitas un endpara que coincida con la firma de la función

Giuseppe

@Giuseppe Ah, está bien. En MATLAB, el seguimiento endes opcional.

Tom Carpenter

puede hacer una función anónima usando @ (n) al comienzo en lugar de usar la función i = a (n)

Michthan

@Michthan no puede hacer eso en MATLAB. ¿No creo que sea posible en Octave tampoco porque tiene bucles?

Tom Carpenter el

1

El seguimiento también endes opcional en Octave. Aquí solo es necesario porque tiene código después de la función

Luis Mendo

6

JavaScript (ES6), 91 bytes

f=(n,a=[p=0])=>n--?f(n,a,(P=n=>++x<n?n%x?P(n):a[a[p]/=x,--p]+=x:p++)(a[p]=a[p]||p+2,x=1)):p

Manifestación

Nota: es posible que deba aumentar el tamaño de pila predeterminado de su motor para que pase todos los casos de prueba.

Pruébalo en línea!

Arnauld
fuente

6

Haskell , 108 106 94 bytes

([0]#[2..]!!)
(a:b)#(p:q)=length b:([b#(a+d:div p d:q)|d<-[2..p-1],mod p d<1]++[(p:a:b)#q])!!0

Pruébalo en línea! Ejemplo de uso: ([0]#[2..]!!) 10rendimientos 6(indexados a 0).

La función #opera en dos listas, el frente invertido de la matriz [p-1, p-2, ..., 1]y el resto infinito de la matriz [p, p+1, p+2, ...]. Construye una lista infinita de posiciones, desde la cual nse devuelve la posición th dada una entrada n.

El patrón se ((a:b)#(p:q))une pal valor de la posición actual de la hormiga y aal valor a la posición anterior. bes el prefijo de la matriz desde la posición 1 a p-2y qel descanso infinito a partir de la posición p+1.

Construimos una lista de llamadas recursivas de la siguiente manera: observamos cada divisor dde p(que es mayor que uno y menor que p) en orden ascendente y sumamos b#(a+d:div p d:q)para cada uno de ellos, es decir, el valor actual pse divide por dy la hormiga se mueve un paso a la izquierda donde dse agrega a. Luego anexamos (p:a:b)#qal final de esta lista, que indica que la hormiga se mueve un paso hacia la derecha.

Luego tomamos la primera de esas llamadas recursivas de la lista y anteponemos la posición actual, que coincide con la longitud de la lista de prefijos b. Debido a que los divisores están en orden ascendente, elegir el primero de la lista de llamadas recursivas garantiza que usemos el más pequeño. Además, como (p:a:b)#qse agrega al final de la lista, solo se selecciona si no hay divisores y, por plo tanto, es primo.

Ediciones:
-2 bytes cambiando la lista de funciones de orden descendente a ascendente.
-12 bytes gracias a la idea de Zgarb de indexar en una lista infinita en lugar de manejar un contador, y cambiando a indexación 0.

Laikoni
fuente

2

96 bytes mediante la creación de una lista infinita e indexación, en lugar de llevar alrededor del mostrador.

Zgarb

1

@ Zgarb ¡Muchas gracias! Incluso es de solo 94 bytes cuando se cambia a indexación 0.

Laikoni

5

TI-BASIC, 108 103 102 98 bytes

La entrada y la salida se almacenan en Ans. La salida está indexada en 1.

Ans→N
seq(X,X,2,9³→A
1→P
For(I,1,N
1→X:∟A(P→V
For(F,2,√(V
If X and not(fPart(V/F:Then
DelVar XV/F→∟A(P
P-1→P
F+∟A(P→∟A(P
End
End
P+X→P
End

kamoroso94
fuente

Puede quitar un byte fPart(∟A(P)/F:con fPart(F¹∟A(P:. Lo mismo en la siguiente línea.

Scott Milner

@ScottMilner Eso no siempre funciona. not(fPart(7⁻¹7es 0 pero not(fPart(7/7es 1.

kamoroso94

5

MATL , 41 bytes

:Q1y"XHyw)Zp?5MQ}1MtYf1)/H(8MyfHq=*+9M]]&

La salida está basada en 1. El programa agota el tiempo para el último caso de prueba en el intérprete en línea.

Pruébalo en línea!

Explicación

El programa aplica el procedimiento como se describe en el desafío. Para hacerlo, hace un uso inusualmente intenso de los portapapeles manuales y automáticos de MATL.

El divisor más pequeño se obtiene como la primera entrada en la descomposición del factor primo.

La actualización "brecha" se realiza sobrescribiendo la entrada correspondiente de la matriz A . La actualización "agregar" se realiza mediante la adición de elementos a A una matriz que contiene ceros, excepto en la posición deseada.

:Q        % Implicitly input n. Push array [2 3 ... n+1]. This is the initial array A. 
          % It contains all required positions. Some values will be overwritten
1         % Push 1. This is the initial value for p
y         % Duplicate from below
"         % For each loop. This executes the following n times.
          %   STACK (contents whosn bottom to top): A, p
  XH      %   Copy p into clipboard H
  y       %   Duplicate from below. STACK: A, p, A
  w       %   Swap. STACK: A, A, p
  )       %   Reference indexing. STACK: A, A[p]
  Zp      %   Isprime. STACK: A, false/true
  ?       %   If true (that is, if A[p] is prime)
    5M    %     Push p from automatic clipboard. STACK: A, p
    Q     %     Add 1. STACK: A, p+1
  }       %   Else (that is, if A[p] is not prime)
    1M    %     Push A[p] from automatic clipboard. STACK: A, A[p]
    t     %     Duplicate. STACK: A, A[p], A[p]
    Yf    %     Prime factors, with repetitions. STACK: A, A[p], prime factors of A[p]
    1)    %     Get first element, d. STACK: A, A[p], d
    /     %     Divide. STACK: A, A[p]/d
    H     %     Push p from clipboard H. STACK: A, A[p]/d, p
    (     %     Assignment indexing: write value. STACK: A with A[p] updated
    8M    %     Push d from automatic clipboard.
    y     %     Duplicate from below. STACK: A with A[p] updated, d, A with A[p] updated
    f     %     Find: push indices of nonzero entries.
          %     STACK: A with A[p] updated, d, [1 2 ... n]
    Hq    %     Push p from clipboard H, subtract 1.
          %     STACK: A with A[p] updated, d, [1 2 ... n], p-1
    =     %     Test for equality, element-wise.
          %     STACK: A with A[p] updated, d, [0 ... 0 1 0 ... 0]
    *     %     Multiply, element-wise. STACK: A with A[p] updated, [0 ... 0 d 0 ... 0]
    +     %     Add, element-wise. STACK: A with A[p-1] and A[p] updated
    9M    %     Push p-1 from automatic clipboard.
          %     STACK: A with A[p-1] and A[p] updated, p-1
  ]       %   End if. The stack contains the updated array and index
]         % End for each. Process the next iteration
&         % Specify that the following implicit display function should display only
          % the top of the stack. Implicitly display

Luis Mendo
fuente

3

Pyth - 44 bytes

Implementación procesal directa.

K}2hhQVQJ@KZIP_J=hZ).?=GhPJ XKZ/JG=tZ XZKG;Z

Test Suite .

Maltysen
fuente

3

PARI / GP, 87 bytes

f(n)=A=[2..9^5];p=1;for(i=1,n,q=factor(A[p])[1,1];if(A[p]-q,A[p]/=q;p--;A[p]+=q,p++));p

Bastante autoexplicativo (no tan golfista). Si no cuenta la f(n)=parte, son 82 bytes. También puede comenzar por n->(85 bytes).

Es un lenguaje 1 indexado.

Editar: la modificación illustrate(n,m)=A=[2..m+1];p=1;for(i=1,n,for(j=1,m,printf("%5s",if(j==p,Str(">",A[j],"<"),Str(A[j]," "))));print();q=factor(A[p])[1,1];if(A[p]!=q,A[p]/=q;p--;A[p]+=q,p++))imprimirá una ilustración de la caminata de la hormiga (dado un terminal lo suficientemente ancho). Por ejemplo illustrate(150,25), dará los primeros 150 pasos en 25 columnas, así:

  > 2 <3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 3 <4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 3> 4 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 5 <2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 2 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 5 <6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 5> 6 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 7 <3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 3 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 7 <8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3 7> 8 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 9 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 6 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 9 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 5 <3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 3 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 3 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 3 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 3> 4 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 5 <2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 2 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 2> 9 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 5 <3 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 3 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 3> 10 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 5 <5 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 5 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 11 <12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 11> 12 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 13 <6 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 13> 6 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 15 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 8 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 7 <4 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 7> 4 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 9 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 8 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 7 <4 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 7> 4 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 9 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 6 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 5 <3 3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5> 3 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3> 3 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3> 2 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2> 3 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 2 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 5 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 3 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 13 <14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3 13> 14 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 15 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 6 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 7 <3 5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 3 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 5 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 7 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5 7> 15 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 10 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 7 <5 5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 5 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 5 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 5> 16 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 7 <8 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 7> 8 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 9 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 8 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 9 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 6 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 9 <3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 5 <3 3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5> 3 <3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3> 3 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 3 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 3> 4 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 5 <2 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5> 2 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 3 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 3> 4 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 5 <2 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 2 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 17 <18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 17> 18 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 19 <9 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 19> 9 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 22 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 4 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 7 <2 11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 2 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 11 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 3 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 19 <20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3 19> 20 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 21 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 6 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 13 <3 7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 3 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 7 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3 7> 10 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 9 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 6 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 15 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 5 <5 3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 5 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 3 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 3 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 5 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3 5> 21 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 8 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 5 <4 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 5> 4 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 7 <2 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 2 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 7 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2 7> 22 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 9 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 5 <3 11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 3 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 11 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 23 <24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11 23> 24 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 25 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 16 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 5 <8 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 5> 8 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 7 <4 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 7> 4 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 9 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 8 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 9 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 6 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 7 <3 3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7> 3 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 3 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 3> 4 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 5 <2 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5> 2 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2> 3 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 2 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 5 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 5> 12 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 7 <6 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 7> 6 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 9 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 5 <3 3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 3 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 3 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3 3> 25 <26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 8 <5 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 5 <4 5 26

Jeppe Stig Nielsen
fuente

2

Python 2 , 142127 bytes

Guardado quince bytes gracias a Sherlock9 .

T=range(2,input()+2);p=0
for _ in T:
 m=T[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:T[p-1]/=d;p-=2;T[p]+=d
print p

Pruébalo en línea!

Jonathan Frech
fuente

127 bytes si no usasP(n)

Sherlock9

126 bytes

Felipe Nardi Batista

@FelipeNardiBatista Desafortunadamente, su sugerencia no parece funcionar para los casos de prueban<=4

Sherlock9

2

Mathematica, 118103 bytes

(s=Range[2,5^6];t=1;Do[If[PrimeQ@s[[t]],t++,s[[t]]/=(k=#2&@@ Divisors@s[[t]]);s[[t-1]]+=k;t--],#];t-1)&

Pruébalo en línea!

Martin Ender ahorró 15 bytes

J42161217
fuente

Tienes un espacio perdido delante Divisors, puedes usar notación infija para Do, y puedes regresar en tlugar de t-1(resultado basado en 1).

Martin Ender

2

Python 3 , 158 149 133 bytes

Esta es una implementación de procedimiento sencilla con una o dos peculiaridades para asegurarse de que el código funcione para todos los casos de prueba. Lo uso [*range(2,n+9)]para asegurarme de que A sea lo suficientemente grande (excepto n<3, n+9es más que suficiente) La elsecláusula divide lo antiguo A[p]por ddecrementos py luego se agrega da lo nuevo A[p], lo que definitivamente es una mala práctica de codificación. De lo contrario, bastante sencillo. Sugerencias de golf bienvenidas!

Editar: -9 bytes sin sympygracias a Halvard Hummel. -14 bytes de Felipe Nardi Batista, -6 bytes de algunas señales de la respuesta Python 2 de Jonathan Frech

p,_,*A=range(int(input())+2)
for _ in A:
 m=A[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:A[p-1]//=d;p-=2;A[p]+=d
print(p)

Pruébalo en línea!

Sherlock9
fuente

145 bytes

Halvard Hummel

148 bytes convirtiéndolo en un programa completo

Felipe Nardi Batista

if d-m:A[p]...y else:p+=1para salvar un byte

Felipe Nardi Batista

143 bytes eliminando la elsedeclaración

Felipe Nardi Batista

después de eliminar la elsedeclaración, no hay diferencia en bytes para la versión de la función

Felipe Nardi Batista

2

PHP, 102 + 1 bytes

for($a=range(2,$argn);$argn--;$d<$a[+$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[+$p]%++$d;);echo$p;

Ejecutar como tubería -Ro probarlo en línea .

Salida vacía para entrada 0; insertar +después echopara un literal0

o use esta versión indexada 1 (103 + 1 bytes):

for($a=range($p=1,$argn);$argn--;$d<$a[$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[$p]%++$d;);echo$p;

Titus
fuente

2

R , 123 bytes

Una implementación sencilla. Se proporciona como una función, que toma el número de movimientos como entrada y devuelve la posición p.

Se repite sobre la secuencia y mueve el puntero hacia adelante y hacia atrás según las reglas. La salida está basada en 0.

Una nota: para encontrar el factor primo más pequeño de un número x, calcula el módulo de x en relación con todos los enteros de 0 a x. Luego extrae los números con un módulo igual a 0, que siempre son [0,1, ..., x]. Si el tercer número no es x, entonces es el factor primo más pequeño de x.

p=function(l){w=0:l;v=w+1;j=1;for(i in w){y=v[j];x=w[!y%%w][3]
if(x%in%c(NA,y))j=j+1
else{v[j]=y/x;j=j-1;v[j]=v[j]+x}}
j-2}

Pruébalo en línea!

NofP
fuente

2

C (gcc), 152 148 bytes

Minified

int f(int n){int*A=malloc(++n*4),p=0,i,q;for(i=0;i<n;i++)A[i]=i+2;for(i=1;i<n;i++){for(q=2;A[p]%q;q++);if(A[p++]>q){A[--p]/=q;A[--p]+=q;}}return p;}

Formado con algunos comentarios.

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  // Initialize array A
  for (i = 0; i < n; i++)
    A[i] = i + 2;
  // Do n step (remember n was incremented)
  for (i = 1; i < n; i++) {
    // Find smallest divisor
    for (q = 2; A[p] % q; q++)
      ;
    if (A[p++] > q) {
      A[--p] /= q;
      A[--p] += q;
    }
  }
  return p;
}

Función principal para probar

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
  if (argc != 2)
    return 2;
  int n = atoi(argv[1]);
  int p = f(n);
  printf("%d => %d\n", n, p);
  return 0;
}

Por mostrar cada paso

Declarar display () dentro de f ()

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  void display(void) {
    for (int i=0; i < p; i++) {
      printf(" %d", A[i]);
    }
    printf(" \033[1;31m%d\033[m", A[p]);
    if (p+1 < n)
      printf(" %d", A[p+1]);
    printf("\n");
  }
  ...

Pantalla de llamada()
```
  A[i] = i + 2;
display();
```
Pantalla de llamada()
```
  }
  display();
}
```

usuario285259
fuente

Puede recortar algunos bytes declarando A como una matriz e inicializando sus controles de bucle antes de los bucles donde sea posible, ¿verdad?

Restablece a Mónica el

1

Clojure, 185 bytes

#(loop[[n p][(vec(range 2 1e3))0]i %](if(= i 0)p(recur(if-let[q(first(for[i(range 2(n p)):when(=(mod(n p)i)0)]i))][(assoc n p(/(n p)q)(dec p)(+(n(dec p))q))(dec p)][n(inc p)])(dec i))))

Ay, editar un "estado" no es ideal en Clojure. Deberá aumentar el exponente para entradas más grandes.

NikoNyrh
fuente

¿Por qué usaste coincidencia de patrones en el loop? Debería poder perder algunos bytes sin eso.

clismique

Además, es posible que pueda cambiar la firstcosa a una somedeclaración.

clismique

Sin la coincidencia de patrones tuve que repetir recurdos veces, una para cada if-letrama. También (dec i)sería duplicado. somenecesita un predicado, podría usarlo +ya que estamos tratando con números, pero este es un carácter más largo que first. CMIIW

NikoNyrh

1

Java 8, 138 135 bytes

n->{int a[]=new int[++n],s=0,p=0,j=0;for(;j<n;a[j++]=j+1);for(;++s<n;p++)for(j=1;++j<a[p];)if(a[p]%j<1){a[p--]/=j;a[p--]+=j;}return p;}

Explicación:

Pruébalo aquí.

n->{                     // Method with integer as both parameter and return-type
  int a[]=new int[++n],  //  Integer-array with a length of `n+1`
      s=0,               //  Steps-counter (starting at 0)
      p=0,               //  Current position (starting at 0)
      j=0;               //  Index integer (starting at 0)
  for(;j<n;              //  Loop (1) from 0 to the input (inclusive due to `++n` above)
    a[j++]=j+1           //   And fill the array with 2 through `n+2`
  );                     //  End of loop (1)
  for(;++s<n;            //  Loop (2) `n` amount of steps:
      p++)               //    And after every iteration: increase position `p` by 1
    for(j=1;             //   Reset `j` to 1
        ++j<a[p];)       //   Inner loop (3) from 2 to `a[p]` (the current item)
      if(a[p]%j<1){      //    If the current item is divisible by `j`:
        a[p--]/=j;       //     Divide the current item by `j`
        a[p--]+=j;}      //     And increase the previous item by `j`
                         //     And set position `p` two steps back (with both `p--`)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return p;              //  Return the resulting position `p`
}                        // End of method

Kevin Cruijssen
fuente

1

Clojure, 198 193 191 bytes

Esto necesita ser severamente golfizado ...

#(loop[i(vec(range 2(+ % 9)))c 0 p 0](if(= % c)p(let[d(dec p)u(i p)f(some(fn[n](if(=(mod u n)0)n))(range 2(inc u)))e(= u f)](recur(if e i(assoc i d(+(i d)f)p(/ u f)))(inc c)(if e(inc p)d)))))

Golf 1 : guardado 5 bytes cambiando (first(filter ...))a(some ...)

Golf 2 : guardado 2 bytes cambiando (zero? ...)a(= ... 0)

Uso:

(#(...) 10000) => 512

Código sin golf:

(defn prime-ant [n]
  (loop [counter 0
         pos 0
         items (vec (range 2 (+ n 9)))]
    (if (= n counter) pos
      (let [cur-item (nth items pos)
            prime-factor
            (some #(if (zero? (mod cur-item %)) %)
              (range 2 (inc cur-item)))
            equals? (= cur-item prime-factor)]
        (recur
          (inc counter)
          (if equals? (inc pos) (dec pos))
          (if equals? items
            (assoc items
              (dec pos) (+ (items (dec pos)) prime-factor)
              pos (/ cur-item prime-factor))))))))

clismique
fuente

La hormiga principal 🐜

Respuestas:

Alice , 45 bytes

Python 2 , 120 bytes

Octava , 109103101 94 bytes

MATLAB, 130 123 118 117 bytes

JavaScript (ES6), 91 bytes

Manifestación

Haskell , 108 106 94 bytes

TI-BASIC, 108 103 102 98 bytes

MATL , 41 bytes

Explicación

Pyth - 44 bytes

PARI / GP, 87 bytes

Python 2 , 142127 bytes

Mathematica, 118103 bytes

Python 3 , 158 149 133 bytes

PHP, 102 + 1 bytes

R , 123 bytes

C (gcc), 152 148 bytes

Minified

Formado con algunos comentarios.

Función principal para probar

Por mostrar cada paso

Clojure, 185 bytes

Java 8, 138 135 bytes

Clojure, 198 193 191 bytes

Uso:

Código sin golf: