Hallo,
Ein noch offenes mathematisches Problem ist die Frage nach sogenannten Teilersummen oder Inhaltsketten. Darunter versteht man:
Gegeben ist eine Zahl a1. Die Summe deren echten Teiler und der 1 sei a2. Deren Teilersumme a3, usw. en.wikipedia.org/wiki/Aliquot_sequence

Berechnet man diese Folge, so endet diese oft bei 1, allerdings nicht immer. Die Folge kann auch zyklisch werden, z.B. bei vollkommenen Zahlen wie der 6, 28 oder 496, bei sozialen Zahlen wie 220 und 284, bzw. in sozialen Ketten wie 12496, 14288, 15472, 14536, 14264, 12496, ...
Allerdings gibt es auch Startzahlen ohne bekannte Folgenentwicklung. Berühmt ist die 276, welche zu den "Lehmer-Five" gehört. www.aliquot.de/tabellen/lehmer.htm

Die Probleme der Folgenberechnung sind:
1. die Bestimmung der Primteiler
2. die Bestimmung der Teilersumme selbst
Für das erste Problem muss man schnelle Faktorisierungsverfahren nutzen, für das zweite Problem muss aus den Primteilern die Summe berechnet werden.

Mein Programmbeispiel mit Quelltext nutzt zur Faktorisierung Probedivisionen und das Pollard-Rho-Verfahren. Die Summe wird nach de.wikipedia.org/wiki/Teilersumme berechnet.
Das Programm ist hinreichend schnell, stößt aber doch auf seine Grenzen. Von der berühmten Startzahl 276 können in vernünftiger Zeit nur etwa 150 Folgenglieder ermittelt werden.
Da der Quelltext doch etwas komplexer ist, wäre es schön, wenn jemand von Euch mal ein paar Startzahlen testen könnte.
Beste Grüße
Mathematiker

Hallo,
dank der Hilfe von Lelf bei meinem Faktorisierungsprogramm gibt es noch eine zusätzliche Version mit dem Brent-Rho-Verfahren statt dem Pollard-Verfahren.
Es ist ein ganzes Stück schneller.
Beste Grüße
Mathematiker

Hallo Mathematiker, Deine in dieser Diskussion vorgestellten Zerlegungen - auch wenn nicht ganz so zuverlässig wie die Probedivisionen (und andere Verfahren), denen nichts verborgen bleibt - verdienen Anerkennung und Respekt.

Was mir auffällt: Deine Formulare bleiben insofern bedienbar, als daß sie sich selbst neu zeichnen und verschiebbar sind. Arbeitest Du mit Application.Processmessages und / oder mit (mindestens) einem zusätzlichen (Rechen-)Thread (ja, könnte ich auch im Quelltext nachschlagen, doch mich da auf die Schnelle zurechtzufinden....)?

Allerdings weigert sich Dein Programm erstaunlicherweise hartnäckig, bei Klick auf den Beenden-Knopf sich auch zu beenden. Dieser Knopf selbst reagiert allerdings auf Druck auf ihn. Minimieren und Maximieren funktionieren hingegen bei laufender Berechnung. Vermutlich müßte dieser Klick ausgewertet und die Berechnung daraufhin abgebrochen werden, was nicht implementiert ist, nicht wahr?

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

Was mir auffällt: Deine Formulare bleiben insofern bedienbar, als daß sie sich selbst neu zeichnen und verschiebbar sind. Arbeitest Du mit Application.Processmessages ...

Ja, an mehreren Stellen des Textes habe ich Application.Processmessages und einen Test auf Abbruch eingefügt.

Delphi-Laie hat folgendes geschrieben :

Allerdings weigert sich Dein Programm erstaunlicherweise hartnäckig, bei Klick auf den Beenden-Knopf sich auch zu beenden.

Mein Fehler; muss ich noch ändern. Ich habe vergessen in der Close-Methode des Formulars den Abbruch der Berechnung abzufragen.

Läuft die Berechnung, geht das Programm damit nicht zu.
Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

markieren Delphi-Quelltext     1: 2: if abbruch=false then begin abbruch:=true; exit end;  end;

Ein Quentchen eleganter wäre: if not abbruch...

Es gab schon unzählige Diskussionen darob, warum man Boolsche Werte nicht direkt miteinander vergleichen sollte. Aus der Sicht der Hochsprache ist es nicht falsch, aber eben unelegant. Wobei false auf 0 gesetzt wird und der Vergleich damit immer zutrifft. Bei true sieht es anders aus (was ich allerdings genaugenommen für einen Compilerfehler halte). Du kannst m.E. auch auf diese Abfrage vorab verzichten und gleich abbruch:=true setzen. Die Ergebnismenge müßte identisch sein: In allen Fällen (beiden Zeilen und egal, ob abbruch mit false oder true einsteigt) geht abbruch immer mit true hervor.

