Project Euler 12

Es geht in der Aufgabe darum, die erste Triangle-Number zu finden, die mehr als 500 Teiler hat.

Mein Ansatz war:

def triangle(n):
        return n * (n+1) / 2

def divisors(n):
        div = []
        for i in range(2,n+1):
                c = 0
                while n % i == 0:
                        c = c+1
                        n = n/i
                if c != 0:
                        div.append(c)
        p = 1
        for i in div:
                p = p* (i+1)
        return p

Anscheinend ist der divisors-Algorithmus nicht effizient genug

Mit Maple (numtheory[divisors]) erhalte ich die gesuchte Lösung recht flott.

Wie kann ich das Programm ein wenig aufmöbeln?

SG1

shisha schrieb:

for i in range(2,n+1):

[strike]Da würd ich nicht bis n, sondern nur bis sqrt(n) gehen, und jeweils n und n/i zur Liste hinzufügen. (Aufpassen bei Quadratzahlen!)[/strike]

edit: Was genau macht divisors eigentlich? Hatte zuerst den Namen falsch verstanden.

divisors bestimmt die anzahl der teiler.

Dafür bestimme ich die potenzen der primfaktorzerlegung.

12 = 2^2 * 3^1 -> [2,1]

Die Anzahl der Teiler ist dann (2+1) * (1+1)

bis sqrt(n) gehe ich nicht, da ich bei einer primzahl sonst probleme hätte mit der methode.

7 = 7^1 -> muss bis 7 sehen

eventuell wäre eine echte primfaktorzerlegung besser und dann ein reduce auf die liste?

Bashar

Kannst du mit der Information was anfangen, dass der Durchschnitt der Teilermengen von n und n+1 {1} ist?

Kannst du mit der Information was anfangen, dass der Durchschnitt der Teilermengen von n und n+1 {1} ist?

Ich weiß dass, das so ist, wüsste aber nicht inwiefern mir das helfen kann...

Ich kann zwar sagen, dass n und n+1 eine andere Primzahlenfaktorisierung haben, weiß aber nichts über die Anzahl der Teiler oder Potenzen der . Oder übersehe ich etwas?

camper

shisha schrieb:

Kannst du mit der Information was anfangen, dass der Durchschnitt der Teilermengen von n und n+1 {1} ist?

Ich weiß dass, das so ist, wüsste aber nicht inwiefern mir das helfen kann...

Ich kann zwar sagen, dass n und n+1 eine andere Primzahlenfaktorisierung haben, weiß aber nichts über die Anzahl der Teiler oder Potenzen der . Oder übersehe ich etwas?

Es bedeutet, dass du divisors(n*(n+1)/2) auf ganz einfache Weise auf divisors(n) und divisors(n+1) zurückführen kannst.

Bashar

Ich habs grad mal spaßeshalber nach meiner Idee in Matlab implementiert. Laufzeit ca. 1,6 Sekunden. Da du das Ergebnis schon mit Maple ermittelt hast, kannst du mir mal sagen, ob 76576500 = 12375*12376/2 richtig ist? Die Zahl hat, wenn ich richtig liege, 576 Teiler.

Michael E.

Das Ergebnis ist korrekt.

Bashar

Danke. Das Script zu posten wäre wahrscheinlich nicht im Sinne von Project Euler, deshalb lasse ich das mal. Es sollte auch nicht nötig sein.

Michael E.

Bashar schrieb:

Danke. Das Script zu posten wäre wahrscheinlich nicht im Sinne von Project Euler, deshalb lasse ich das mal. Es sollte auch nicht nötig sein.

Mit der korrekten Lösung hat man Zugriff auf das Forum, wo es dutzende Codes gibt

BTW: 1,6 Sekunden? Das klingt ganz schön lang für Matlab. Hast du eine vorgefertigte Tabelle für Primzahlen benutzt? Das sollte die Sache erheblich beschleunigen. Außerdem kann man immer die Faktorisierung von n+1 für die nächste Iteration behalten, sodass die Anzahl der Faktorisierungen sich halbiert. Natürlich sollte man bei geraden Zahlen n/2 und nicht n faktorisieren.

Bashar

Ich hab nicht mit Primzahlfaktorisierung gearbeitet, sondern wirklich mit allen Teilern.

ich hab's spaßeshalber in pharo smalltalk implementiert. 8-12 Millisekunden Rechenzeit und ca 12-16 Millisekunden mehr mit Ausgabe des Ergebnisses.
:xmas1:

