Hal yang perlu diketahui:

Pertama, angka keberuntungan.

Angka keberuntungan dihasilkan seperti ini:

Ambil semua bilangan asli:

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

Kemudian, hapus setiap angka kedua.

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

Sekarang 3aman.

Hapus setiap nomor ke-3:

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

Sekarang 7aman.

Hapus setiap nomor 7.

Lanjutkan, dan hapus setiap nnomor, di mana nnomor aman pertama setelah eliminasi.

Daftar akhir nomor aman adalah angka keberuntungan.

Angka-angka sial terdiri dari daftar angka yang terpisah, yaitu [U1, U2, U3... Un].

U1 adalah set angka pertama yang dihapus dari "kandidat" yang beruntung, jadi mereka adalah:

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

U2 adalah set angka kedua yang dihapus:

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

Dan seterusnya dan seterusnya ( U3adalah daftar ketiga, U4adalah yang keempat, dll.)

Tantangan:

Tugas Anda adalah, ketika diberi dua input mdan n, menghasilkan mnomor ke-10 dalam daftar Un.

Contoh input dan output:

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

Spesifikasi:

• Program Anda harus bekerja mhingga 1e6, dan nhingga 100.
  • Anda dijamin keduanya mdan nbilangan bulat positif.
  • Jika Anda penasaran, U(1e6, 100)= 5,333,213,163. (Terima kasih @pacholik!)
• Program Anda harus menghitungnya dalam 1 hari di komputer modern yang masuk akal.

Ini adalah kode-golf , jadi kode terpendek dalam byte menang!

PS: Alangkah baiknya jika seseorang membuat formula umum untuk menghasilkan ini. Jika Anda memiliki formula, harap cantumkan jawaban Anda!

CJam , 74 byte

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

Cobalah online! Akan time out untuk kasus yang lebih besar, lebih banyak pada batasan waktu di bawah ini.

Penjelasan:

Program kami tanpa malu-malu meminjam kode aditsu untuk menghasilkan daftar angka keberuntungan N , mengganti angka 1 dengan angka 2 memberikan kenaikan pada setiap fase ayakan. Kode yang tersisa berkurang pada setiap elemen hingga nol ditemukan (dengan mengiris dan menambahkan ekor yang tidak dikurangi) dan secara efektif menghitung langkah-langkah di setiap fase N dari ayakan sekaligus.

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

Pengaturan waktu:

Jika Anda benar-benar harus menjalankan program di browser untuk angka yang lebih besar, Anda dapat menggunakan penerjemah ini dan membiarkan skrip untuk melanjutkan jika diminta, tetapi ini mungkin terlalu lambat untuk memenuhi syarat. Menggunakan ( M , N ) = (100.100) membutuhkan ~ 247s. Iterasi program relatif linier dalam hal M , sehingga komputasi (1e6.100) bisa memakan waktu ~ 29 hari.

Menggunakan penerjemah shell pada PC program menghitung (100.100) dalam ~ 6s dan menghitung (1e4.100) dalam ~ 463s. Program harus dapat menghitung (1e6.100) dalam ~ 13-17hrs. Dalam hal ini saya akan menganggap program memenuhi syarat.

Catatan semua waktu dikumpulkan dalam pengukuran dan perhitungan.

Perl, 87 85 82 81 byte

Termasuk +4 untuk -pX

Berikan input pada STDIN sebagai satu baris dengan n pertama (perhatikan ini adalah kebalikan dari urutan yang disarankan dalam tantangan). Jadi untuk menghitung U(1000000, 100):

unlucky.pl <<< "100 1000000"

Algoritma berdasarkan jawaban angka keberuntungan dari aditsu . Kompleksitas waktunya sangat cepat untuk rentang yang diperlukan. The kasus memberikan dalam 0,7 detik. Karena perl perl dengan rekursi berbasis itu menggunakan banyak memori. Menulis ulang sebagai fungsi akan membuat penggunaan memori tetapi jumlah byte lebih lamaO(n^2)100, 10000005333213163do$0O(n)