Mathematiker hat folgendes geschrieben :

Läuft die Berechnung, geht das Programm damit nicht zu.

Womit? Mit Deiner obigen Quelltextzeile? Damit wird doch der Abbruch vorbereitet?!

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

Ein Quentchen eleganter wäre: if not abbruch...

Asche auf mein Haupt. Du hast recht. Irgendwann habe ich mir angewöhnt alle boolean-Variablen so abzufragen. Und alte Gewohnheiten wird man nicht so schnell los.

Delphi-Laie hat folgendes geschrieben :

Mathematiker hat folgendes geschrieben : Läuft die Berechnung, geht das Programm damit nicht zu. Womit? Mit Deiner obigen Quelltextzeile? Damit wird doch der Abbruch vorbereitet?!

Das ist nicht elegant, aber effektiv. Während die Berechnung läuft ist abbruch=false . Klickst Du auf Abbrechen, muss die Berechnung erst gestoppt werden, andernfalls gibt es Probleme bei der Speicherfreigabe. Deshalb stoppe ich erst einmal die Rechnung. Und erst bei einem zweiten Klick auf Abbrechen geht das Programm zu.
Wie gesagt: nicht elegant. Da aber die Teilersuche rekursiv läuft, sehe ich im Moment keine andere Möglichkeit, korrekt die Rekursion und das Programm ohne Speicherlecks zu verlassen. Jedenfalls kenne ich keine. Vielleicht, weiß jemand Rat.
Beste Grüße
Mathematiker

Hallo,

sicherlich ist es schon bekannt, daß die Zahl 1248 eine endliche Teilersummenfolge besitzt.
Ich wurde von Mathematiker mit seinen Anregungen der Primzahl-Zerlegung auf dieses Thema aufmerksam gemacht und will nun das Ergebis präsentieren. Aber die Frage, ob das alles einen Sinn macht, kann ich noch nicht beantworten.

Gruß Lelf

Hallo Lelf,
starke Leistung und in nur 8 Minuten? Wie hast Du denn das gemacht? Oder anders gefragt, was für einen Supercomputer oder Superprogramm hast Du denn?
Ich habe aber eine weitere "Herausforderung" für Dich. Wie wäre es denn mit der Startzahl 43230. Die Folge hat 4356 Glieder.

Lelf hat folgendes geschrieben :

Aber die Frage, ob das alles einen Sinn macht, kann ich noch nicht beantworten.

Warum braucht man immer einen bedeutungsvollen Sinn? Die Aufgabe gibt es, also versucht man diese zu lösen. Es macht Spaß und man freut sich, wenn man eine noch längere Folge gefunden hat. Und irgendwann wird es jemanden gelingen, die Folge der 276 zu knacken.
Beste Grüße
Mathematiker

Hallo Mathematiker,

also, mein Computer hat sich gefreut, als ich ihn bei der Teilersummenfolge-Berechnung von 43230 nach 863 Gliedern (die zu faktorisierenden Zahlen sind hier 79-stellig) und einer Laufzeit von 11 Stunden, abgeschaltet habe: "Ich kann nicht mehr", hat er gesagt und weiter: "Du kannst jetzt in Urlaub fahren, und ich habe 4 Wochen lang meine Ruhe."

Bis bald Lelf, aber ich bleib' dran.

Hallo,

Nach erholsamen Urlaubstagen durften mein Computer und ich wieder arbeiten.
Die 43230-Teilersummen-Folge ist schon ein harte Nuss und hat einige schwächen in meinem Programm aufgedeckt.
Mir ging es hauptsächlich darum, die Richtigkeit der Berechnungen und Faktorisierung grosser Zahlen zu überprüfen.
Und tatsächlich: die 4357. Folge ist 1. Falls jemand Interesse an langen Zahlenkollonnen haben sollte, kann er hier nachschauen.

Gruß Lelf

Hallo Lelf,

Lelf hat folgendes geschrieben :

Die 43230-Teilersummen-Folge ist schon ein harte Nuss

Starke Leistung! Ich habe die Berechnung mit meinem langsamen Programm nach 24 Stunden aufgegeben.
Bei der Analyse Deiner 43230-Berechnung habe ich gelesen:
"MPQS with one large prime (multi polynomial quadratic sieve)"
Hast Du tatsächlich eine Delphi-Lösung für ein MPQ-Sieb? Alle Achtung.
Beste Grüße
Mathematiker