Rzeczy, które warto wiedzieć:

Po pierwsze, szczęśliwe liczby.

Szczęśliwe liczby są generowane w następujący sposób:

Weź wszystkie liczby naturalne:

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

Następnie usuń co drugi numer.

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

Teraz 3jest bezpieczny.

Usuń co trzeci numer:

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

Teraz 7jest bezpieczny.

Usuń co 7 liczbę.

Kontynuuj i usuwaj każdy nnumer, gdzie njest pierwszy bezpieczny numer po eliminacji.

Ostateczna lista bezpiecznych liczb to szczęśliwe liczby.

Pechowe liczby składają się z osobnych list liczb, które są [U1, U2, U3... Un].

U1 to pierwszy zestaw liczb usunięty ze szczęśliwych „kandydatów”, więc są to:

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

U2 jest usunięty drugi zestaw liczb:

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

I tak dalej itd. ( U3Jest trzecią listą, U4czwartą itd.)

Wyzwanie:

Twoim zadaniem jest, po otrzymaniu dwóch danych wejściowych mi nwygenerowanie mth liczby na liście Un.

Przykładowe dane wejściowe i wyjściowe:

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

Okular:

• Twój program musi działać mdo 1e6, a nnawet do 100.
  • Masz gwarancję, że zarówno mi nsą dodatnimi liczbami całkowitymi.
  • Jeśli jesteś ciekawy, U(1e6, 100)= 5,333,213,163. (Dziękuję @pacholik!)
• Twój program musi to obliczyć w ciągu 1 dnia na rozsądnym nowoczesnym komputerze.

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach!

PS: Byłoby miło, gdyby ktoś wymyślił ogólną formułę ich generowania. Jeśli masz formułę, podaj ją w swojej odpowiedzi!

CJam , 74 bajty

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

Wypróbuj online! Przekroczą limit czasu dla większych przypadków, więcej na temat ograniczeń czasowych poniżej.

Wyjaśnienie:

Nasz program bezwstydnie pożycza kod aditsu, aby wygenerować listę N szczęśliwych liczb, a zamiana 1 na 2 daje przyrost w każdej fazie sita. Pozostałe kody zmniejszają się na każdym elemencie, aż do znalezienia zera (przez krojenie i dołączanie nieodkresowanego ogona) i skutecznie zlicza kroki w każdej z N faz sita jednocześnie.

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

Wyczucie czasu:

Jeśli absolutnie musisz uruchomić program w przeglądarce dla większych liczb, możesz użyć tego interpretera i pozwolić skryptowi na kontynuowanie, jeśli pojawi się monit, ale może to być zbyt wolne, aby się zakwalifikować. Użycie ( M , N ) = (100,100) zajmuje ~ 247 sekund. Iteracja programów jest względnie liniowa pod względem M , więc obliczenia (1e6,100) mogą zająć ~ 29 dni.

Za pomocą interpretera powłoki na komputerze program oblicza (100,100) w ~ 6s i oblicza (1e4,100) w ~ 463s. Program powinien być w stanie obliczyć (1e6,100) w ~ 13-17 godzin. W takim przypadku założę, że program się kwalifikuje.

Uwaga: wszystkie czasy zostały zaokrąglone w górę zarówno w pomiarach, jak i obliczeniach.

Perl, 87 85 82 81 bajtów

Obejmuje +4 za -pX

Podaj dane wejściowe STDIN jako jedną linię z n jako pierwszą (zauważ, że jest to odwrotność kolejności sugerowanej w wyzwaniu). Aby obliczyć U(1000000, 100):

unlucky.pl <<< "100 1000000"

Algorytm oparty na aditsu „s szczęśliwe liczby odpowiedzieć Złożoność czas jest O(n^2)więc to raczej szybko do wymaganego zakresu. Obudowa 100, 1000000daje 5333213163w 0,7 sekundy. Z powodu problemów, jakie ma perl z do$0rekurencją bazową, zużywa dużo pamięci. Przepisanie go jako funkcji spowodowałoby użycie pamięci, O(n)ale jest o kilka bajtów dłuższe

unlucky.pl:

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

Działa to tak, jak pokazano, ale użyj literału, ^Saby uzyskać wynik.

Nie wiem o żadnym wcześniejszym użyciu $^Sw 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))

Funkcja L generuje rząd możliwych szczęśliwych liczb (jeśli k to Prawda) lub Un (jeśli Fałsz). Ocenione leniwie (więc nie muszę generować nieskończonych list n-1, jeśli chcę Un ).

Uruchomić funkcję U .

Prędkość

Uruchomienie U (1 000 000; 100) na moim komputerze z PyPy zajmuje około 1h 45min. Podejrzewam, że jakieś cztery godziny z CPython. (Tak, dokładnie 4 godz. 20 min.)

Gdybym użył listy zamiast generatorów, mógłbym zyskać trochę prędkości, ale potrzebowałbym listy o większym rozmiarze niż pozwala mi Python. A jeśli tak, potrzebowałby dziesiątek gigabajtów pamięci RAM.

Tak, a U (1 000 000; 100) = 5 333 213 163 .

Haskell

Nie można obliczyć dla n = 1: 175 160 bajtów

Po kompilacji komputer potrzebował 2h 35m na obliczenie danych wejściowych (1000000,100)użycia:

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)

Próbowałem pozbyć się wheremodułów, ale wydaje się, że wpływają one na szybkość i nie jestem pewien, dlaczego ... Ale myślę, że można tu zrobić więcej przycinania.

Metodą do zastosowania jest m?nzapytanie o odpowiedź na pytanie mi n.

Nie golfił

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.

Myślę, że możliwe jest połączenie funkcji „skipeverynth” i „everynth” w jedną funkcję, która zwraca parę.

Użyłem kodu tego rodzaju osoby do pominięcia każdego n-tego elementu. Zrobiłem to sam kilka razy, ale zawsze było to znacznie bardziej nieefektywne i nie mogłem zrozumieć, dlaczego.

Możliwość obliczenia dla wszystkich n: 170 bajtów

Jest to w zasadzie to samo, ale maxtrzeba było wrzucić kilka funkcji, aby obsłużyć specjalny przypadek 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 bajty

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

Stosowanie

f(5,2)
Returns 29

Musi mieć wystarczająco duży wektor, aby zacząć, więc jest wystarczająco dużo liczb, aby zwrócić wartość. Utworzony wektor ma już około 800 Mb, a funkcja może obsłużyć do m = 1e4 i n = 100, więc wciąż znacznie poniżej celu.

Aby utworzyć wystarczająco duży wektor do obliczenia f (1e6,100), trzeba wziąć wektor początkowy 1: 2e10. Z powodu procedur alokacji danych Rs tworzy to wektor> 70 Gb, którego nie można uruchomić na żadnym komputerze, który znam, chociaż kod by się uruchomił.

Error: cannot allocate vector of size 74.5 Gb

Dla porównania f (1e4,100) działa w około około 30 sekund. Na tej podstawie i kilku mniejszych testach f (1e6,100) zajęłoby około godziny.

Rakieta 332 bajty

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

Wersja bez golfa:

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

Testowanie:

(f 100 5 2)

Wydajność:

29

Clojure, 221 bajtów

Mighty długo ale uchwyty sprawa (f 1). Bez tego specjalnego przypadku było to 183 bajty. To był zbyt wielki wysiłek, aby go nie opublikować.

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

Przykładowe wyniki:

(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 przypadków zostało obliczonych w ciągu około 4,7 godzin, przynajmniej się nie zawiesiło.

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