Bibliothek zum Faktoriesieren von Zahlen
-
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 =>
1000710009100371003910061Deine Bedingung ist also weder hinreichend noch notwendig.
-
Leider gibt es auch Zahlen, die stark verlieren.
1076540344177317317=83^3*1882764638191->
83318827646381911121258912099531021=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.
-
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 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
522723754904172727Verschiedene Primzahlen schrumpfen nicht, würde ich meinen. Hast ja ein schönes Beispiel mit "minimalen" Primzahlen gebaut.
-
volkard schrieb:
Hab ein wenig getestet.
Also die 20 hats schon in sich:
20=2^25
225=32*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?
-
-
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.
-
Denke hat sich erst mal erledigt, hab schon sehr effizienten Code. Bisher nur leider kein Ergebnis
-
T.K. schrieb:
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.
Github?
