Historia:

Lucy le preguntó a George cuál era su número de la suerte. Después de cierta contemplación, George respondió que tenía varios números de la suerte. Después de una breve confusión, Lucy le preguntó a George cuáles son sus primeros nnúmeros de la suerte. Luego, George le pidió a su amigo que le escribiera un programa para hacer el trabajo por él.

El reto:

Escribirás un programa / función que recibirá del argumento de entrada / función estándar una cadena o un entero n. El programa / función devolverá / generará los primeros n Lucky Numbers . Los números de la suerte se definen a través de un tamiz de la siguiente manera.

Comience con los enteros 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, ...

Ahora elimine cada segundo número:

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

El segundo número restante es 3 , así que elimine cada tercer número:

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

Ahora el siguiente número restante es 7 , así que elimine cada séptimo número:

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

Luego, elimine cada noveno número y así sucesivamente. La secuencia resultante son los números de la suerte.

Victorioso:

Como es habitual para codegolf, gana menos bytes.

Como de costumbre, las presentaciones que utilizan lagunas estándar están descalificadas.

Pitón 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]

¡La magia de iterar sobre una lista mientras el ciclo lo modifica!

La lista Lcomienza con todos los enteros 1a un valor suficientemente alto. El código itera sobre cada elemento rde L, tomando la sublista de cada relemento y quitando cada uno de esos valores. Como resultado, los valores eliminados no se repiten. Al final, imprime los primeros nelementos.

La expresión map(A.remove,B)es un truco que he estado esperando mucho tiempo para usar. Llama A.removea cada elemento de B, lo que hace Bque se eliminen todos los elementos de A. Efectivamente, toma la diferencia de la lista, aunque requiere Bser una sublista de A. Requiere Python 2, ya que Python 3 en realidad no evaluaría el mapa.

El primer bucle necesita una carcasa especial para convertir rde 1a 2, como r+=r<2.

El límite superior suficientemente alto de 2**nhace que el programa sea muy lento para valores grandes de n. Usar es n*n+1suficiente, pero cuesta un personaje. Tenga en cuenta que n*nno funciona para 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 una función f. La expresión se 1:s[3,5..]3evalúa como la lista infinita de números de la suerte, y fsimplemente toma el primero nde ellos por take n.

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

Podría eliminar 5 bytes del tamiz utilizando una comprensión de lista paralela

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

pero eso requeriría pasar la enorme bandera del compilador -XParallelListCompa GHC para habilitar la extensión.

Explicación del tamiz.

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

La idea básica es que s(n:k)pproduce el (p-1)número número de la suerte n, elimina cada nnúmero de la cola infinita k(compensado ppara tener en cuenta los números producidos anteriormente) y vuelve a esa lista con el acumulador (p+1). En f, iniciamos el proceso con los números impares a partir de 3, y clavamos 1al frente, obteniendo exactamente los números de la suerte.

Pitón 2, 71 69 67

Al principio, pensé que este sería un gran desafío para el corte de matriz de Python. Sin embargo, me encontré con un escollo cuando descubrí que a los sectores con un paso distinto de 1 solo se les puede asignar otro segmento de longitud idéntica. Pero después de buscar en Google "python remove slice", mi fe fue restaurada: encontré una delafirmación original que funciona perfectamente.

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

Versión antigua

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 gracias a 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. >

Solo tengo unas pocas palabras para decir ...

... "Argh me duele el cerebro".

Explicación

> <> es un lenguaje de programación esotérico 2D y definitivamente no es adecuado para esta tarea, debido a su falta de matrices. De hecho, el único tipo de datos en> <> es una extraña mezcla de int / float / char, y todo sucede en una pila de pilas.

Aquí está el resumen:

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

Aquí hay un ejemplo simulado que demuestra aproximadamente cómo funciona el tamizado (aquí kestá el número de la suerte con el que tamizamos):

[[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

Pruébalo en línea

Explicación:

Esta implementación no elimina números sucesivamente de una matriz, sino que calcula cada número en función de cuántos se habrían eliminado antes.
Para cada índice i (de 0 a n-1) y cada número de suerte anterior l, en orden inverso, incrementamos i en i / (l-1), excepto para l = 1 usamos 1 en lugar de 0, y también sumamos 1 al final.
Por ejemplo, para i = 4 tenemos los primeros 4 números, [1 3 7 9], y 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

Pyth: 23 22 bytes

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

Pruébelo en línea: Pyth Compiler / Executor

Explicación:

<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

La reducción en realidad calcula más que Qnúmeros de la suerte (el comando eliminar se llama Q + 1 veces, Q-1 debería 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]

Con saltos de línea:

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

Versión 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
}

Versión 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

Toma información de STDIN.

Explicación del 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";

Pruébalo en línea aquí

Python 2, 105101 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]

Solo una implementación sencilla.

Pyth, 39 36 35 32 bytes

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

Similar al enfoque anterior, pero las cosas están indexadas en 0 en lugar de 1. Pruébalo en línea .

Gracias a @Jakube por señalar un ahorro 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[[;;#]])&

Implementación directa de la definición. Como algunas otras respuestas, comienza con un rango desde 1hasta y luego sigue filtrando.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 "}

ACTUALIZACIÓN: obviamente, grep{...}es mejor que map{...?$_:()} 81:

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

ACTUALIZACIÓN: OK, en realidad una línea ahora. No puedo parar. (?) 78:

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

Octava, 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

Sin golf:

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

Explicación (de derecha a izquierda):

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 demasiado largo, pero solo puedo acortarlo en un intercambio de 1 byte *:para !hacer que la lista crezca exponencialmente.

JavaScript (ES6) 96 99

Editar cuenta atrás en el primer bucle - gracias @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)

Sin golf

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

Prueba en la consola Firefox / FireBug

F(57)

Salida

[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

Gracias a @flawr por sus comentarios y sugerencias muy apropiados.

Ejemplo del símbolo del sistema de 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

Esperaba jugar más golf, pero bueno. No todos los días se conecta a una función recursiva en un 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

Salida:

$ ./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

Más corto usando una implementación más sencilla:

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

Ve, 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)
    }
}

Implementación directa usando gorutina y tuberías para hacer tamices.

MATLAB, 62 caracteres

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

Al principio malinterpreté el desafío: mi versión revisada ahora es en realidad más corta.

Raqueta 196 bytes

Produce números de la suerte hasta 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)))))

Versión sin golf:

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

Pruebas:

(f 100)

Salida:

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