Bibliothek zum Faktoriesieren von Zahlen

Columbo

T.K. schrieb:

Genaueres findet man unter http://matheplanet.com/matheplanet/nuke/html/article.php?sid=1163

Vielen Dank für den Link, der ist gut.

SG1

T.K. schrieb:

Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ .

Ja.

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Wieso?

SG1 schrieb:

T.K. schrieb:

Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ .

Ja.

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Wieso?

Weil nach jedem Schritt ein Primfaktor abgespalten wird.

Columbo

T.K. schrieb:

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Ich glaub du redest von einem anderen Problem. Das kann ich nicht nachvollziehen.
$15 = 3\cdot 5$
$35 = 5\cdot 7$
$57 = 3\cdot 19$
$319 = 11\cdot 29$
1129 ist zwar eine Primzahl, wir haben hier jedoch vier Schritte gebraucht um diese zu erreichen, wo du doch einen garantiert hast. Im Übrigen begreife ich die Logik nicht.

volkard

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Wir nehmen wirklich große Nicht-Primzahlen an, die schon eine Weile das Spiel gespielt haben, um so groß zu werden.
Die Zahl z habe 1000 Stellen.
Sie kann nur wachsen, wenn ein Teiler t so doof ist, daß len(t)+len(z/t)>len(z).
Also wenn sie einen kleinen Primfaktor hat wie 3, 7 oder 11.
2 kann nicht sein, weil z als letze Ziffern den größten Primfaktor des Vorgängers hat. Darum auch nicht 4, 5, 6 oder 8.
So große Zahlen schrumpfen also wieder.
Und weil sie nicht weiter wachsen können, fallen sie zwangsläufig irgendwann auf eine Primzahl.

Leider hat die Skizze zwei Lücken.
a) Das Wachstum ist nur "so für alle im Duchschnitt" begrenzt, es könnte doch eine Zahl geben, die ganz zufällig jedesmal eine 3 und z/3 ausspuckt und so immer weiter wächst.
b) Es könnte auch einen Zyklus von 17 Zahlen mit weniger als 1000 Stellen geben.

Bengo

T.K. schrieb:

Arcoth schrieb:

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Meinst du mich?

Natürlich. Du sagst Ja, aber diese Antwort ist nicht offensichtlich.

Ich finde es offensichtlich. Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ . Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Leider nicht ganz richtig. Es kann passieren, dass eine Zahl in einen Zyklus gerät. Zum Beispiel:
a -> b -> c -> b -> c -> b. Wird nie eine Primzahl.
Ich habe keine Ahnung, wie wahrscheinlich so ein Zyklus ist, aber bei unendlich vielen Zahlen kann es ja durchaus einen geben. Und nach so einem will ich mit meinem Programm suchen. Bisher ohne Erfolg (aber auch ohne schnelle Faktorisierung).

Die andere sehr unwahrscheinliche Möglichkeit ist, dass die Folge unendlich weiter geht, aber nie auf eine Primzahl stößt. Das ist unwahrscheinlich, weil die Zahl maximal etwa 2 Stellen pro Iteration gewinnen kann, die Primzahlen aber deutlich dichter liegen.

Noch eine andere Frage: Wenn ich eine Funktion hätte, die mir einen Faktor einer zahl ausgibt, wie mache ich darauf am besten die Primzahlfaktorzerlegung?

volkard

Bengo schrieb:

Noch eine andere Frage: Wenn ich eine Funktion hätte, die mir einen Faktor einer zahl ausgibt, wie mache ich darauf am besten die Primzahlfaktorzerlegung?

Habs damals rekursiv gemacht.

void spalte(bigint zahl,vector<bigint>& faktoren){
   if(istPrim(zahl))
      faktoren.push_back(zahl);
   else{
      f1=pollard(zahl);
      f2=zahl/f1;
      //fussnote
      spalte(f1,faktoren);
      spalte(f2,faktoren);
   }
}

//fussnote: spalte hat schon eine logarithmisch beschränkte Rekursionstiefe, aber wer Muffensausen hat, kann da gerne ein if(f1<f2)swap(s1,f2); machen und den zweiten spalte-Aufruf durch zahl=f2;goto anfang; ersetzen, dann isser sogar logarithmisch mit der Stellenzahl, wenn ich mich nicht irre.

volkard

Hab ein wenig getestet.
Also die 20 hats schon in sich:
20=2^25
225=3^2*52
3252=2^2*3*271
223271=297699
297699=399233
399233=715623
715623=3*263*907
und so weiter…

volkard schrieb:

Benutzt afair pollard's rho und war als ich's letzte mal reinschaute ein guter Kompromiss zwischen Schnell und Einfach.

