História:

Lucy perguntou a George qual era o seu número da sorte. Após alguma contemplação, George respondeu que tinha vários números da sorte. Após uma breve confusão, Lucy perguntou a George quais neram seus primeiros números da sorte. George então pediu a você, seu amigo, que escrevesse um programa para ele fazer o trabalho.

O desafio:

Você escreverá um programa / função que receberá do argumento de entrada / função padrão uma string ou um número inteiro n. O programa / função retornará / produzirá os primeiros n números da sorte . Os números da sorte são definidos através de uma peneira da seguinte forma.

Comece com os números inteiros positivos:

1, 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, ...

Agora remova cada segundo número:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

O segundo número restante é 3 , então remova todos os terceiros números:

1, 3, 7, 9, 13, 15, 19, 21, 25, ...

Agora, o próximo número restante é 7 , então remova todo sétimo número:

1, 3, 7, 9, 13, 15, 21, 25, ...

Em seguida, remova todos os nonos números e assim por diante. A sequência resultante são os números da sorte.

Ganhando:

Como de costume no codegolf, o menor número de bytes vence.

Como de costume, as submissões usando brechas padrão são desqualificadas.

Python 2, 79

n=input()
L=range(1,2**n)
for r in L:r+=r<2;map(L.remove,L[r-1::r])
print L[:n]

A mágica de iterar sobre uma lista enquanto o loop a modifica!

A lista Lcomeça com todos os números inteiros 1para um valor suficientemente alto. O código itera sobre cada elemento rde L, obtendo a sub-lista de todos ros elementos enésimo e removendo cada um desses valores. Como resultado, os valores removidos não são repetidos. No final, imprima os primeiros nelementos.

A expressão map(A.remove,B)é um truque que estou esperando há muito tempo para usar. Ele chama A.removecada elemento de B, o que faz com que todos os elementos Bsejam removidos A. Efetivamente, leva a diferença da lista, embora exija Buma sub-lista de A. Requer o Python 2, já que o Python 3 não avaliaria o mapa.

O primeiro loop precisa ser especial para converter rde 1para 2, comor+=r<2 .

O limite superior suficientemente alto de 2**ntorna o programa muito lento para valores grandes de n. Usar n*n+1basta, mas custa um personagem. Observe que n*nnão funciona n=1.

Haskell, 71 69 bytes

s(n:k)p=n:s[m|(i,m)<-zip[p..]k,i`mod`n>0](p+1)
f n=take n$1:s[3,5..]3

Define uma função f. A expressão é 1:s[3,5..]3avaliada para a lista infinita de números da sorte e fsimplesmente pega o primeiro ndeles take n.

f 20
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]

Eu poderia raspar 5 bytes da peneira usando uma compreensão de lista paralela

s(n:k)p=n:s[m|m<-k|i<-[p..],i`mod`n>0](p+1)

mas isso exigiria passar o sinalizador do compilador -XParallelListComppara o GHC para ativar a extensão.

Explicação da peneira

s(n:k)p=               -- Sieving a list with head n and tail k with accumulator p is
 n:                    -- the head n, followed by
  s[m|                 -- the result of sieving the list of numbers m
    (i,m)<-zip[p..]k,  -- where (i,m) is drawn from [(p,k_0),(p+1,k_1),(p+2,k_2),..] and
    i`mod`n>0]         -- i does not divide n,
   (p+1)               -- using p+1 as the accumulator

A ideia básica é que s(n:k)pproduza o (p-1)número da sorte n, diminua cada nnúmero da cauda infinita k(compensado por ppara contabilizar os números produzidos anteriormente) e retorne a essa lista com acumulador (p+1). Em f, inicializamos o processo com os números ímpares começando de 3e aderindo 1à frente, obtendo exatamente os números da sorte.

Python 2, 71 69 67

No começo, eu pensei que isso seria um grande desafio para o fatiamento de array do Python. No entanto, encontrei um obstáculo quando descobri que fatias com uma etapa diferente de 1 só podem ter outra fatia de comprimento idêntico atribuída a elas. Mas, depois de pesquisar no "python remove slice", minha fé foi restaurada: encontrei uma deldeclaração descolada que faz o truque perfeitamente.

