Definicja
Dodatnia liczba całkowita n
jest liczbą praktyczną (sekwencja OEIS A005153 ) i wszystkie mniejsze liczby całkowite dodatnie mogą być reprezentowane jako sumy różnych dzielników n
.
Na przykład 18
jest liczbą praktyczną: jej dzielniki to 1, 2, 3, 6, 9 i 18, a inne dodatnie liczby całkowite mniejsze niż 18 można utworzyć w następujący sposób:
4 = 1 + 3 5 = 2 + 3 7 = 1 + 6
8 = 2 + 6 10 = 1 + 9 11 = 2 + 9
12 = 3 + 9 = 1 + 2 + 9 = 1 + 2 + 3 + 6
13 = 1 + 3 + 9 14 = 2 + 3 + 9 15 = 6 + 9
16 = 1 + 6 + 9 17 = 2 + 6 + 9
Ale 14
to nie jest liczba praktyczna: jej dzielniki to 1, 2, 7 i 14 i nie ma ich podzbioru, który dodaje 4, 5, 6, 11, 12 lub 13.
Wyzwanie
Napisz program, funkcję lub czasownik, który przyjmuje jako dane wejściowe dodatnią liczbę całkowitą x
i albo zwraca, albo wypisuje x- tą liczbę praktyczną, indeksowaną od 1 dla zgodności z OEIS. Twój kod musi być wystarczająco wydajny, aby mógł obsługiwać dane wejściowe do 250000 w mniej niż dwie minuty na rozsądnym komputerze stacjonarnym. (Uwaga: moja implementacja referencyjna w Javie zarządza 250000 w mniej niż 0,5 sekundy, a moja referencyjna implementacja w Pythonie zarządza nią w 12 sekund).
Przypadki testowe
Input Expected output
1 1
8 18
1000 6500
250000 2764000
1000000 12214770
3000000 39258256
źródło
Odpowiedzi:
J (99 znaków)
Ponieważ w opisie problemu pojawia się prośba o „program, funkcję lub czasownik ”, ktoś musiał złożyć J. J ludzie zauważą, że tak naprawdę nie grałem (!) Ani nie zoptymalizowałem tego. Podobnie jak inne wpisy, użyłem twierdzenia Stewarta, wspomnianego na łączu OEIS, aby sprawdzić, czy każda liczba parzysta jest praktyczna, czy nie.
Nie mam gotowego dostępu do „rozsądnego komputera stacjonarnego” z zainstalowanym J. Na moim sześcioletnim netbooku
f 250000
oblicza się w 120,6 sekundy, co nie jest niespełna dwie minuty, ale przypuszczalnie na nieco bardziej rozsądnym komputerze kończy się to z czasem.źródło
Mathematica,
126121 znakówDzięki Belizariusz.
Korzystanie z formuły na wikipedii.
Przykłady:
Obliczenia
f[250000]
na moim komputerze zajęły lata 70 .źródło
(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Haskell - 329
Przykłady:
Oto mały pakiet testowy (do powyższego):
Wyniki testu po kompilacji z
ghc -O3
:źródło
parse error on input `='
. Czy muszę użyć jakiejś flagi czy innej?asdf.hs
i uruchomićghci asdf.hs
, a stamtąd będzie można uzyskać dostępf
ghc --make -O3 [filename]
. Możesz także załadować go do ghci,:l [filename]
ale biorąc pod uwagę ograniczenia czasowe, prawdopodobnie skompilowane są najlepiej. :)ghci
ładuje pliki określone w swoich argumentachghc
. Twój komputer jest szybszy niż mój, ale wciąż jest w granicach kryterium wydajności na moim komputerze po 98 sekundach.JavaScript,
306 307282 B.Ok. 250 tys. 6s na moim laptopie.
Skomentowano kod bez golfa: http://jsfiddle.net/82xb9/3/ teraz z lepszym testowaniem sigma i lepszym warunkiem jeśli (dziękuję komentarze)
Wersje przededytacyjne : http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/
źródło
k--;
zreturn k-1
. Mimo że zwiększa nieco swoją liczbę bajtów, można zaoszczędzić kilka z rzeczy jak zastąpieniep[i]>=P+2
zp[i]>P+1
(i prawdopodobnie przez usunięcie wewnętrznego wywołanie funkcji i stosującbreak
zamiast).