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

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.

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 .

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]

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/