n=input()
l=range(n*n+9)
for v in l:del l[v&~1::v or 2]
print l[:n]

Versão antiga

n=input()
l=range(1,n*n+9)
for v in l:del l[v-1%v::v+1/v]
print l[:n]

-2 bytes graças ao Sp3000.

> <> , 121 114 111 bytes

i2+:&:*1\
:})?v:2+>l{
nao2\r~1
)?vv>1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1
3.\ ff+
!?:<]-1v
~]{43. >

Eu tenho apenas algumas palavras para dizer ...

... "Argh, meu cérebro dói."

Explicação

> <> é uma linguagem de programação esotérica 2D e definitivamente não é adequada para esta tarefa, devido à falta de matrizes. De fato, o único tipo de dado em> <> é uma estranha mistura de int / float / char, e tudo acontece em uma pilha de pilhas.

Aqui está o resumo:

Line 1:            i2+:&:*1\

i2+:&              Read a char as input (n) and add 2, copying n+2 into the register
:*                 Duplicate and multiply, giving (n+2)^2 on the stack
1\                 Push 1 and go to the next line

Line 2:            >l{:})?v:2+

l{:})?v            Go to the next line if the stack's length is greater than (n+2)^2
:2+                Otherwise duplicate the top of the stack and add 2 to it

Line 3:            \r~1nao2

r~                 Reverse the stack and pop; stack contains the first (n+2)^2 odd integers
1nao               Print 1 (special case)
2\                 Push 2 (let's call this "i" for "iterations") and go to the next line

Line 4:            >1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1)?vv

1+                 Increment i
:&:&=?;            If i is equal to n+2 (+2 because we started at 2), halt
:[{::nao}]$}       Print the i-th element down (the next lucky number) and also
                   copy it to the top of the stack, while moving i to the bottom
l1-[               Move everything but i to a new stack
0                  Push 0 (let's call this "r" for recursion depth)

Sieve loop:

1+                 Increment r
}:l3-$%$l1-@@-{$[  Move everything up to the last element to be sieved out to a new stack
{~                 Remove said last element
1)?vv              If the length is 1, go to line 6 (sieving complete)
                   Otherwise go to line 5, which repeats this sieve loop by teleporting

Line 6:            :?!v1-]

:?!v1-]            Keep unrolling and decrementing r until r is 0

Line 7:            >~]{43.             

~]                 Pop r and unroll once more (to the stack where i waits)
43.                Loop, performing everything from line 4 all over again

Aqui está um exemplo simulado que demonstra aproximadamente como a kpeneira funciona (eis o número da sorte com o qual peneiramos):

[[15 13 11 9 7 5 3 1 k=3 r=0]]     -- move -->
[[15 13] [11 9 7 5 3 1 k=3 r=1]]   -- pop  -->
[[15 13] [9 7 5 3 1 k=3 r=1]]      -- move -->
[[15 13] [9 7] [5 3 1 k=3 r=2]]    -- pop  -->
[[15 13] [9 7] [3 1 k=3 r=2]]      -- move -->
[[15 13] [9 7] [3 1] [k=3 r=3]]    -- pop  -->
[[15 13] [9 7] [3 1] [r=3]]        (now we unroll)

CJam - 25

Lri{1$W%{1$\(1e>/+}/)+}/p

Experimente online

Explicação:

Essa implementação não remove números sucessivamente de uma matriz, mas calcula cada número com base em quantos teriam sido removidos antes dela.
Para cada índice i (de 0 a n-1) e cada número da sorte anterior l, em ordem inversa, incrementamos i em i / (l-1), exceto por l = 1, usamos 1 em vez de 0 e também adicionamos 1 no final.
Por exemplo, para i = 4, temos os 4 primeiros números, [1 3 7 9] e calculamos:
4 + 4 / (9-1) = 4
4 + 4 / (7-1) = 4
4 + 4 / (3 -1) = 6
6 + 6/1 = 12
12 + 1 = 13

L              empty array - the first 0 lucky numbers :)
ri             read and convert to integer (n)
{…}/           for each number (i) from 0 to n-1
    1$         copy the previous array
    W%         reverse the order
    {…}/       for each array element (l)
        1$     copy i
        \(     swap with l and decrement l
        1e>    use 1 if l=1
        /+     divide and add to i
    )+         increment and add the new lucky number to the array
