Berechnen Sie praktische Zahlen

18

Definition

Eine positive ganze Zahl nist eine praktische Zahl (OEIS-Sequenz A005153 ), wenn alle kleineren positiven ganzen Zahlen als Summen verschiedener Teiler von dargestellt werden können n.

Ist beispielsweise 18eine praktische Zahl: Die Teiler sind 1, 2, 3, 6, 9 und 18, und die anderen positiven ganzen Zahlen kleiner als 18 können wie folgt gebildet werden:

 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

Dies 14ist jedoch keine praktische Zahl: Die Teiler sind 1, 2, 7 und 14, und es gibt keine Teilmenge davon, die zu 4, 5, 6, 11, 12 oder 13 addiert.

Herausforderung

Schreiben Sie ein Programm, eine Funktion oder ein Verb, das eine positive Ganzzahl als Eingabe verwendet xund entweder die x- te praktische Zahl zurückgibt oder ausgibt , die aus Gründen der Konsistenz mit OEIS von 1 indexiert wird. Ihr Code muss so effizient sein, dass er auf einem vernünftigen Desktop-Computer Eingaben von bis zu 250000 in weniger als zwei Minuten verarbeiten kann. (Hinweis: Meine Referenzimplementierung in Java verwaltet 250000 in weniger als 0,5 Sekunden und meine Referenzimplementierung in Python in 12 Sekunden.)

Testfälle

Input        Expected output
1            1
8            18
1000         6500
250000       2764000
1000000      12214770
3000000      39258256
Peter Taylor
quelle
(IMHO) Dies kann sogar interessant sein, wenn der schnellste Code (pro Sprache?) Gewinnt
Sarge Borsch
4
@ SargeBorsch So sehen Sie Tabellen mit 250.000 Einträgen in allen Antworten
Dr. belisarius
@belisarius guter Punkt. aber ich denke, dass solches Betrügen leicht verboten werden kann. Oder das Problem erfordert möglicherweise richtige Antworten für eine beliebige Anzahl, aber dann würde es Schwierigkeiten geben, wenn es in einer Sprache ohne große ganze Zahlen in der Standardbibliothek ausgeführt wird ...: /
Sarge Borsch
Ich habe eine algorithmische Optimierung im Sinn, aber mit den aktuellen Regeln bin ich zu faul, um sie zu implementieren: P
Sarge Borsch
4
@SargeBorsch, wenn du nicht Golf spielen willst, kannst du deinen Code auf etwas wie gist.github.com hochladen und einen Link in einem Kommentar hier oder im Chat einfügen. FWIW Ich bevorzuge Codegolf mit großzügigen Leistungseinschränkungen gegenüber dem schnellsten Code aus zwei Gründen: Erstens ist die Länge des Codes objektiver messbar; zweitens wird ein Kompromisselement eingeführt: Welche Geschwindigkeitsoptimierungen können ausgelassen werden, um den Code zu verkürzen, ohne die Leistung zu beeinträchtigen?
Peter Taylor

Antworten:

5

J (99 Zeichen)

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
)

Da die Problemstellung nach einem "Programm, einer Funktion oder einem Verb " fragt , musste jemand eine J-Vorlage machen. J Leute werden feststellen, dass ich nicht wirklich Golf (!) Gespielt oder dies optimiert habe. Wie bei den anderen Einträgen habe ich Stewarts Theorem verwendet, das im OEIS-Link erwähnt wurde, um zu testen, ob jede gerade Zahl praktisch ist oder nicht.

Ich habe keinen sofortigen Zugriff auf einen "vernünftigen Desktop-Computer", auf dem J installiert ist. Auf meinem sechs Jahre alten Netbook f 250000rechnet das in 120,6 Sekunden, was nicht ganz unter zwei Minuten liegt, aber vermutlich auf jedem etwas vernünftigeren Computer mit der Zeit erledigt.

Omar
quelle
6

Mathematica, 126 121 Zeichen

Dank an Belisarius.

Verwendung der Formel auf Wikipedia.

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

Beispiele:

f[1]

1

f[8]

18

f[250000]

2764000

Es dauerte 70er Jahre, um f[250000]auf meinem Computer zu rechnen .

Alephalpha
quelle
3
Ich denke, Sie können eine bessere Leistung auf Kosten eines
Zeichens erzielen,
1
Indem Sie den Code aus der OEIS-Übermittlung reduziert haben, haben Sie die Ausführung um das Zehnfache verlangsamt. Ich frage mich nur: "Warum läuft Ihr Code Ihrer Meinung nach so viel langsamer als das OEIS-Beispiel?"
DavidC
@belisarius Dein Vorschlag halbiert die Zeit wie erwartet.
DavidC
2
Das gleiche in 119 Zeichen:(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..])!!)

Beispiele:

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

Hier ist eine kleine Testsuite (voranstellen):

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]

Testergebnisse nach der Zusammenstellung mit 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
quelle
Wenn ich das in ghci probiere beschwert es sich parse error on input `='. Muss ich irgendeine Flagge benutzen?
Peter Taylor
1
@PeterTaylor So können Sie keine Funktionsdefinitionen in ghci einfügen. Das einfachste, was Sie tun können, ist, es zu speichern asdf.hsund auszuführen ghci asdf.hs. Von dort aus können Sie dann auff
mniip
@PeterTaylor ghc --make -O3 [filename] . Sie könnten es auch in ghci mit laden, :l [filename]aber angesichts der kompilierten Zeitbeschränkungen ist es wahrscheinlich am besten. :)
Jonathan Van Matre
@ JonathanVanMatre wie im obigen Kommentar zu sehen, ghci lädt Dateien in den angegebenen Argumenten
Mniip
Ach ja ok In der Zwischenzeit habe ich es mit Ihrem Test-Framework und ausgeführtghc . Ihr Computer ist schneller als meiner, aber er liegt nach 98 Sekunden immer noch im Leistungskriterium meines Computers.
Peter Taylor
2

Javascript, 306 307 282B

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}

250k in ca. 6s auf meinem Laptop.

Kommentierter Code ohne Golfspiel: http://jsfiddle.net/82xb9/3/ jetzt mit besseren Sigma-Tests und einer besseren If-Bedingung (danke Kommentare)

Pre-Edit-Versionen: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/

Alexander-Brett
quelle
Die Frage fragt nach einer Funktion oder einem Programm (JS hat keine Verben). Statt die erste Zeile zu zählen, sollten Sie die zweite Zeile in eine Funktionsdeklaration einschließen und die letzte k--;durch ersetzen return k-1. Obwohl dies Ihre Byteanzahl geringfügig erhöht, können Sie einige davon durch Ersetzen p[i]>=P+2durch p[i]>P+1(und möglicherweise durch Entfernen des internen Funktionsaufrufs und Verwenden von a break) speichern .
Peter Taylor
Ich denke, der Teil "testing sigma" kann sowohl für die Größe als auch für die Geschwindigkeit umgeschrieben werden : jsfiddle.net/3DTSa . Diese JS-Lösung ist jedoch so schnell wie sie ist.
user2846289