[ZT] fast-quadratischer Teiler

Neue Frage »

Milbrae Auf diesen Beitrag antworten »
[ZT] fast-quadratischer Teiler
Ich habe bei Programming Praxis einen interessanten Artikel gefunden, der m. E. etwas zahlentheoretische Aufarbeitung benötigt. Zu finden ist der Artikel hier: programmingpraxis . com / 2016 / 08 / 05 / nearly-square-divisors.
(Könnte ein Admin bitte den Link einfügen? Danke Freude )

Es geht darum, dass zu einer Zahl n die Zahlen a und b gefunden werden sollen, so dass gilt und die Differenz von a und b minimiert ist. Wenn n eine Quadratzahl ist, dann ist .
Andernfalls ergibt sich für n = 60 bspw. a = 10, b = 6. Gesucht wird in dem Beispiel auf PP der fast-quadratische Teiler für n = 224403121196654400.

Ich habe hierfür ein kleines Python-Programm gepostet:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
import math

def nsd(n):
    s = (int)(math.sqrt(n))
    while n % s:
        s -= 1
    print s
    print n // s

n = 224403121196654400
nsd(n)
Ergebnis ist b = 473670855, a = 473753280.

Für solche Zahlen ist das Ergebnis mit der Routine nsd() relativ schnell zu berechnen. Wenn sich n aber wie folgt zusammensetzt: n = 2**3 * 3**2 * 5 * 7 * 11**2 * 23 * 67 * 73**2 * 83 * 89 * 97 * 101 * 103 * 107 = 1997176648439957666247720
...brauche ich bereits ca. 26 Sekunden für die Berechnung, mit Pypy immerhin nur 6.

Ich schätze, man kann die gesamte Operation immens beschleunigen, wenn man die Primfaktoren von n näher unter die Lupe nimmt. Ich weiß nur noch nicht genau wie. Meiner Meinung nach könnte man auch alle Teiler von n betrachten. 1997176648439957666247720 hat aber schon 110592 Teiler. Bei Zahlen mit noch mehr Primteilern bzw. größeren Primteilerpotenzen wächst diese Zahl schnell ins Unermessliche.
Milbrae Auf diesen Beitrag antworten »

Für bessere Lesbarkeit habe ich das Programm minimal geändert:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
import math, string