unlucky.pl:

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

Ini berfungsi seperti yang ditunjukkan, tetapi gunakan literal ^Suntuk mendapatkan skor yang diklaim.

Saya tidak mengetahui adanya penggunaan sebelumnya $^Sdalam perlgolf.

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

Fungsi L menghasilkan deretan kemungkinan angka keberuntungan (jika k adalah Benar) atau Un (jika Salah). Dievaluasi dengan malas (jadi saya tidak perlu membuat n-1 daftar tanpa batas jika saya ingin Un ).

Jalankan fungsi U .

Kecepatan

U (1.000.000; 100) membutuhkan waktu sekitar 1 jam 45 menit untuk berjalan di mesin saya dengan PyPy. Saya curiga sekitar empat jam dengan CPython. (Ya, tepatnya 4 jam 20 menit.)

Jika saya menggunakan daftar alih-alih generator, saya mungkin mendapatkan beberapa kecepatan, tetapi saya akan membutuhkan daftar ukuran yang lebih besar daripada yang diizinkan oleh Python. Dan jika itu terjadi, itu akan membutuhkan puluhan gigabyte RAM.

Ya, dan U (1.000.000; 100) = 5.333.213.163 .

Haskell

Tidak dapat menghitung untuk n = 1: 175 160 byte

Saat dikompilasi, dibutuhkan komputer saya 2jam 35m untuk menghitung input (1000000,100)penggunaan ini:

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)

Saya mencoba membersihkan wheremodul, tetapi tampaknya mempengaruhi kecepatan dan saya tidak yakin mengapa ... Tapi saya pikir ada lebih banyak pemangkasan yang harus dilakukan di sini.

Metode yang digunakan adalah m?nuntuk menanyakan jawaban yang diberikan mdan n.

Tidak disatukan

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.

Saya rasa mungkin untuk menggabungkan fungsi 'skipeverynth' dan 'everynth' menjadi fungsi tunggal yang mengembalikan pasangan.

Saya menggunakan kode orang baik ini untuk melewatkan setiap elemen ke-n. Saya melakukannya sendiri beberapa kali, tetapi selalu jauh lebih tidak efisien dan saya tidak tahu mengapa.

Mampu menghitung semua n: 170 byte

Ini pada dasarnya sama, tetapi beberapa maxfungsi harus dilemparkan untuk menangani kasus khusus 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)

R 82 byte

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

Pemakaian

f(5,2)
Returns 29

Ini harus memiliki vektor yang cukup besar untuk memulai sehingga ada cukup angka untuk mengembalikan nilai. Vektor yang dibuat sudah sekitar 800Mb dan fungsinya dapat menangani hingga m = 1e4 dan n = 100 sehingga masih jauh dari tujuan.

Untuk membuat vektor yang cukup besar untuk menghitung f (1e6.100) akan membutuhkan vektor awal 1: 2e10. Karena prosedur alokasi data Rs ini menciptakan vektor> 70Gb yang tidak dapat dijalankan di komputer mana pun yang saya tahu meskipun kode akan berjalan.

Error: cannot allocate vector of size 74.5 Gb

Untuk referensi f (1e4.100) berjalan sekitar 30 detik. Berdasarkan ini dan beberapa tes yang lebih kecil f (1E6.100) akan memakan waktu sekitar satu jam.

Racket 332 byte

(λ(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 tidak disatukan:

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

Pengujian:

(f 100 5 2)

Keluaran:

29

Clojure, 221 byte

Perkasa panjang tapi menangani kasus ini (f 1). Tanpa kasus khusus itu adalah 183 byte. Ini terlalu banyak upaya untuk tidak mempostingnya.

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

Output sampel:

(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 case dihitung dalam waktu sekitar 4,7 jam, setidaknya tidak crash.

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