Números desafortunados!

22

Cosas que saber:

Primero, números de la suerte.

Los números de la suerte se generan así:

Toma todos los números naturales:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20...

Luego, elimina cada segundo número.

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39...

Ahora 3está a salvo.

Eliminar cada 3er número:

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49, 51, 55, 59...

Ahora 7está a salvo.

Eliminar cada séptimo número.

Continúe y elimine cada nnúmero, donde nes el primer número seguro después de una eliminación.

La lista final de números seguros son los números de la suerte.


Los números desafortunados se componen de listas separadas de números, que son [U1, U2, U3... Un].

U1 es el primer conjunto de números eliminado de los "candidatos" afortunados, por lo que son:

2, 4, 6, 8, 10, 12, 14, 16, 18, 20...

U2 es el segundo conjunto de números eliminado:

5, 11, 17, 23, 29, 35, 41, 47, 53, 59...

Y así sucesivamente ( U3es la tercera lista, U4es la cuarta, etc.)


Reto:

Su tarea es, cuando se le dan dos entradas my n, generar el mnúmero th en la lista Un.

Ejemplo de entradas y salidas:

(5, 2) -> 29
(10, 1) -> 20

Especificaciones:

  • Su programa debe funcionar mhasta 1e6y nhasta 100.
    • Estás garantizado que ambos my nson enteros positivos.
    • Si tienes curiosidad, U(1e6, 100)= 5,333,213,163. (¡Gracias @pacholik!)
  • Su programa debe calcularlo dentro de 1 día en una computadora moderna razonable.

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

PD: Sería bueno que a alguien se le ocurriera una fórmula general para generarlos. Si tienes una fórmula, ¡por favor, ponla en tu respuesta!

clismique
fuente
En OEIS: A219178 y A255543
Arnauld el
66
Relacionado.
Martin Ender
2
¿Ha implementado código que realmente puede funcionar (1e6,1e6)?
Jonathan Allan
2
Si va a tener un requisito de tiempo, debe especificar el entorno de temporización (como su máquina, una máquina virtual en línea disponible gratuitamente o "una computadora moderna razonable").
Mego
1
¿Es aceptable que la función no funcione para el n=1caso? Como esto es especial, para todos los demás casos, el índice basado en 0 del siguiente número de la suerte es n-1.
Myridium

Respuestas:

1

CJam , 74 bytes

