Su tarea es implementar la secuencia de enteros A130826 :
un n es el número entero positivo más pequeño de tal manera que un n - n es un múltiplo entero de 3 y dos veces el número de divisores de (a n - n) / 3 da n º plazo en las primeras diferencias de la secuencia producida por el Flavius Josefo tamiz.
Perdido todavía? Bueno, en realidad es bastante fácil.
El tamiz Flavius Josephus define una secuencia entera de la siguiente manera.
Comience con la secuencia de enteros positivos y establezca k = 2 .
Retirar cada k ésimo número entero de la secuencia, empezando por el k ésimo .
Incremente ky regrese al paso 2.
f n es el n º entero (1-indexado) que nunca se retira.
Si, como de costumbre, σ 0 (k) denota el número de divisores positivos del entero k , podemos definir a n como el entero positivo más pequeño de modo que 2σ 0 ((a n - n) / 3) = f n + 1 - f n .
Reto
Escriba un programa o función que tome un entero positivo n como entrada e imprima o devuelva un n .
Aplican reglas estándar de código de golf . ¡Que gane el código más corto!
Ejemplos trabajados
Si eliminamos cada segundo elemento de los enteros positivos, nos queda con
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...
Después de eliminar cada tercer elemento del resto, obtenemos
1 3 7 9 13 15 19 21 25 27 31 33 37 39 ...
Ahora, quitando cada cuarto, luego quinto y luego sexto elemento
1 3 7 13 15 19 25 27 31 37 39 ...
1 3 7 13 19 25 27 31 39 ...
1 3 7 13 19 27 31 39 ...
1 3 7 13 19 27 39 ...
La última fila muestra los términos f 1 a f 7 .
Las diferencias de los elementos consecutivos de estos términos son
2 4 6 6 8 12
Dividiendo estas diferencias hacia adelante por 2 , obtenemos
1 2 3 3 4 6
Estos son los recuentos de divisores objetivo.
- 4 es el primer entero k tal que σ 0 ((k - 1) / 3) = 1 . De hecho, σ 0 (1) = 1 .
- 8 es el primer entero k tal que σ 0 ((k - 2) / 3) = 2 . De hecho, σ 0 (2) = 2 .
- 15 es el primer entero k tal que σ 0 ((k - 3) / 3) = 3 . De hecho, σ 0 (4) = 3 .
- 16 es el primer entero k tal que σ 0 ((k - 4) / 3) = 3 . De hecho, σ 0 (4) = 3 .
- 23 es el primer entero k tal que σ 0 ((k - 5) / 3) = 4 . De hecho, σ 0 (6) = 4 .
- 42 es el primer entero k tal que σ 0 ((k - 6) / 3) = 6 . De hecho, σ 0 (12) = 6 .
Casos de prueba
n a(n)
1 4
2 8
3 15
4 16
5 23
6 42
7 55
8 200
9 81
10 46
11 119
12 192
13 205
14 196622
15 12303
16 88
17 449
18 558
19 127
20 1748
21 786453
22 58
23 2183
24 3096
25 1105
26 786458
27 12582939
28 568
29 2189
30 2730
fuente
Respuestas:
Jalea,
30292725 bytesAhorré 2 bytes gracias a @Dennis que me notificó
Æd
y otros 2 bytes por combinar las dos cadenas.Pruébalo en línea!
Esta fue probablemente la más divertida que he tenido con Jelly. Comencé desde la segunda línea, que calcula f n a partir de n usando la fórmula en OEIS, y es bastante hermosa.
Explicación
fuente
Python 2 ,
121119118 bytesEl tiempo de ejecución debe ser aproximadamente O (16 n ) con uso de memoria O (4 n ) . Reemplazar
4**n
con5<<n
, lo que creo que es suficiente, mejoraría dramáticamente esto, pero no estoy convencido de que funcione para valores arbitrariamente grandes de n .Pruébalo en línea!
Comportamiento asintótico y límites superiores de una n
Defina b n como (a n - n) / 3 , es decir, el entero positivo más pequeño k tal que σ 0 (k) = ½ (f n + 1 - f n ) .
Como se señaló en la página OEIS, f n ~ ¼πn 2 , entonces f n + 1 - f n ~ ¼π (n + 1) 2 - ¼πn 2 = ¼π (2n + 1) ~ ½πn .
De esta manera, ½ (f n + 1 - f n ) ~ ¼πn . Si el número real es un primo p , el entero positivo más pequeño con p divisores es 2 p-1 , por lo que b n puede aproximarse por 2 c n , donde c n ~ ¼πn .
Por lo tanto, b n <4 n se mantendrá durante n suficientemente grande , y dado que 2 ¼πn <2 n << (2 n ) 2 = 4 n , estoy seguro de que no hay contraejemplos.
Cómo funciona
Esto establece algunas referencias para nuestro proceso iterativo.
n es la entrada del usuario: un entero positivo.
r es la lista [1, ..., 4 n - 1] .
s es una copia de r .
Repetir la lista una vez con
r*1
crea una copia superficial, por lo que modificar s no modificará r .d se inicializa como la tupla (s) .
Este primer valor no es importante. Todos los demás tendrán recuentos de divisores de enteros positivos.
Para cada entero k de 1 a 4 n - 1 , hacemos lo siguiente.
del s[k::k+1]
toma cada entero (k + 1) th en s , comenzando con el (k + 1) th , y elimina esa porción de s .Esta es una forma directa de almacenar un intervalo inicial del tamiz Flavio Josefo en s . Se calculará mucho más que las requeridas n + 1 términos iniciales, pero utilizando un único
for
bucle para actualizar ambos s y d ahorra algunos bytes.d+=sum(k%j<1for j in r)*2,
cuenta cuántos elementos de r dividen k de manera uniforme y agrega 2σ 0 (k) a d .Como d se inicializó como una tupla singleton, 2σ 0 (k) se almacena en el índice k .
Esto encuentra el primer índice de f n + 1 - f n en d , que es el k más pequeño de modo que 2σ 0 (k) = f n + 1 - f n , luego calcula a n como 3k + 1 e imprime el resultado.
fuente
Java 8,
336,305,303,287,283279 bytes57 bytes eliminados gracias a Kritixi Lithos
Golfed
Sin golf
fuente
int
es más corto que el usojava.util.Scanner
. Pero incluso si está utilizando el escáner, puede hacerSystem.out.print(h(new java.util.Scanner().nextInt()))
y eliminar la línea anteriorint h()
, puedes cambiarlo aint v = (g(k,k)-g(k,k-1))/2,u = 0,t = 1;
. Puede cambiar su declaración if (que está dentro de su ciclo for) deif(t%i==0)
aif(t%i<1)
g
para volver utilizando operadores ternarios algo así comoreturn s==0?N+1:g(s-1,N+N/2)
-ishMathematica,
130116106103 byteso
Terminó siendo casi idéntico al código Jelly de @ Pietu1998 ...
Explicación
Catch
lo que seaThrow
-ed (arrojado)Bucle infinito;
k
comienza1
e incrementa cada iteración.Asignar
f
:Encuentra
{1, 2, ... , n}
. Revertirla.Una función que emite ceil (n1 / n2 + 1) * n2
Asigne
f
una función que aplique recursivamente la función anterior a la lista de los dos pasos anteriores, usando cada salida como la primera entrada y cada elemento de la lista como la segunda entrada. La "salida" inicial (primera entrada) es el primer elemento de la lista.Compruebe si dos veces el número de divisores de
k
es igual a f (n + 1) - f (n).Si la condición es
True
,Throw
el valor dek
. De lo contrario, continúe en bucle.Multiplique la salida por 3 y agregue n.
Versión de 130 bytes
fuente
Perl 6 ,
154149136107 bytesSin golf:
fuente
05AB1E ,
353439 bytesSe ve horrible, al igual que el rendimiento en tiempo de ejecución. La entrada tarda varios segundos en obtener valores pequeños. No intentes números como el 14; eventualmente encontrará el resultado, pero llevaría años.
Explicación
Funciona como 2 programas llamados secuencialmente. El primero calcula F n + 1 - F n y el segundo determina un n basado en su definición, utilizando un enfoque de fuerza bruta.
F n + 1 : F n se evalúa para cada iteración aunque sea invariante en bucle. Hace que el tiempo del código sea ineficiente, pero lo hace más corto.
Pruébalo en línea!
fuente
žHL
) y luego filtra los valores que no satisfacen las restricciones de tamiz. Creo que la primera parte de este programa debería reescribirse por completo con un enfoque completamente diferente para que sea golfable.given enough time and memory
, ya que ya vi varias respuestas sobre otras preguntas que corrieron tan lentamente que era casi imposible decir si produjeron el resultado correcto o no. Por esta razón, puse el cálculo del tamiz a un lado del ciclo y me costó 2 bytes.