Oblicz praktyczne liczby

18

Definicja

Dodatnia liczba całkowita njest 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 18jest 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 14to 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ą xi albo zwraca, albo wypisuje x- 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
Peter Taylor
źródło
(IMHO) może to być interesujące, jeśli wygrywa najszybszy kod (na język?)
Nazwa wyświetlana
4
@SargeBorsch Więc zobaczysz tabele 250 000 wpisów w odpowiedziach
dr belisarius
@belisarius good point. ale myślę, że takie oszustwo można łatwo zakazać. Albo problem może wymagać poprawnych odpowiedzi dla dowolnej liczby, ale wtedy pojawiałyby się trudności podczas robienia tego w języku bez dużych liczb całkowitych w standardowej bibliotece ...: /
Nazwa wyświetlana
Mam na myśli jedną optymalizację algorytmiczną, ale przy obecnych regułach jestem zbyt leniwy, aby ją wdrożyć: P
Nazwa wyświetlana
4
@SargeBorsch, jeśli nie chcesz zagrać w golfa, kod możesz przesłać na coś takiego jak gist.github.com i upuścić link w komentarzu tutaj lub na czacie. FWIW Wolę code golfa z dużymi ograniczeniami wydajności od najszybszego kodu z dwóch powodów: po pierwsze, długość kodu jest bardziej obiektywnie mierzalna; po drugie wprowadza element kompromisu: które optymalizacje prędkości można pominąć, aby skrócić kod bez rujnowania wydajności?
Peter Taylor

Odpowiedzi:

5

J (99 znaków)

f=:3 :0
'n c'=.0 1
while.c<y do.
'p e'=.__ q:n=.n+2
c=.c+*/(}.p)<:}:1+*/\(<:p^e+1)%<:p
end.
n+n=0
)

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 250000oblicza 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.

Omar
źródło
6

Mathematica, 126 121 znaków

Dzięki Belizariusz.

Korzystanie z formuły na wikipedii.

f=(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&

Przykłady:

f[1]

1

f[8]

18

f[250000]

2764000

Obliczenia f[250000]na moim komputerze zajęły lata 70 .

alephalpha
źródło
3
Myślę, że można uzyskać lepszą wydajność kosztem jednego znaku, omijając nieparzyste liczby całkowite
dr belisarius
1
Zmniejszając kod z przedłożenia OEIS, spowolniłeś wykonanie 10-krotnie. Zastanawiam się tylko: „jak myślisz, dlaczego twój kod działa o wiele wolniej niż przykład OEIS?”
DavidC
@belisarius Twoja sugestia skraca czas o połowę, zgodnie z oczekiwaniami.
DavidC
2
To samo dotyczy 119 znaków:(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Dr Belisarius
3

Haskell - 329

s 1=[]
s n=p:(s$div n p)where d=dropWhile((/=0).mod n)[2..ceiling$sqrt$fromIntegral n];p=if null d then n else head d
u=foldr(\v l@((n,c):q)->if v==n then(n,c+1):q else(v,1):l)[(0,1)]
i z=(z<2)||(head w==2)&&(and$zipWith(\(n,_)p->n-1<=p)(tail n)$scanl1(*)$map(\(n,c)->(n*n^c-1)`div`(n-1))n)where w=s z;n=u w
f=((filter i[0..])!!)

Przykłady:

> f 1
1
> f 13
32
> f 1000
6500

Oto mały pakiet testowy (do powyższego):

import Data.Time.Clock
import System.IO

test x = do
    start <- getCurrentTime
    putStr $ (show x) ++ " -> " ++ (show $ f x)
    finish <- getCurrentTime
    putStrLn $ " [" ++ (show $ diffUTCTime finish start) ++ "]"

main = do
    hSetBuffering stdout NoBuffering
    mapM_ test [1, 8, 1000, 250000, 1000000, 3000000]

Wyniki testu po kompilacji z ghc -O3:

1 -> 1 [0.000071s]
8 -> 18 [0.000047s]
1000 -> 6500 [0.010045s]
250000 -> 2764000 [29.084049s]
1000000 -> 12214770 [201.374324s]
3000000 -> 39258256 [986.885397s]
mniip
źródło
Kiedy próbuję tego w ghci, narzeka parse error on input `='. Czy muszę użyć jakiejś flagi czy innej?
Peter Taylor
1
@PeterTaylor Nie można wklejać definicji funkcji do ghci w ten sposób. Najprościej jest to zapisać asdf.hsi uruchomić ghci asdf.hs, a stamtąd będzie można uzyskać dostępf
mniip
@PeterTaylor 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. :)
Jonathan Van Matre
@JonathanVanMatre jak widać w powyższym komentarzu, ghciładuje pliki określone w swoich argumentach
mniip
Ach, okej W międzyczasie mam go uruchomionego z twoim szkieletem testowym i ghc. Twój komputer jest szybszy niż mój, ale wciąż jest w granicach kryterium wydajności na moim komputerze po 98 sekundach.
Peter Taylor
2

JavaScript, 306 307 282 B.

function y(r){for(n=r-1,k=1;n;k++)if(p=[],e=[],c=0,P=s=1,!((x=k)%2|1==x)){while(x>1){for(f=x,j=2;j<=Math.sqrt(f);j++)if(f%j==0){f=j;break}f!=p[c-1]?(p.push(f),e.push(2),c++):e[c-1]++,x/=f}for(i=0;c>i;i++){if(p[i]>P+1){s=0;break}P*=(Math.pow(p[i],e[i])-1)/(p[i]-1)}s&&n--}return k-1}

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/

Alexander-Brett
źródło
Pytanie, czy poprosić o funkcji lub programu (JS nie ma czasowników), więc raczej niż nie licząc pierwszego wiersza należy owinąć drugą linię w deklaracji funkcji i zastąpić ostateczna k--;z return k-1. Mimo że zwiększa nieco swoją liczbę bajtów, można zaoszczędzić kilka z rzeczy jak zastąpienie p[i]>=P+2z p[i]>P+1(i prawdopodobnie przez usunięcie wewnętrznego wywołanie funkcji i stosując breakzamiast).
Peter Taylor
Myślę, że część „testowanie sigmy” można przepisać zarówno pod względem wielkości, jak i prędkości: jsfiddle.net/3DTSa . Chociaż to rozwiązanie JS jest bardzo szybkie.
user2846289,