p              pretty print

Pitão: 23 22 bytes

<u-G%@GhH+0GQ%2r1^hQ2Q

Experimente online: Pyth Compiler / Executor

Explicação:

<u-G%@GhH+0GQ%2r1^hQ2Q    Q = input()
             %2r1^hQ2     create the list [1, 2, ..., (Q+1)^2-1][::2]
 u          Q%2r1^hQ2     G = [1, 2, ..., (Q+1)^2-1][::2]
                           modify G for each H in [0, 1, 2, ..., Q]:
  -G%:GhH+0G                  G = G - ([0] + G)[::G[H+1]]
                               (minus is remove in Pyth)
<                    Q    print the first Q elements of the resulting list

A redução realmente calcula mais do que Qnúmeros da sorte (o comando remove é chamado Q + 1 vezes, Q-1 deve ser suficiente).

R, 58 bytes

n=scan();s=r=1:n^2;for(j in 1:n)r=r[-max(2,r[j])*s];r[1:n]

Com quebras de linha:

n=scan()              #user input
s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
for(j in 1:n)
  r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
r[1:n]                #print

Versão anterior, 62 bytes

function(n){
  s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
  for(j in 1:n)
    r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
  r[1:n]                #print
}

Versão anterior, 78 bytes

n=as.numeric(readline())   #ask for user input and convert it to numeric
r=1:n^2                    #create a large enough vector to sieve
for(j in 1:n){             #loop
  r=r[-max(2,r[j])*1:n^2]  #iteratively remove elements by position in vector
}
r[1:n]                     #print

CJam, 32 30 bytes

3ri:N#,N{0\__I1e>)=%-+}fI(;N<p

Recebe entrada de STDIN.

Explicação do código :

