Números azarados!

22

Coisas a saber:

Primeiro, números da sorte.

Os números da sorte são gerados da seguinte forma:

Pegue todos os números naturais:

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

Em seguida, remova cada segundo número.

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

Agora 3está seguro.

Remova cada terceiro número:

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

Agora 7está seguro.

Remova todos os sétimos números.

Continue e remova todo nnúmero de th, onde nestá o primeiro número seguro após uma eliminação.

A lista final de números seguros são os números da sorte.

Os números azarados são compostos por listas separadas de números [U1, U2, U3... Un].

U1 é o primeiro conjunto de números removido dos "candidatos" sortudos, então eles são:

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

U2 é o segundo conjunto de números removido:

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

E assim por diante ( U3a terceira lista, U4a quarta etc.)

Desafio:

Sua tarefa é, ao receber duas entradas me ngerar o mnúmero th na lista Un.

Exemplos de entradas e saídas:

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

Especificações:

  • Seu programa deve funcionar para maté 1e6e naté 100.
    • Você tem a garantia de que ambos me nnúmeros inteiros positivos.
    • Se você está curioso, U(1e6, 100)= 5,333,213,163. (Obrigado @pacholik!)
  • Seu programa deve calcular isso dentro de 1 dia em um computador moderno razoável.

Isso é código-golfe , então o código mais curto em bytes vence!

PS: Seria bom se alguém apresentasse uma fórmula geral para gerá-las. Se você tem uma fórmula, coloque-a na sua resposta!

code-golf math sequence clismique
fonte
No OEIS: A219178 e A255543
Arnauld
6
Relacionado.
Martin Ender
2
Você implementou código que pode realmente executar (1e6,1e6)?
Jonathan Allan
2
Se você precisar de um tempo, precisará especificar o ambiente de tempo (como sua máquina, uma VM on-line disponível gratuitamente ou "um computador moderno razoável").
Mego 28/09
1
É aceitável que a função não funcione para o n=1caso? Como isso é especial - para todos os outros casos, o índice baseado em 0 do próximo número da sorte é n-1.
Myridium 28/09

Respostas:

1

CJam , 74 bytes

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

Experimente online! Tempo limite para casos maiores, mais restrições de tempo abaixo.

Explicação:

Nosso programa empresta vergonhosamente o código do aditsu para gerar uma lista de N números da sorte, substituindo 1 por 2 fornece o incremento em cada fase da peneira. O código restante diminui em todos os elementos até que um zero seja encontrado (fatiando e acrescentando uma cauda não decrementada) e efetivamente conta os passos em cada uma das N fases da peneira de uma só 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

Cronometragem:

Se você precisar absolutamente executar o programa no navegador para obter números maiores, poderá usar esse intérprete e permitir que o script continue se solicitado, mas isso pode ser muito lento para se qualificar. Usar ( M , N ) = (100.100) leva ~ 247s. A iteração dos programas é relativamente linear em termos de M ; portanto, a computação (1e6.100) pode levar ~ 29 dias.

Usando o interpretador de shell em um PC, o programa calcula (100.100) em ~ 6s e calcula (1e4.100) em ~ 463s. O programa deve poder calcular (1e6.100) em ~ 13-17 horas. Nesse caso, assumirei que o programa está qualificado.

Observe que todos os horários foram arredondados nas medidas e nos cálculos.

Linus
fonte
7

Perl, 87 85 82 81 bytes

Inclui +4 para -pX

Dê entrada no STDIN como uma linha com n primeiro (observe que isso é o inverso da ordem sugerida no desafio). Então, para calcular U(1000000, 100):

unlucky.pl <<< "100 1000000"

Algoritmo baseado nos números da sorte do aditsu respondem A complexidade do tempo é O(n^2)muito rápida para o intervalo necessário. O 100, 1000000caso dá 5333213163em 0,7 segundos. Devido aos problemas que o perl tem com a do$0recursão baseada, ele usa muita memória. Reescrevê-lo como uma função faria a memória usar, O(n)mas é um número de bytes mais longo

unlucky.pl:

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

Isso funciona como mostrado, mas use literal ^Spara obter a pontuação reivindicada.

Não conheço nenhum uso anterior do $^Sperlgolf.

Ton Hospel
fonte
Mas quanto tempo isso leva (1e6,100)?
Myridium 30/09/16
@Myridium Devido à explosão de memória causada por do$0ele, é basicamente inacessível em qualquer computador realista. Mas se essa memória existisse cerca de 2 anos. Eu realmente não escrevi e testei uma versão normal baseada em sub-rotinas, mas esperaria que isso terminasse em alguns meses e funcionasse mesmo em computadores com muito pouca memória. Portanto, é bom que esses valores não estejam no intervalo necessário para esse desafio.
Ton Hospel 30/09/16
O desafio não é calcular (1e6,100)dentro de um dia? Como assim, esses valores não são necessários?
Myridium
@Myridium Observe isso no meu programa ne msão fornecidos em ordem inversa. A 100 1000000entrada calcula U(1000000, 100)e dá 5,333,213,163em 0,7 segundos. É de longe o programa mais rápido
dentre
Ah, tudo bem, eu esperava (100,1e6)ser muito mais rápido do que (1e6,100), e pensei que essa fosse a explicação para o relâmpago 0,7 segundos!
Myridium 30/09/16
7

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

