Cerita:

Lucy bertanya pada George berapa Angka Keberuntungannya. Setelah beberapa perenungan, George menjawab bahwa ia memiliki beberapa Angka Keberuntungan. Setelah kebingungan singkat, Lucy bertanya pada George apa nAngka Keberuntungan pertamanya . George kemudian meminta Anda, temannya, untuk menulis kepadanya sebuah program untuk melakukan pekerjaan untuknya.

Tantangan:

Anda akan menulis sebuah program / fungsi yang akan menerima dari input standar / argumen fungsi string atau integer n. Program / fungsi kemudian akan mengembalikan / menampilkan n Angka Keberuntungan pertama . Angka keberuntungan didefinisikan melalui ayakan sebagai berikut.

Mulai dengan bilangan bulat positif:

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

Sekarang hapus setiap angka kedua:

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

Angka kedua yang tersisa adalah 3 , jadi hapuslah setiap angka ketiga:

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

Sekarang angka selanjutnya yang tersisa adalah 7 , jadi hapuslah setiap angka ketujuh:

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

Selanjutnya, hapus setiap angka kesembilan dan seterusnya. Urutan yang dihasilkan adalah angka keberuntungan.

Kemenangan:

Seperti biasa untuk codegolf, byte paling sedikit menang.

Seperti biasa, pengiriman menggunakan celah standar didiskualifikasi.

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]

Keajaiban iterasi pada daftar saat loop memodifikasinya!

Daftar Ldimulai dengan semua bilangan bulat 1ke nilai yang cukup tinggi. Kode iterates atas setiap elemen rdari L, mengambil sublist setiap r'elemen th, dan menghapus masing-masing nilai. Akibatnya, nilai yang dihapus tidak berulang. Pada akhirnya, cetak nelemen pertama .

Ekspresi map(A.remove,B)adalah trik yang sudah lama saya tunggu untuk digunakan. Itu panggilan A.removeuntuk setiap elemen B, yang menyebabkan semua elemen Buntuk dihapus A. Secara efektif, diperlukan perbedaan daftar, meskipun Bharus menjadi sublist dari A. Ini membutuhkan Python 2, karena Python 3 tidak akan benar-benar mengevaluasi peta.

Loop pertama perlu di-cased khusus untuk mengkonversi rdari 1menjadi 2, as r+=r<2.

Batas atas yang cukup tinggi 2**nmembuat program sangat lambat untuk nilai besar n. Menggunakan n*n+1cukup, tetapi biaya karakter. Catatan yang n*ntidak berfungsi n=1.

Haskell, 71 69 byte

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

Menentukan fungsi f. Ekspresi 1:s[3,5..]3mengevaluasi ke daftar nomor keberuntungan yang tak terbatas, dan fhanya mengambil yang pertama ndengan take n.

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

Saya bisa mencukur 5 byte dari saringan menggunakan pemahaman daftar paralel

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

tetapi itu akan membutuhkan melewati flag compiler humongous -XParallelListCompke GHC untuk mengaktifkan ekstensi.

Penjelasan dari saringan

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

Ide dasarnya adalah s(n:k)pmenghasilkan angka (p-1)keberuntungan ke-1 n, menjatuhkan setiap nangka dari ekor yang tak terbatas k(diimbangi dengan pmemperhitungkan angka yang dihasilkan sebelumnya), dan berulang ke daftar itu dengan akumulator (p+1). Dalam f, kami menginisialisasi proses dengan angka ganjil mulai dari 3, dan tempel 1ke depan, mendapatkan angka keberuntungan persis.

Python 2, 71 69 67

Pada awalnya, saya pikir ini akan menjadi tantangan besar bagi pemotongan array Python. Namun, saya menemukan batu sandungan ketika saya menemukan bahwa irisan dengan langkah selain 1 hanya dapat memiliki irisan lain dengan panjang yang sama. Tetapi setelah googling "python remove slice", iman saya dipulihkan: Saya menemukan delpernyataan funky yang melakukan trik dengan sempurna.

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