3ri:N#,                          "Read the input in N and get first 3^N whole numbers";
       N{0\__I1e>)=%-+}fI        "Run the code block N times, storing index in I";
         0\__                    "Put 0 before the array and take 2 copies";
             I1e>)=              "Take min(2, I + 1) th index from the copy";
                   %             "Take every array[ min (2, I + 1)] element from the array";
                    -+           "Remove it from the list and prepend 0 to the list";
                         (;N<p   "Print number index 1 to N";

Experimente online aqui

Python 2, 105 101 bytes

n=input()
L=range(-1,n*n+9,2)
i=2
while L[i:]:L=sorted(set(L)-set(L[L[i]::L[i]]));i+=1
print L[1:n+1]

Apenas uma implementação direta.

Pitão, 39 36 35 32 bytes

J%2r1h^Q2VJI>JhN=J-J%@JhN+2J;<JQ

Semelhante à abordagem acima, mas as coisas são indexadas em 0 e não em 1. Experimente online .

Agradecemos a @Jakube por apontar uma economia de bytes.

Mathematica, 80 bytes

(For[l=Range[#^2];i=1,(m=l[[i++]]~Max~2)<=Length@l,l=l~Drop~{m,-1,m}];l[[;;#]])&

Implementação direta da definição. Como algumas outras respostas, começa com um intervalo de 1até e continua a filtrar.n2

Perl, 86 81 78

86:

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=map{$i++%($n+($n<2))?$_:()}@a;$k-=$k&&print"$n "}

UPDATE: obviamente, grep{...}é melhor quemap{...?$_:()} 81:

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=grep{$i++%($n+($n<2))}@a;$k-=$k&&print"$n "}

UPDATE: OK, na verdade é uma linha agora. Eu posso parar. (?) 78:

@a=(1..($k=<>)**2);for$n(@a){$k-=$i=$k&&print"$n ";@a=grep{$i++%($n+=$n<2)}@a}

Oitava, 139 83 72

function r=l(n)r=1:2:n^2;for(i=2:n)h=r(i);r(h:h:end)=[];end;r=r(1:n);end

Ungolfed:

function r=l(n)
  r=1:2:n^2;
  for(i=2:n)
    h=r(i);
    r(h:h:end)=[];
  end
r=r(1:n);  # reduce it to only N lucky numbers
end

J, 60 52 bytes

   ({.}.@((>:@{.,]#~0<({~{.)|i.@#)@]^:[2,1+2*i.@*:@>:)) 8
1 3 7 9 13 15 21 25

Explicação (da direita para a esquerda):

2,1+2*i.@*:@>:  generates the list 2 1 3 5 7 9... with (n+1)^2 odd numbers
^:[             repeats n times the following
@]                using the list
0<({~{.)|i.@#     is the remainder of the indexes of the lists elements with the first element positive (i.e. index divisible by first element)
]#~               keep those elements from the list
>:@{.,            concatenate a first element with the value of the current one +1
}.@             drop first element
{.              take the first n element

2,1+2*i.@*:@>:parece muito longo, mas só posso reduzi-lo em 1 byte, fazendo *:com !que a lista cresça exponencialmente.

JavaScript (ES6) 96 99

Editar Contagem regressiva no primeiro loop - obrigado @DocMax

F=n=>(i=>{
  for(o=[1];--i;)o[i]=i-~i;
  for(;++i<n;)o=o.filter((x,j)=>++j%o[i]);
})(n*n)||o.slice(0,n)

Ungolfed

F=n=>{
  for (i = n*n, o = [1]; --i;)
    o[i] = i+i+1;
  for (; ++i < n; )
    o = o.filter((x, j) => (j+1) % o[i])
  return o.slice(0,n)
}

Teste no console Firefox / FireBug

F(57)

Saída

[1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303]

Matlab, 104 bytes

function x=f(n)
k=1;N=n;x=0;while nnz(x)<n
x=1:N;m=1;while m-nnz(x)
m=x(x>m);x(m:m:end)=[];end
N=N+2;end

Agradecemos a @flawr pelos comentários e sugestões muito apropriados.

Exemplo do prompt de comando do Matlab:

>> f(40)
ans =
  Columns 1 through 22
     1     3     7     9    13    15    21    25    31    33    37    43    49    51    63    67    69    73    75    79    87    93
  Columns 23 through 40
    99   105   111   115   127   129   133   135   141   151   159   163   169   171   189   193   195   201

Bash + coreutils, 136

Eu esperava jogar mais isso, mas tudo bem. Nem todos os dias que você entra em uma função recursiva em um script de shell:

f(){
mapfile -tn$2 a
(($1>$2))&&{
tr \  \\n<<<${a[@]}
sed $[${a[-1]}-$2]~${a[-1]}d
}|f $1 $[$2+1]||echo ${a[@]}
}
yes|sed -n 1~2=|f $1 2

Saída:

$ ./lucky.sh 23
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99
$ 

Bash + coreutils, 104

Menor usando uma implementação mais direta:

a=(`seq 1 2 $[3+$1**2]`)
for((;i++<$1;));{
a=($(tr \  \\n<<<${a[@]}|sed 0~${a[i]}d))
}
echo ${a[@]:0:$1}

Go, 326

package main
import"fmt"
func s(k, p int,in chan int)chan int{
    o := make(chan int)
    go func(){
        for p>0{
            o<-<-in;p--
        }
        for{
            <-in
            for i:=1;i<k;i++{o<-<-in}
        }
    }()
    return o
}
func main(){
    n := 20
    fmt.Print(1)
    c := make(chan int)
    go func(c chan int){
        for i:=3;;i+=2{c<-i}
    }(c)
    for i:=1;i<n;i++{
        v := <-c
        fmt.Print(" ", v)
        c = s(v, v-i-2, c)
    }
}

Implementação direta usando goroutine e tubos para fazer peneiras.

MATLAB, 62 caracteres

n=input('');o=1:2:n^2;for i=2:n;o(o(i):o(i):end)=[];end;o(1:n)

No início, interpretei mal o desafio - minha versão revisada agora é realmente mais curta.

Raquete 196 bytes

Produz números da sorte até n:

(λ(n)(let loop((l(filter odd?(range 1 n)))(i 1))(define x(list-ref l i))(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)
    (let loop ((l (filter odd? (range 1 n))) (i 1))
      (define x (list-ref l i))
      (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)

Saída:

'(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)