Sämtliche Zahlen in einer Liste miteinander multiplizieren

[Eliazz]

Hallo ich sitze gerade an dem Problem:
"Highly divisible triangular number" (12) von projecteuler.net... Hier ein link: http://projecteuler.net/problem=12
Ich habe da gestern schon den großteil von gemacht und will/werde das Problem mit einer Primfaktorzerlegung lösen, die auch schon echt super klappt. Im grunde folgendes: Jede Zahl kann in eine unbekannte Nummer von Primzahlen aufgelöst werden, so ist 1025 z.b: 5 * 5 * 41.
Ich weiß, das mann sämtliche natürliche Teiler einer Zahl bekommt indem man alle Möglichen Kombies Durchrechnet (und die 1 dazunimmt ^^)
Für 1025: 5 , 5 , 45 , 5 * 5 = 25 , 5 * 41 = 205 , 5 * 5 * 41 = 1025. Ich habe das Programm nun schon soweit, dass ich eine Liste mit allen Primfaktoren habe. Ich muss (möglichst schnell) für große Zahlen jetzt die Anzahl der Teiler einer Zahl daraus errechnen. Danach prüfe ich ob diese Anzahl über 500 liegt ( Man muss die erste Zahl finden, bei der sie über 500 liegt) und gebe sie dann gegebenenfalls aus (oder mache eben weiter). Das Problem dabei ist, das die Anzahl der Primfaktoren natürlich variiert. Ich wüßte jetzt zwar, wie ich ein Programm schreibe, dass alle 2er Kombies oder 3er Kombies ausrechnet, aber ich kann das ja schlecht bis 500 machen und immer prüfen wie lang die Liste ist. Ich brauche also eine Funktion. Aber ich weiß nicht wie ich das mache, dass er die einzelnen Elemente einer Liste als Parameter nimmt und dann eben das tut, was ich beschrieben habe. Hat jemand eine Idee?
MFG

[BlackJack]

@Eliazz: Also erst einmal eine Anmerkung zu Project Euler: Die allermeisten Probleme haben eine Lösung die wenig Rechenarbeit erfordert wenn man den richtigen Ansatz kennt oder herausfindet. Es gibt also eigentlich immer einen besseren Ansatz als viele Möglichkeiten durchzurechnen. Vieles kann man auch ohne Rechner mit Stift und Papier lösen, wenn man den richtigen Ansatz gefunden hat.

Selbst für „brute force” scheinst Du aber von der falschen Seite anzufangen. Die Frage ist doch welche „triangle number” mehr als 500 Teiler hat. Da wäre doch der erste Schritt alle „triangle numbers” zu erzeugen, zum Beispiel mit einer Generatorfunktion. Und dann brauchst Du eine Funktion die eine Zahl in Teiler zerlegt. Und zwar nicht nur solche die Prim sind, sondern alle. Dazu müsste man die Primfaktorzerlegung etwas anpassen, dass sie nicht nur Primteiler sondern alle Teiler liefert. Wo man dabei auf das Problem stösst was Du jetzt in der Frage stehen hast, ist mir nicht so ganz klar!? Das wäre auch ganz furchtbar ineffizient.

Wenn man die Faktorzerlegung hat, kann man die auf jede „triangle number” anwenden, solange bis die Faktoranzahl grösser 500 ist.

[Eliazz]

Da sieht man, dass du mich völlig falsch verstanden hast.... -.-
Natürlich habe ich Triangle Numbres erzeugt, ich wollte euch das ersparen, weil es nicht teil des Problems ist. Und wenn du dir meine Frage durchlesen würdest wüsstest du, das ich ERST in Primzahlen zerlege um diese dann DANACH miteinander multipliziere(n) will... Brute Forcing wäre, alle zahlen von der zahl x bis 1 durchzuprobieren und dann wenn es klappt einen counter hochzuzählen... Geht bestimmt auch, aber dauert ewig, also kann mir jetzt jemand sagen, was ich eigentlich gefragt habe?
Listen durchmultiplizieren. Belehrungen zu meinem Ansatz wollte ich nämlich erstmal gar nicht, sonst hätte ich Code angehängt, danke

[Eliazz]

Ps: Natürlich muss ich die Triangle Zahlen an sich durchprobieren! Oder was schlägst du vor? Ja klar, ich könnte Stichproben machen oder so was, aber ich muss ja ertsmal die Möglichkeit haben, Proben zu machen... Ich habe mich lange mit einem Mathematiker über die Sache mit der Anzahl der Möglichkeiten unterhalten und das ist eine gute herangehensweise.... Es geht mir nur um den Programmierasspekt.

[Eliazz]

Okay, kleine Anmerkung: Ich weiß, dass ich für eine Zahl x eine Liste mit Primzahlen habe...
Und ich weiß, wenn ich in dieser Liste alles durchprobiere, habe ich die Teiler.... Aber wie Durchprobieren?

[BlackJack]

@Eliazz: Du hast doch eine Zahl `x` und all ihre Primfaktoren. Und nun denk mit dem durchprobieren mal nicht so kompliziert und vergiss die Multiplikation.