Bashar schrieb:

Ich hab nicht mit Primzahlfaktorisierung gearbeitet, sondern wirklich mit allen Teilern.

Zeig mal bitte

Bashar

Tim schrieb:

Zeig mal bitte

function [n,m,d] = Euler12(N)
% Returns the smallest n such that the n-th triangle number (m = n(n+1)/2) has
% at least N divisors

n1 = 1;
d1 = 1;
n2 = 1;
d2 = 1;

D = 2;
while d1*d2 < N
    temp = n1;
    n1 = n2;
    n2 = temp + D;

    d1 = d2;
    d2 = Divisors(n2);

    if D == 1
        D = 2;
    else
        D = 1;
    end
end

n = n1;
m = n1*n2;
d = d1*d2;

function d = Divisors(n)
% returns the number of divisors of n
d = 1;
for i = 2:n
    if mod(n, i) == 0
        d = d + 1;
    end
end

Offensichtlich nicht optimal ich habs kurz vor (nicht nach;)) der :xmas1: :xmas2: Weihnachtsparty :xmas2: :xmas1: geschrieben und aufgehört als es lief. Jetzt nochmal mit Octave probiert, das bricht sich anscheinend stundenlang einen ab (was mir ehrlich gesagt spanisch vorkommt, ich hätte nicht mit Geschwindigkeitsunterschieden Faktor >100 gerechnet). Also besser vielleicht doch mit Primzahlzerlegung versuchen .... Und mit besseren Namen blabla :xmas1:

22 millisekunden

mult := [ :n :p || e q | 
	e := 0. q := p.
	[ n \\ q = 0 ] 
		whileTrue: [ 
			e := e+1. 
			q := q*p ]. 
	e+1 ].
primes := Integer primesUpTo: 19.
numberOfDivisors := [ :n | 
	primes 
		inject: 1 into: [ :prod :prime | 
			prod * (mult value: n value: prime) ] ].
run := [ | n | n := 1.
	[ | d | 
		d := numberOfDivisors value: n*(n+1)/2.
		d < 500 ] 
			whileTrue: [ n := n+1 ].
		Transcript  
			show: n asString ].
Time millisecondsToRun: [ run value ].

das Smiley in Zeile 1 steht für "Doppelpunkt p" :xmas2:

7 millisekunden und 5 ms mit -O3 bei mir - eig gar nicht so viel schneller als in smalltalk

#include<iostream>
typedef unsigned int Int;
Int mult(Int n, Int p){
  Int e = 0, q = p;
  while(!(n%q)){
    e++; q *= p;
  }
  return e+1;
}
Int Primes[] = { 2, 3, 5, 7, 11, 13, 17 };
Int numberOfDivisors(Int n){
  Int prod = 1, i = 0;
  while(i < 7)
    prod *= mult(n, Primes[i++]);
  return prod;
}
int main(void){
  Int n = 1;
  while(numberOfDivisors(n*(n+1)/2) < 500)
    n++;
  std::cout << n << std::endl;
  return 0;
}

Michael E.

Mach noch aus dem cout ein printf oder lass wenigstens endl weg. Wie viel schneller willst du es denn noch haben?

knivil

!rr!rr_. schrieb:

smalltalk implementiert. 8-12 Millisekunden Rechenzeit und ca 12-16 Millisekunden ... 7 millisekunden und 5 ms mit -O3 bei mir - eig gar nicht so viel schneller als in smalltalk ...

Nur leider helfen die Zahlen nicht wirklich beim Vergleich. Hier weiss niemand, welche Hardware du benutzt. Betriebsysteme koennten sich auch auf die Zeit auswirken.

Schaut man sich das pdf an (sichtbar, wenn das Problem gloest wurde) wird dort geschrieben:

When the above algo is written in assembly (including the generation of primes up to 1000) and almost fully optimized, it runs in less than 1 millisec on a P4-1500. It should easily run in less than 10 millisec when written in most modern compiled languages.

knivil schrieb:

Nur leider helfen die Zahlen nicht wirklich beim Vergleich. Hier weiss niemand, welche Hardware du benutzt. Betriebsysteme koennten sich auch auf die Zeit auswirken.

darum hat er ja den code geposted -.-

knivil

Und das soll es besser machen? Bei einem Quelltext weiss ich die Sprache sicher, bei den anderen ... hinzukommt Compiler/Interpreter/VM/Architektur ... etc.