A função L gera a linha de possíveis números da sorte (se k for Verdadeiro) ou Un (se Falso). Avaliada preguiçosamente (para que eu não precise gerar listas infinitas n-1 se quiser Un ).

Função de executar U .

Rapidez

U (1.000.000; 100) leva cerca de 1h 45min para executar na minha máquina com o PyPy. Eu suspeito que cerca de quatro horas com CPython. (Sim, 4h 20min para ser mais preciso.)

Se eu usasse uma lista em vez de geradores, poderia ganhar velocidade, mas precisaria de uma lista de tamanho maior do que o Python me permite. E se tivesse, precisaria de dezenas de gigabytes de RAM.

Sim e U (1.000.000; 100) = 5.333.213.163 .

pacholik
fonte
Deve ser válido agora.
clismique 27/09/16
3

Haskell

Não é possível calcular para n = 1: 175 160 bytes

Quando compilado, o meu computador demorou 2h 35m para calcular uma entrada do (1000000,100)uso deste:

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)

Tentei livrar os wheremódulos, mas eles parecem afetar a velocidade e não sei por que ... Mas acho que há mais podas a serem feitas aqui.

O método a ser usado é m?npara consultar a resposta dada um me n.

Ungolfed

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.

Acho que é possível combinar as funções 'skipeverynth' e 'everynth' em uma única função que retorna um par.

Eu usei o código dessa pessoa gentil para pular cada enésimo elemento. Fiz isso algumas vezes, mas sempre foi muito mais ineficiente e não conseguia descobrir o porquê.

Capaz de calcular para todos os n: 170 bytes

Isso é basicamente o mesmo, mas algumas maxfunções tiveram que ser utilizadas para lidar com o 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)
Myridium
fonte
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

Isso precisa ter um vetor grande o suficiente para começar, para que haja números suficientes para retornar o valor. O vetor criado já tem cerca de 800 Mb e a função pode suportar até m = 1e4 e n = 100, ainda muito aquém do objetivo.

Para criar um vetor grande o suficiente para calcular f (1e6.100) seria necessário um vetor inicial de 1: 2e10. Devido aos procedimentos de alocação de dados de Rs, isso cria um vetor> 70Gb que não pode ser executado em nenhum computador que conheço, embora o código seja executado.

Error: cannot allocate vector of size 74.5 Gb

Para referência, f (1e4.100) é executado em aproximadamente 30 segundos. Com base nisso e em alguns testes menores, f (1e6.100) levaria cerca de uma hora.

gtwebb
fonte
Marcar sua resposta como não concorrente não a dispensa de atender aos requisitos do desafio.
Mego2
O @Mego já viu muitas respostas que não atendem aos requisitos (há pelo menos uma outra neste desafio). Eu o codifiquei e sinto que ele atende ao espírito da solicitação de codificação, também afirmei claramente onde ficou aquém. Além disso, como você mencionou em seus comentários à pergunta, ela não indica em que tipo de computador é necessário testar. Tenho certeza de que existem computadores por aí que podem gravar 7 Gb na memória e processá-los. O que eu estava fazendo não podia fazê-lo, mas eu ainda queria postar e pensei que a declaração clara era um compromisso válido.
Gtwebb #
Temos uma política clara sobre respostas que não atendem à especificação do desafio . Dito isto, não sei por que você rotulou sua resposta como não concorrente. Se bem entendi, isso deve funcionar com memória suficiente, mas você não pode testá-lo porque não possui RAM suficiente. Isso está correto?
Dennis
1
1. Esta política está sendo aplicada, mas quatro moderadores não podem testar todas as respostas no site. Se você encontrar um envio que não está em conformidade com as regras, sinalize para atenção do moderador para que possamos dar uma olhada. 2. Você não precisa aprender um idioma de golfe para participar. Linguagens de produção como R são igualmente bem-vindas. Eu posto respostas Python a mim mesmo regularmente.
Dennis
1
3. A especificação não menciona nenhum limite de memória, mas há um limite de 24 horas. Na ausência de um computador com 70 GiB (ou você quis dizer giga bits ) para testar isso, é difícil determinar se essa resposta é válida ou não. Sugiro tentar extrapolar o tempo de execução da melhor maneira possível. Se for menos de um dia, remova o cabeçalho não concorrente e inclua sua extrapolação na postagem. Se demorar mais, seu envio deve ser otimizado ou removido.
Dennis
1

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

Versão não destruída: 

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

Teste: 

(f 100 5 2)

Saída: 

29
rnso
fonte
1

Clojure, 221 bytes

Muito longo, mas lida com o caso (f 1). Sem esse caso especial, eram 183 bytes. Foi um esforço demais para não ser publicado.

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

Saídas de amostra:

(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 foi calculado em cerca de 4,7 horas, pelo menos não travou.

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