[Eliazz]

Okay, was soll ich denn machen?
Ahhh Fakultät oder so?
Kenn ich noch aus Mathe... MHHH

[BlackJack]

@Eliazz: Fakultät ist auch zu kompliziert. Bleib mal bei den Grundrechenarten.

[Eliazz]

Magst du mir nicht einfach helfen? Es ist nicht so leicht wie du sagst: Bitte bedenke, zahlen dürfen nicht doppelt gezählt werden, 3*2 ist 2*3.
Außerdem gibt es ja seeeeeehr viele Kombis wenn es viele zahlen gibt.. Also... WIE?

[BlackJack]

@Eliazz: Ich hatte daran gedacht die Zahl durch die Primfaktoren zu teilen. Bin mir aber nun unsicher ob das nicht nur für die Beispiele funktioniert die ich ausprobiert habe, bzw. halbwegs sicher dass es nicht verallgemeinerbar ist.

Dafür kenne ich mittlerweile eine halbwegs einfache Lösung. Zumindest was die Formel und Umsetzung in Code angeht. Ich bin mir aber ziemlich sicher, dass ich da nicht selbst drauf gekommen wäre.

[Eliazz]

Okay und wo ist diese geheime Lösung?
Meine Idee wäre, dass doch über ne Fakultät laufen zu lassen und alle doppelten herauszunehmen...

[BlackJack]

@Eliazz: Die geheime Lösung ist auf Wikipedia versteckt. Die Funktion mit der man die Anzahl der Teiler berechnen kann, hat nämlich einen eigenen Namen und deshalb auch eine Wikipedia-Seite. Der Name lautet „Teileranzahlfunktion”.

[Eliazz]

Hör mal... Das mag ja alles sein und ich werde das Problem auch gleich gelöst haben... Aber meine Frage ist doch eine ganz andere:
Ich möchte eine Funktion, die sämtliche Kombies in einer Liste durchrechnet, nur ich weiß nicht wie! Seöbst wenn ich das Problem gelöst habe, das ist doch auch für die Zukunft interessant!

[BlackJack]

@Eliazz: Na im Grunde weisst Du doch wie, Du hast es ja selbst schon skizziert: Du musst alle Kombinationen aufzählen, erst die mit zwei Zahlen, dann die mit drei, vier, und so weiter bis zur Länge der Liste. Und dann jede dieser aufgezählten Kombinationen ausmultiplizieren. Da dabei gleiche Werte heraus kommen können, muss man die Zahlen in eine Menge stecken um das auszufiltern.

Zum Aufzählen von Teil- und Potenzmengen gibt es im `itertools`-Modul passende Funktionen.

[BlackJack]

Hier ist eine mögliche Implementierung:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from itertools import chain, count, combinations, imap
from operator import mul


def product(values):
    return reduce(mul, values, 1)


def iter_prime_factors(number):
    for candidate in chain([2], count(3, 2)):
        while number % candidate == 0:
            yield candidate
            number /= candidate
            if number == 1:
                return


def calculate_divisors(number):
    divisors = set([1])
    prime_factors = list(iter_prime_factors(number))
    divisors.update(
        imap(
            product,
            chain.from_iterable(
                combinations(prime_factors, length)
                for length in xrange(1, len(prime_factors) + 1)
            )
        )
    )
    return divisors


def main():
    number = 228627036
    print list(iter_prime_factors(number))
    divisors = calculate_divisors(number)
    print divisors
    print len(divisors)


if __name__ == '__main__':
    main()

Die Primfaktorzerlegung für eine allgemeine ganze Zahl ist natürlich nur effizient solange man nur *eine* Zahl während des Programmlaufs auf diese Weise zerlegt. Wenn man das wiederholt machen muss, könnte man Primzahlen erzeugen und cachen, und damit viele Divisionen/Tests sparen.

[BlackJack]

Vedammt noch eins, gerade als ich den letzten Beitrag abgeschickt hatte fiel mir eine bessere Lösung ein, also eine die wirklich nur *direkt* die Teiler aufzählt ohne Doubletten:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from itertools import chain, count, imap, product as cartesian_product
from operator import mul


def product(values):
    return reduce(mul, values, 1)


def iter_prime_factors(number):
    for candidate in chain([2], count(3, 2)):
        exponent = 0
        while number % candidate == 0:
            number /= candidate
            exponent += 1
        if exponent:
            yield (candidate, exponent)
        if number == 1:
            return


def iter_divisors(number):
    powers = [
        [prime**i for i in xrange(exponent + 1)]
        for prime, exponent in iter_prime_factors(number)
    ]
    return imap(product, cartesian_product(*powers))


def main():
    number = 228627036
    print list(iter_prime_factors(number))
    divisors = list(iter_divisors(number))
    print divisors
    print len(divisors)


if __name__ == '__main__':
    main()

Ich nehme auch zurück dass ich nicht selbst auf die Teileranzahlfunktion gekommen wäre, denn die ergibt sich aus dieser Lösung trivialerweise.