def nsd(n):
    s = (int)(math.sqrt(n))
    while n % s:
        s -= 1
    print ("a = " + string.strip(str(n // s)))
    print ("b = " + string.strip(str(s)))


n = 224403121196654400
print ("n = " + string.strip(str(n)))
nsd(n)
Ausgabe:
code:
1:
2:
3:
4:
n = 224403121196654400
a = 473753280
b = 473670855
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Milbrae
Wenn sich n aber wie folgt zusammensetzt: n = 2**3 * 3**2 * 5 * 7 * 11**2 * 23 * 67 * 73**2 * 83 * 89 * 97 * 101 * 103 * 107 = 1997176648439957666247720
...brauche ich bereits ca. 26 Sekunden für die Berechnung, mit Pypy immerhin nur 6.

[...] Meiner Meinung nach könnte man auch alle Teiler von n betrachten.

Wohl wahr, zumal dann wenn man (wie bei dir) die Primfaktorzerlegung bereits kennt! Z.B. hat dein n "nur" Teiler - selbst wenn man die alle berechnet, ist man weit schneller als die von dir genannten Zeiten.
Milbrae Auf diesen Beitrag antworten »

Wenn nicht HAL, wer sonst Wink

Das n mit gerade mal 110.592 Teilern ist zwar ein zeitaufwendigeres aber vielleicht auch ungeeignetes Beispiel. Es heißt ja immer "Think big!". Was also wenn n das Produkt der Primzahlen < 1.000 ist? Dann hätte n zwar nur 168 Primfaktoren, die läppern sich insgesamt aber zu 374.144.419.156.711.147.060.143.317.175.368.453.031.918.731.001.856 Teilern. Die alle zu prüfen wäre ganz schön ermüdend...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Milbrae
Was also wenn n das Produkt der Primzahlen < 1.000 ist? Dann hätte n zwar nur 168 Primfaktoren, die läppern sich insgesamt aber zu 374.144.419.156.711.147.060.143.317.175.368.453.031.918.731.001.856 Teilern. Die alle zu prüfen wäre ganz schön ermüdend...

Richtig, in dem Fall sollte man "intelligenter" vorgehen, also nicht alle Teiler betrachten.

Wie auch immer, meine Anmerkung bezog sich ja auch nur auf den Vergleich zu deinem ersten Algorithmus. Und wie der sich bei "n das Produkt der Primzahlen < 1.000" verhält, darüber wollen wir wohl besser mal den Mantel des Schweigens decken. Big Laugh
Milbrae Auf diesen Beitrag antworten »

Warum wollen wir das? verwirrt
 
 
HAL 9000 Auf diesen Beitrag antworten »

Das meinst du jetzt nicht ernst, oder? unglücklich
Milbrae Auf diesen Beitrag antworten »

Hammer Fehler gefunden. Wir wollen das wirklich nicht.

Ich vermute, die "intelligentere" Variante hat mit der Primfaktorisierung zu tun. Für n = 1.000# sind das ja nur 168 Faktoren.
Milbrae Auf diesen Beitrag antworten »

Auf ProgrammingPraxis gab's jetzt den Hinweis eines Nutzers zu einer Variante des Rucksack-Problems. Das Prinzip, warum das so ist, hab ich noch nicht ganz durchschaut. Das Haskell-Programm (wovon ich gar keine Ahnung hab), das er vorschlägt, scheint ganz gut zu funktionieren und gibt den Exponenten der e-Funktion zur Lösung wider.
HAL 9000 Auf diesen Beitrag antworten »

Stimmt - logarithmiert ähnelt es dem Rucksackproblem.
RavenOnJ Auf diesen Beitrag antworten »

Ich habe das Haskell-Programm des Users matthew in deinem Link etwas gepimpt. Die Funktion largestSubset gibt die Liste aus, die der geforderten Bedingung entspricht:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
-- largestSubset setzt nicht voraus, dass die Liste [a] geordnet ist

largestSubset:: (Num a,Ord a)=> a -> [a] -> [a]
largestSubset t (x:xs)  | x:xs == [] = []
	| xs == [] = if x <= t then [x] else []
	| x > t = largestSubset t xs
	| otherwise = if sum(fst r) > sum(snd r) then fst r else snd r
			where r = (largestSubset t xs,x:largestSubset (t-x) xs)

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]::[Integer]
s = map (log .fromIntegral) $ primes
target = sum s/2

main = print("primes ="++ show primes ) >>
	print ("target = " ++ show target ++ ", entspricht " ++ show (round . exp$ target))>>
	print ("Summe logs Ergebnisliste: " ++ show(sum r)) >> 
	print( "Ergebnisliste: " ++show u) >> 
	print( "Produkt Ergebnisliste: " ++ show m) >> 
	print( "Produkt Restliste: " ++ show n) >>
	print("Produkt primes: "++ show p)
		where {r = largestSubset target s;
		u = map (round . exp) $ r;
		m = foldl (*) 1 u;
		p = foldl (*) 1 primes;
		n = p `div` m}


Laufzeit auf meinem ein paar Jahre alten Rechner (2 Kerne arbeiten parallel): 3 sec.
Das Ergebnis:
"primes =[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]"
"target = 30.7931475747082, entspricht 23620771158595"
"Summe logs Ergebnisliste: 30.793095488055403"
"Ergebnisliste: [2,3,5,7,17,19,37,41,53,61,71]"
"Produkt Ergebnisliste: 23619540863730"
"Produkt Restliste: 23622001517543"
"Produkt primes: 557940830126698960967415390"

Edit: Für das Problem auf PP ergibt sich (Laufzeit 15 s; der große Laufzeitunterschied liegt an den zusätzlichen zwei Primfaktoren. Jeder weitere Faktor bringt eine Verdopplung des Baumes. 22 gegenüber 20 also ca. Faktor 4):
"primes =[2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37]"
"target = 19.976110238769248, entspricht 473712066"
"Summe logs Ergebnisliste: 19.976023239718703"
"Ergebnisliste: [37,31,23,19,7,5,3,3,3]"
"Produkt Ergebnisliste: 473670855"
"Produkt Restliste: 473753280"
"Produkt primes: 224403121196654400"
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »