Reguläre Zahlen sind Zahlen, die die Potenzen gleichmäßig auf 60 verteilen. Als Beispiel, 60 2 = 3600 = 48 × 75, also sind sowohl 48 als auch 75 Teiler einer Potenz von 60. Also sind sie auch reguläre Zahlen.
Dies ist eine Erweiterung von , die auf die nächste Potenz von zwei aufrundet .
Ich habe einen ganzzahligen Wert N , der große Primfaktoren enthalten kann und ich möchte ihn auf eine Zahl runden, die nur aus kleinen Primfaktoren besteht (2, 3 und 5)
Beispiele:
f(18) == 18 == 21 * 32 f(19) == 20 == 22 * 51 f(257) == 270 == 21 * 33 * 51 Was wäre ein effizienter Weg, um die kleinste Zahl zu finden, die diese Anforderung erfüllt?
Die Werte können sehr groß sein. Daher möchte ich vermeiden, alle regulären Zahlen beginnend mit 1 aufzuzählen oder ein Array aller möglichen Werte beizubehalten.
Okay, hoffentlich ist das dritte Mal hier ein Zauber. Ein rekursiver Verzweigungsalgorithmus für eine anfängliche Eingabe von p, wobei N die Zahl ist, die in jedem Thread "gebaut" wird. NB 3a-c werden hier als separate Threads gestartet oder anderweitig (quasi-) asynchron ausgeführt.
Berechnen Sie die nächstgrößere Potenz von 2 nach p, rufen Sie R auf. N = p.
Ist N & gt; R? Beende diesen Thread. Besteht p aus nur kleinen Primfaktoren? Sie sind fertig. Fahren Sie andernfalls mit Schritt 3 fort.
Gehen Sie nach einer der 3a-c zu Schritt 4.
a) Runden Sie p bis zum nächsten Vielfachen von 2. Diese Zahl kann als m * 2 ausgedrückt werden.
b) Runden Sie p bis zum nächsten Vielfachen von 3. Diese Zahl kann als m * 3 ausgedrückt werden.
c) Runden Sie p bis zum nächsten Vielfachen von 5. Diese Zahl kann als m * 5 ausgedrückt werden.
Gehen Sie zu Schritt 2 mit p = m.
Ich habe die Buchführung weggelassen, um den Überblick über N zu behalten, aber das ist ziemlich einfach. Ich nehme es.
Bearbeiten: Vergessen 6, danke ypercube.
Edit 2: Hatte dies bis zu 30, (5, 6, 10, 15, 30) erkannt, dass das unnötig war, nahm das heraus.
Edit 3: (Der letzte, den ich verspreche!) Die 30er-Kontrolle wurde hinzugefügt, um zu verhindern, dass dieser Algorithmus Ihren ganzen Arbeitsspeicher verbraucht.
Bearbeiten Sie 4: Änderung von Macht-von-30 zu Macht-von-2, pro finnws Beobachtung.
Man kann ein beliebig dünnes Stück der Hamming-Folge um das n-te Mitglied in time ~ n^(2/3) by direct erstellen Aufzählung der Tripel (i,j,k) so, dass N = 2^i * 3^j * 5^k .
Der Algorithmus funktioniert von log2(N) = i+j*log2(3)+k*log2(5) ; zählt alle möglichen k s auf und für jede, alle möglichen j s, findet man die obere i und damit die dreifache (k,j,i) und behält sie in einer "band" wenn innerhalb der angegebenen "width" unterhalb des gegebenen high logarithmischer Höchstwert (wenn width & lt; 1 es kann höchstens ein solcher i sein) sortiert sie dann nach ihrem Logarithmus.
WP sagt , dass n ~ (log N)^3 , d. h. Laufzeit ~ (log N)^2 . Hier interessiert uns nicht die genaue Position des gefundenen Triple in der Sequenz, also alle Zählberechnungen aus dem ursprünglichen Code kann weggeworfen werden:
Nach der Aufzählung der Tripel im Slice ist es eine einfache Frage des Sortierens und Suchens, wobei praktisch O(1) Zeit (für beliebig dünn ein Slice) verwendet wird, um das erste Tripel über N zu finden. . Nun, für konstante Breite (logarithmisch) ist die Anzahl der Zahlen in der Scheibe (Mitglieder der "oberen Kruste" in (i,j,k) -Raum unterhalb der log(N) -Ebene) wieder m ~ n^2/3 ~ (log N)^2 und die Sortierung dauert m log m time (damit die Suche, auch linear, ~ m Laufzeit dauert). Aber die Breite kann nach einigen empirischen Beobachtungen für größere N s kleiner gemacht werden; und konstante Faktoren für die Aufzählung von Tripeln sind sowieso viel höher als für die nachfolgende Sortierung.
Selbst bei konstanter Breite (logarithmisch) läuft es sehr schnell und berechnet den 1.000.000sten Wert in der Hamming-Sequenz sofort und das Milliardste in 0.05s.
Die ursprüngliche Idee von "Top-Band der Tripel" ist Louis Klauder zu verdanken, wie in meinem Post auf einem zitiert DDJ Blogs Diskussion zurück im Jahr 2008.
update: wie von GordonBGood in die Kommentare , es gibt keine Notwendigkeit für die ganze Band aber eher nur ein oder zwei Werte über und unter dem Ziel. Der Algorithmus kann leicht dahingehend geändert werden. Die Eingabe sollte auch dahingehend getestet werden, dass sie eine Hamming-Nummer selbst ist, bevor mit dem Algorithmus fortgefahren wird, um Abrundungsprobleme mit doppelter Genauigkeit zu vermeiden. Es gibt keine Rundungsprobleme, bei denen die Logarithmen der Hamming-Zahlen verglichen werden, die im Voraus bekannt sind, um unterschiedlich zu sein (obwohl bis zu einem Billionth Eintrag gehen in der Sequenz verwendet etwa 14 signifikante Ziffern in Logarithmuswerten, so dass nur 1-2 Ziffern übrig bleiben, so dass sich die Situation tatsächlich dort ändern kann, aber für 1-milliardste brauchen wir nur 11 signifikante Ziffern).
update2: stellt fest, dass die doppelte Genauigkeit für Logarithmen dies auf Zahlen unterhalb von etwa 20.000 bis 40.000 Dezimalziffern (d. h. 10 Billionstel bis 100 Billionstel Hamming-Zahl) begrenzt. Wenn dies für so große Zahlen wirklich notwendig ist, kann der Algorithmus zurück auf die Arbeit mit den Integer-Werten selbst umgeschaltet werden, anstatt auf deren Logarithmen, die langsamer sind.
Sie möchten die kleinste Anzahl m finden, die m >= N und m = 2^i * 3^j * 5^k ist, wo alle i,j,k >= 0 .
Unter Logarithmen können die Gleichungen wie folgt umgeschrieben werden:
%Vor% Sie können log2 , log3 , log5 und logN auf (ausreichend hoch, abhängig von der Größe von N ) Genauigkeit berechnen. Dann sieht dieses Problem wie ein Problem Integer Linear programming aus und Sie könnten versuchen, es mit einem der bekannten Algorithmen zu lösen dieses NP-schwere Problem.
Hier ist eine Lösung in Python, die auf Antwort von Will Ness basiert, aber einige Abkürzungen verwendet und reine Ganzzahlmathematik verwendet, um das Ausführen zu vermeiden in numerischer Genauigkeitsfehler des Protokollbereichs:
%Vor%In Englisch: Iteriere jede Kombination von 5s und 3s, finde schnell die nächste Potenz von 2 & gt; = Ziel für jedes Paar und behalte das kleinste Ergebnis bei. (Es ist eine Verschwendung von Zeit, jedes mögliche Vielfache von 2 zu durchlaufen, wenn nur eines von ihnen korrekt sein kann). Es kehrt auch früh zurück, wenn es jemals feststellt, dass das Ziel bereits eine reguläre Zahl ist, obwohl dies nicht unbedingt notwendig ist.
Ich habe es ziemlich gründlich getestet, jede Integer von 0 bis 51200000 getestet und die Liste mit OIS Ссылка verglichen viele große Zahlen, die ± 1 von regulären Zahlen sind usw. Es wird jetzt in verwendet SciPy um optimale Größen für FFTs zu finden.
Ich bin mir nicht sicher, ob die Log-Methode schneller ist, weil ich sie nicht zuverlässig genug zum Testen bekommen konnte. Ich denke, es hat eine ähnliche Anzahl von Operationen, obwohl? Ich bin mir nicht sicher, aber das ist ziemlich schnell. Nimmt & lt; 3 Sekunden (oder 0,7 Sekunden mit gmpy), um zu berechnen, dass 2 142 × 3 80 × 5 444 die nächste reguläre Zahl oben ist 2 2 × 3 454 × 5 249 +1 (die 100.000.000ste reguläre Zahl, die 392 Ziffern hat)
Hier ist eine andere Möglichkeit, an die ich gerade gedacht habe:
Wenn N X Bits lang ist, dann ist die kleinste reguläre Zahl R ≥ N in der Bereich
[2X-1, 2X]
z.B. Wenn N = 257 (binary 100000001 ) dann wissen wir, dass R 1xxxxxxxx ist, es sei denn R ist genau gleich der nächsten Potenz von 2 (512)
Um alle regulären Zahlen in diesem Bereich zu erzeugen, können wir zuerst die ungeraden regulären Zahlen (dh Vielfache der Potenzen von 3 und 5) erzeugen, dann jeden Wert nehmen und so oft (durch Bitverschiebung) mit 2 multiplizieren notwendig, um es in diesen Bereich zu bringen.
In Python:
%Vor%Weißt du was? Ich werde Geld auf den Vorschlag setzen, dass der "dumme" Algorithmus tatsächlich am schnellsten ist. Dies beruht auf der Beobachtung, dass die nächste reguläre Zahl im Allgemeinen nicht viel größer als die gegebene Eingabe zu sein scheint. Also fang einfach an zu zählen, und nach jedem Inkrement musst du umgestalten und sehen, ob du eine reguläre Nummer gefunden hast. Erstellen Sie jedoch einen Verarbeitungsthread für jeden verfügbaren Kern, den Sie haben, und für N-Kerne muss jeder Thread jede N-te Zahl untersuchen. Wenn jeder Thread eine Zahl gefunden oder den Schwellenwert für die Zweierpotenz überschritten hat, vergleiche die Ergebnisse (behalte die beste Zahl) und schon bist du dran.
Tags und Links algorithm math prime-factoring hamming-numbers smooth-numbers