Naja, bin mit pollard-rho ruck zuck an die Grenzen meines Rechner gekommen.

Bengo schrieb:

Das ist unwahrscheinlich, weil die Zahl maximal etwa 2 Stellen pro Iteration gewinnen kann, die Primzahlen aber deutlich dichter liegen.

43467514876394875501133442699882620583081205227=
3^2*101*189437*3310762051*6411638533*11891567953317269293->
321011894373310762051641163853311891567953317269293
Vier Stellen gewonnen.

volkard schrieb:

Sie kann nur wachsen, wenn ein Teiler t so doof ist, daß len(t)+len(z/t)>len(z).
Also wenn sie einen kleinen Primfaktor hat wie 3, 7 oder 11.

Das müssen keine kleinen Primfaktoren sein.
101538353409718995449=10007*10009*10037*10039*10061 =>
1000710009100371003910061

Deine Bedingung ist also weder hinreichend noch notwendig.

volkard

Leider gibt es auch Zahlen, die stark verlieren.

1076540344177317317=83^3*1882764638191->
8331882764638191

1121258912099531021=58147^2*331628069
581472331628069

Das liegt an dieser willkürlichen ^q-Regel. Hast du ein konkretes Beispiel mit verschiedenen Primzahlen, das schrumpft?

volkard schrieb:

2 kann nicht sein, weil z als letze Ziffern den größten Primfaktor des Vorgängers hat.

Der kann aber mehrmals auftreten (z.B. 2 mal) und dann ist eine 2 wiederum möglich.

volkard

kleinaberprime schrieb:

Das liegt an dieser willkürlichen ^q-Regel. Hast du ein konkretes Beispiel mit verschiedenen Primzahlen, das schrumpft?

Nee, nur mit p1^q*…

volkard

volkard schrieb:

kleinaberprime schrieb:

Das liegt an dieser willkürlichen ^q-Regel. Hast du ein konkretes Beispiel mit verschiedenen Primzahlen, das schrumpft?

Nee, nur mit p1^q*…

Beispiel, wo es nicht der kleinste Primfaktor ist:
967432285582247915=5*227^2*3754904172727
522723754904172727

Verschiedene Primzahlen schrumpfen nicht, würde ich meinen. Hast ja ein schönes Beispiel mit "minimalen" Primzahlen gebaut.

Bengo

volkard schrieb:

Hab ein wenig getestet.
Also die 20 hats schon in sich:
20=2^25
225=3^2*52
3252=2^2*3*271
223271=297699
297699=399233
399233=715623
715623=3*263*907
und so weiter…

volkard schrieb:

Benutzt afair pollard's rho und war als ich's letzte mal reinschaute ein guter Kompromiss zwischen Schnell und Einfach.

Naja, bin mit pollard-rho ruck zuck an die Grenzen meines Rechner gekommen.

Bengo schrieb:

Das ist unwahrscheinlich, weil die Zahl maximal etwa 2 Stellen pro Iteration gewinnen kann, die Primzahlen aber deutlich dichter liegen.

43467514876394875501133442699882620583081205227=
3^2*101*189437*3310762051*6411638533*11891567953317269293->
321011894373310762051641163853311891567953317269293
Vier Stellen gewonnen.

Ja hast recht, sind vier Stellen, aber immernoch weniger, als die Primzahldichte. Soweit ich weiß, ist der Fall 20 bis heute nicht geklärt, und das Problem ist auch ziemlich sicher noch nicht gelöst worden. Ist eins der 1000$ Problems von John Conway https://oeis.org/A248380/a248380.pdf . Er hat aber gesagt, er zahlt auch 1000€ wenn es einer löst

Ich hab jetzt glaube so ziemlich alle meine Möglichkeiten ausgereizt, um mit einem Programm ein Gegenbeispiel zu finden, jetzt bruach ich entweder viel Glück, oder muss noch mal mathematisch ran gehen. Vielleicht wird wirklich echt jede zahl zu einer Primzahl (Conway selbst ist davon recht überzeugt).

Arcoth schrieb:

Ich glaub du redest von einem anderen Problem.

Ja, hab mich verlesen.

@Bengo: Bist du noch am MPQS interessiert?

T.K. schrieb:

@Bengo: Bist du noch am MPQS interessiert?

Poste sie doch einfach.

Gulasch schrieb:

T.K. schrieb:

@Bengo: Bist du noch am MPQS interessiert?

Poste sie doch einfach.

Das ganze Projekt hat AFAIR ca. 10000 Zeilen C++-Code. Der MPQS-Code vielleicht 1000.

Bengo

Denke hat sich erst mal erledigt, hab schon sehr effizienten Code. Bisher nur leider kein Ergebnis