ri0Lri:U{1$W%{1$\(1e>/+}/)+}/2t:A0@{@:B:(_0#):D{D(_A=tD<BD>+}&@)@DU=-}h]1=

Pruébalo en línea! Tiempo de espera para casos más grandes, más sobre las limitaciones de tiempo a continuación.


Explicación:

Nuestro programa pide préstamos descaradamente el código de aditsu para generar una lista de N números de la suerte, reemplazando 1 con un 2 da el incremento en cada fase del tamiz. El código restante disminuye en cada elemento hasta que se encuentra un cero (cortando y agregando una cola no decrementada) y efectivamente cuenta los pasos en cada una de las N fases del tamiz a la vez.

ri                               e# read M
0Lri:U{1$W%{1$\(1e>/+}/)+}/2t:A  e# list steps (also becomes B)
0@                               e# arrange stack [B I M]
{                                e# while M
   @:B                           e#   get current B
   :(                            e#   decrement every element in B
   _0#):D                        e#   find first 0
   {                             e#   if there is a 0
      D(_A=t                     e#     reset that element in B
      D<BD>+                     e#     replace tail after 0
   }&                            e#   end if
   @)                            e#   increment I
   @DU=-                         e#   decrement M if N-th phase of sieve
}h                               e# end loop
]1=                              e# return I

Sincronización:

Si absolutamente debe ejecutar el programa en el navegador para números más grandes, puede usar este intérprete y permitir que el script continúe si se le solicita, pero esto puede ser demasiado lento para calificar. Usar ( M , N ) = (100,100) toma ~ 247s. La iteración de los programas es relativamente lineal en términos de M , por lo que la computación (1e6,100) podría tomar ~ 29 días.

Usando el intérprete de shell en una PC, el programa calcula (100,100) en ~ 6s y calcula (1e4,100) en ~ 463s. El programa debería poder calcular (1e6,100) en ~ 13-17hrs. En este caso, supondré que el programa califica.

Tenga en cuenta que todos los tiempos se redondearon tanto en las mediciones como en los cálculos.

Linus
fuente
7

Perl, 87 85 82 81 bytes

Incluye +4 para -pX

Dé entrada en STDIN como una línea con n primero (observe que este es el reverso del orden sugerido en el desafío). Entonces para calcular U(1000000, 100):

unlucky.pl <<< "100 1000000"

Algoritmo basado en aditsu Es números de la suerte responder a la complejidad del tiempo es O(n^2)por lo que es más rápido para la escala requerida. El 100, 1000000caso cede 5333213163en 0.7 segundos. Debido a los problemas que tiene Perl con la do$0recursión basada, utiliza mucha memoria. Reescribirlo como una función haría que la memoria se usara, O(n)pero es un número de bytes más largo

unlucky.pl:

#!/usr/bin/perl -pX
$_=$a{$_}||=/\d+$/>--$_?2*$&+$^S:($_=$_.A.(do$0,$^S?0|$&+$&/~-$_:$&*$_-1),do$0)

Esto funciona como se muestra, pero usa literal ^Spara obtener la puntuación reclamada.

No conozco ningún uso anterior de $^Sperlgolf.

Ton Hospel
fuente
¿Pero cuánto dura esto (1e6,100)?
Myridium
@Myridium Debido a la explosión de memoria causada por do$0él, es básicamente inalcanzable en cualquier computadora realista. Pero si esa memoria existiera alrededor de 2 años. Realmente no he escrito y probado una versión normal basada en subrutinas, pero esperaría que termine en unos meses y se ejecute incluso en computadoras con muy poca memoria. Por lo tanto, es bueno que estos valores no estén en el rango requerido para este desafío.
Ton Hospel
¿No es el desafío calcular (1e6,100)dentro de un día? ¿Qué quieres decir con que estos valores no son obligatorios?
Myridium
@Myridium Observe que en mi programa ny mse dan en orden inverso. La 100 1000000entrada calcula U(1000000, 100)y da 5,333,213,163en 0.7 segundos. Es, con mucho, el programa más rápido de estos actualmente publicado
Ton Hospel
Ah, bueno, esperaba (100,1e6)ser mucho más rápido que (1e6,100)eso, ¡y pensé que esta era la explicación de los rápidos 0.7 segundos!
Myridium
7

Pitón 3, 170

from itertools import*
def L(n,k=1):
 if n<2:yield from count(2+k,2)
 t=L(n-1);l=next(t)
 for i in t:
  n+=1
  if(n%l>0)==k:yield i
U=lambda m,n:sum(islice(L(n,0),m-1,m))

La función L genera la fila de posibles números de la suerte (si k es verdadero) o Un (si es falso). Evaluado perezosamente (por lo que no tengo que generar n-1 listas infinitas si quiero Un ).

Función de ejecución T .

Velocidad

U (1,000,000; 100) tarda aproximadamente 1h 45min en ejecutarse en mi máquina con PyPy. Sospecho unas cuatro horas con CPython. (Sí, 4h 20min para ser precisos).

Si usara una lista en lugar de generadores, podría ganar algo de velocidad, pero necesitaría una lista de mayor tamaño que Python me permite. Y si lo hiciera, necesitaría docenas de gigabytes de RAM.


Sí, y U (1,000,000; 100) = 5,333,213,163 .

pacholik
fuente
Debería ser válido ahora.
clismique
3

Haskell

No se puede calcular para n = 1: 175160 bytes

Cuando se compiló, mi computadora tardó 2h 35m en calcular una entrada para (1000000,100)usar esto:

n#s=y:(n#p)where y:p=drop(n-1)s
n%s=f n s$[]where f n s=(take(n-1)s++).f n(drop n s) 
l 2=[1,3..]
l m=((l$m-1)!!(m-2))%(l$m-1)
m?n=(((l n)!!(n-1))#(l$n))!!(m-1)

Traté de deshacerme de los wheremódulos, pero parecen afectar la velocidad y no estoy seguro de por qué ... Pero creo que hay más poda que hacer aquí.

El método a utilizar es m?npara consultar la respuesta dada una my n.

Sin golf

everynth n xs = y:(everynth n ys) -- Takes every nth element from a list 'xs'
  where y:ys = drop (n-1) xs

skipeverynth n xs = f' n xs $ []  -- Removes every nth element from a list 'xs'
  where f' n xs = (take (n-1) xs ++) . f' n (drop n xs) 

l 2 = [1,3..] -- The base case of the list of lucky numbers for 'n=2'
l m = skipeverynth ((l$m-1)!!(m-2)) (l$m-1) -- Recursively defining next case as being the last one with every 'ath' element skipped. Here, 'a' is the (m-1)th elemnent of the (l (m-1)) list.
ul m = everynth ((l m)!!(m-1)) (l$m) -- This is not used other than to compute the final, required unlucky number list. It picks out every 'ath' element.

ans m n = (ul n)!!(m-1) -- The function giving the answer.

Creo que es posible combinar las funciones 'skipeverynth' y 'everynth' en una sola función que devuelve un par.

Utilicé el código de esta amable persona para omitir cada enésimo elemento. Lo hice algunas veces, pero siempre fue mucho más ineficiente y no podía entender por qué.

Capaz de calcular para todos los n: 170 bytes

Esto es básicamente lo mismo, pero se maxtuvieron que incluir un par de funciones para manejar el caso especial de n=1.

n#s=y:(n#p)where y:p=drop(n-1)s
n%s=f n s$[]where f n s=(take(n-1)s++).f n(drop n s) 
l 1=[1..]
l m=((l$m-1)!!(max 1$m-2))%(l$m-1)
m?n=(((l n)!!(max 1$n-1))#(l$n))!!(m-1)
Miridio
fuente
2

R 82 bytes

f<-function(m,n){a=1:2e8
i=1
while(i<n){a=c(0,a)[c(F,rep(T,i))]
i=i+1}
a[(n+1)*m]}

Uso

f(5,2)
Returns 29

Esto debe tener un vector lo suficientemente grande para comenzar, por lo que quedan suficientes números para devolver el valor. El vector creado ya es de aproximadamente 800Mb y la función puede manejar hasta m = 1e4 yn = 100, por lo que todavía está muy por debajo del objetivo.

Para crear un vector lo suficientemente grande como para calcular f (1e6,100) se necesitaría un vector inicial de 1: 2e10. Debido a los procedimientos de asignación de datos de Rs, esto crea un vector> 70 Gb que no se puede ejecutar en ninguna computadora que conozca, aunque se ejecutaría el código.

Error: cannot allocate vector of size 74.5 Gb

Como referencia, f (1e4,100) se ejecuta en aproximadamente 30 segundos. Basado en esto y en un par de pruebas más pequeñas, f (1e6,100) tomaría aproximadamente una hora.

gtwebb
fuente
Marcar su respuesta como no competitiva no lo excusa de no cumplir con los requisitos del desafío.
Mego
@Mego He visto muchas respuestas que no cumplen con los requisitos (hay al menos 1 en este desafío). Lo codifiqué y siento que cumple con el espíritu de la solicitud de codificación, también dije claramente dónde se quedó corto. Además, como mencionas en tus comentarios a la pregunta, no indica qué tipo de computadora necesita probar. Estoy seguro de que hay computadoras que pueden escribir 7 Gb en la memoria y procesarlas. En el que estaba no podía hacerlo, pero todavía quería publicar y pensé que la declaración clara era un compromiso válido.
gtwebb
Tenemos una política clara sobre las respuestas que no cumplen con la especificación del desafío . Dicho esto, no estoy seguro de por qué calificó su respuesta como no competitiva. Si entiendo correctamente, esto debería funcionar con suficiente memoria, pero no podría probarlo porque no tiene suficiente RAM. ¿Es eso correcto?
Dennis
1
1. Esta política se está aplicando, pero cuatro moderadores no pueden probar todas las respuestas en el sitio. Si encuentra un envío que no cumple con las reglas, márquelo para la atención del moderador para que podamos echarle un vistazo. 2. No tienes que aprender un idioma de golf para participar. Los lenguajes de producción como R son igualmente bienvenidos. Publico respuestas de Python de forma regular.
Dennis
1
3. La especificación no menciona ningún límite de memoria, pero hay un límite de tiempo de 24 horas. En ausencia de una computadora con 70 GiB (o quiso decir giga bits ) para probar esto, es difícil determinar si esta respuesta es válida o no. Sugiero que intentes extrapolar el tiempo de ejecución lo mejor que puedas. Si es menos de un día, elimine el encabezado no competitivo e incluya su extrapolación en la publicación. Si lleva más tiempo, su envío debe optimizarse o eliminarse.
Dennis
1

Raqueta 332 bytes

(λ(N m n)(let loop((l(filter odd?(range 1 N)))(i 1))(define x (list-ref l i))(if(= i (sub1 n))
(begin(set! l(for/list((j(length l))#:when(= 0(modulo(add1 j)x)))(list-ref l j)))(list-ref l(sub1 m)))
(begin(set! l(for/list((j(length l))#:unless(= 0(modulo(add1 j) x)))(list-ref l j)))(if(>= i(sub1 (length l)))l
(loop l(add1 i)))))))

Versión sin golf:

(define f
  (λ(N m n)
    (let loop ((l (filter odd? (range 1 N))) (i 1))
      (define x (list-ref l i))
      (if (= i (sub1 n))
          (begin (set! l (for/list ((j (length l)) 
                                   #:when (= 0 (modulo (add1 j) x)))
                           (list-ref l j)))
                 (list-ref l (sub1 m)))
          (begin (set! l (for/list ((j (length l)) 
                                   #:unless (= 0 (modulo (add1 j) x)))
                           (list-ref l j)))
                 (if (>= i (sub1 (length l)))
                     l
                     (loop l (add1 i))))))))

Pruebas:

(f 100 5 2)

Salida:

29
rnso
fuente
1

Clojure, 221 bytes

Muy largo pero maneja el estuche (f 1). Sin ese caso especial, era de 183 bytes. Esto fue demasiado esfuerzo para no publicarlo.

(defn f([n](if(< n 2)(take-nth 2(drop 2(range)))(f n 1(take-nth 2(rest(range))))))([n i c](if (< n 2)c(let[N(first(drop i c))F #((if(= 2 n)= >)(mod(inc %)N)0)](f(dec n)(inc i)(filter some?(map-indexed #(if(F %)%2)c)))))))

Resultados de muestra:

(pprint (map #(take 10 (f %)) (range 1 10)))
((2 4 6 8 10 12 14 16 18 20)
 (5 11 17 23 29 35 41 47 53 59)
 (19 39 61 81 103 123 145 165 187 207)
 (27 57 91 121 153 183 217 247 279 309)
 (45 97 147 199 253 301 351 403 453 507)
 (55 117 181 243 315 379 441 505 571 633)
 (85 177 277 369 471 567 663 757 853 949)
 (109 225 345 465 589 705 829 945 1063 1185)
 (139 295 447 603 765 913 1075 1227 1377 1537))

1000000 100 caso se calculó en aproximadamente 4,7 horas, al menos no se bloqueó.

java -jar target\stackoverflow-0.0.1-SNAPSHOT-standalone.jar 1000000 100
5333213163
"Elapsed time: 1.7227805535565E7 msecs"
NikoNyrh
fuente