Versi lama

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

-2 byte terima kasih kepada Sp3000.

> <> , 121 114 111 byte

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

Saya hanya punya beberapa kata untuk dikatakan ...

... "Argh, otakku sakit."

Penjelasan

> <> adalah bahasa pemrograman 2D esoterik dan jelas tidak cocok untuk tugas ini, karena kurangnya array. Bahkan, satu-satunya tipe data di> <> adalah campuran aneh int / float / char, dan semuanya terjadi pada setumpuk tumpukan.

Inilah ikhtisarnya:

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

Berikut adalah contoh tiruan yang menunjukkan kira-kira cara kerja pengayak (di sini kadalah angka keberuntungan yang kami saring):

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

Cobalah online

Penjelasan:

Implementasi ini tidak menghapus angka secara berurutan dari array, tetapi menghitung setiap angka berdasarkan berapa banyak yang akan dihapus sebelumnya.
Untuk setiap indeks i (dari 0 hingga n-1) dan setiap angka keberuntungan l sebelumnya, dalam urutan terbalik, kami menambah i dengan i / (l-1), kecuali untuk l = 1 kami menggunakan 1 bukan 0, dan juga menambahkan 1 di akhir.
Misalnya untuk i = 4 kita memiliki 4 angka pertama, [1 3 7 9], dan menghitung:
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 byte

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

Cobalah secara online: Pyth Compiler / Executor

Penjelasan:

<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

Pengurangan sebenarnya menghitung lebih dari Qangka keberuntungan (perintah hapus disebut Q + 1 kali, Q-1 harus cukup).

R, 58 byte

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

Dengan jeda baris:

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 sebelumnya, 62 byte

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 sebelumnya, 78 byte

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 byte

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

Mengambil input dari STDIN.

Penjelasan kode :

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";

Cobalah online di sini

Python 2, 105 101 byte

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]

Implementasi yang mudah.

Pyth, 39 36 35 32 byte

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

Mirip dengan pendekatan di atas, tetapi semuanya diindeks 0 daripada diindeks 1. Cobalah online .

Terima kasih kepada @Jakube karena menunjukkan penghematan byte.

Mathematica, 80 byte

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

Implementasi langsung dari definisi. Seperti beberapa jawaban lain, mulai dengan rentang dari 1ke dan kemudian terus memfilter.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: jelas, grep{...}lebih baik dari map{...?$_:()} 81:

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

UPDATE: OK, sebenarnya satu-liner sekarang. Saya bisa berhenti. (?) 78:

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

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

Tidak Disatukan:

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 byte

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

Penjelasan (dari kanan ke kiri):

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.@*:@>:tampaknya terlalu lama tetapi saya hanya dapat mempersingkat dengan 1 byte swapping *:dengan !membuat daftar bertambah secara eksponensial.

JavaScript (ES6) 96 99

Edit Menghitung mundur di loop pertama - terima kasih @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)

Tidak disatukan

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

Uji di Firefox / konsol FireBug

F(57)

Keluaran

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

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

Dengan terima kasih kepada @ flawr untuk komentar dan saran yang sangat tepat.

Contoh dari command prompt 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

Saya berharap untuk menurunkan ini lebih, tapi oh well. Tidak setiap hari Anda melakukan pipe ke fungsi rekursif dalam skrip 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

Keluaran:

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

Lebih pendek menggunakan implementasi yang lebih mudah:

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

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

Implementasi lurus ke depan menggunakan goroutine dan pipa untuk membuat saringan.

MATLAB, 62 karakter

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

Saya salah menafsirkan tantangan pada awalnya - versi revisi saya sekarang sebenarnya lebih pendek.

Racket 196 byte

Menghasilkan angka keberuntungan hingga 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 tidak disatukan:

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

Pengujian:

(f 100)

Keluaran:

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