Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / ... und Spiele: Mengen und Teilmengen
1 2 Previous Next  
- - By Ulf Flörsheimer Date 2016-08-20 13:34
Vor kurzem bin ich auf eine interessante Aufgabe gestoßen: Es soll eine Menge aus 12 Zahlen gefunden werden. Aus dieser Menge sollen nun auf jede erdenkliche Weise drei Zahlen gezogen und jeweils deren Summe gebildet werden. Die Summen aller Tripel sollen unterschiedlich sein, so dass bei Kenntnis der Menge aus einer Tripel-Summe eindeutig auf die drei Zahlen des Tripels zu schließen ist. Die Zahlen sollen zudem so gewählt werden, dass die Summe des größten Tripels möglichst klein wird.

Ich will die trockene Beschreibung an einem kleinen Beispiel mit nur 5 Zahlen erläutern:

Die betrachtete Menge sei {1,  4, 7, 9, 13}.
Die möglichen Tripel und ihre Summen lauten:
{1, 4, 7}  ==> 12
{1, 4, 9}  ==> 14
{1, 4, 13}  ==> 18
{1, 7, 9}  ==> 17
{1, 7, 13}  ==> 21
{1, 9, 13}  ==> 23
{4, 7, 9}  ==> 20
{4, 7, 13}  ==> 24
{4, 9, 13}  ==> 26
{7, 9, 13}  ==> 29

Da alle Tripel zu unterschiedlichen Summenwerten führen, wäre die Basismenge eine legale Lösung für eine Grundgesamtheit mit 5 Elementen. Ihre maximale Teilsumme ist die 29. Es wäre nun die Frage, ob es Mengen mit kleineren maximalen Teilsummen gibt.

Aber nun zurück zu dem Problem mit den 12 Zahlen. Im Prinzip ist es einfach, eine Lösung zu finden: Nehmen wir einfach folgende Zahlen 1, 10, 100, 1000, ..., 100000000000. Die Summe der Tripel ist offensichtlich eindeutig und die maximale Summe beträgt 111000000000. Intuitiv ist klar, dass es auch unter 111 Milliarden gehen sollte.

Wer sich mit dem Binärsystem auskennt, wird die obigen Zahlen vielleicht als Binärzahlen interpretieren. Das Ergebnis ist dann genau so eindeutig und die maximale Summe 111000000000(binär) entspricht 3584(dezimal).

Aber auch 3584 erscheint noch immer ziemlich groß. Habt ihr bessere Vorschläge für die zwölf Zahlen der Menge? Ich würde mich über Lösungsvorschläge sehr freuen.

Schönes Wochenende
Ulf
Parent - - By Frank Brenner Date 2016-08-20 16:47 Edited 2016-08-20 16:57
Ad hoc  sind mir folgende 12 Zahlen eingefallen die man im Kopf berechnen kann:

1,2,3,5,8,14,25,45,82,150,272,502

Summe der drei höchsten = 924
Parent - - By Ulf Flörsheimer Date 2016-08-20 16:59
Eingefallen ist gut! Unter 1000 ist für den Anfang schon mal echt nicht schlecht! Ich weiß nicht, wie du es genau angestellt hat, aber im Laufe meiner Spielereien bin ich auf vergleichbare Ergebnisse gekommen.

Ich kenne selbst keine Optimallösung und würde später gerne über die Vorgehensweise diskutieren, aber für jetzt möchte ich erst mal sagen: Falls du noch Lust zum Puzzeln hast, es geht auf jeden Fall noch ein Stück besser!

Ich freue mich auf mehr von Dir ... und vielleicht auch von anderen.
Parent - - By Frank Brenner Date 2016-08-20 18:07
ups, ja du hast recht, ich hab mich verrechnet. Muss nochmal neu überlegen
Dann erklär ich auch wie ich das im kopf gerechnet hab.
Parent - By Frank Brenner Date 2016-08-20 18:16
Also, eine bessere Möglichkeit ist

1,2,3,4,7,12,21,38,69,126,215, 361 mit summe  = 702

Hast du noch etwas besseres gefunden ?
Parent - - By Frank Brenner Date 2016-08-20 18:29
Die kleinste 3 elementige Menge ist

1,2,3    3er Summen: 6
            2er Summen: 3,4,5

Nächstes Element ergibt sich zu 6-3+1 = 4

1,2,3,4     Größte 3er Summe: 9
                 Kleinste 2er Summe: 3
                 ----> nächstes Element ist dann 9-3+1 = 7

1,2,3,4,7    Größte 3er Summe: 14
                  kleinste 2er Summe: 3   
                  ---> nächstes Element 14-3+1 = 12

1,2,3,4,7,12  größte 3er Summe:  23
                      kleinste 2er Summe: 3
                     ---> nächestes  Element 23-3+1 = 21

1,2,3,4,7,12,21          -> nächtest element (7+12+21)-3+1 = 38
1,2,3,4,7,12,21,38     -> nächstes element (12+21+38)-3+1 = 69
1,2,3,4,7,12,21,38,69      -> nächstes element (69+38+21)-3+1 = 126
1,2,3,4,7,12,21,38,69  ,126     -> nächstes element (126+69+38)-3+1 =   231
1,2,3,4,7,12,21,38,69  ,126,231      -> nächstes element (231+126+69)-3+1 =   424

-->
1,2,3,4,7,12,21,38,69  ,126,231 ,424

Mit einer etwas cleveren suche mit einem programm kann man eine noch dichtere aufsteigende Folge finden nämlich diese hier:

1,2,3,4,7,12,21,38,69,126,215,361
Parent - - By Ulf Flörsheimer Date 2016-08-20 19:53 Edited 2016-08-20 19:58
Hallo Frank,

vielen Dank für deine Arbeit, aber irgendwas kann meiner Meinung nach nicht stimmen. Das Problem fängt schon hier an: 1,2,3,4,7. Hier haben die Triple (1,4,7) und (2,3,7) beide die Summe 12. Das Problem pflanzt sich dann entsprechend fort. Ansonsten ist dein Ergebnis hinsichtlich der Größe schon sehr beachtlich!

Wie suchst du "clever" mit einem Programm? Wie reduzierst du die Werte? Einfach über ein paar for-Schleifen? Und jetzt eine ganz ernst gemeinte Frage (daher bitte nicht falsch verstehen): Wie schaffst du es, die Eindeutigkeit der Summen zu erkennen, ohne dass du dabei über deinen Basisfehler, der einzige Fehler in deiner Rechnung, der aber dauernd auftritt) stolperst? Wie schaffst du es, die Prüfungen zu reduzieren?

Ich bin so vorgegangen: Ich habe erst versucht eine Optimallösung für 5, 6 und 7 Elemente ganz brachial mit Programm zu finden. Dabei fiel mir etwas auf, was mir half, in der Folge die Suche zu verengen und dabei die Menge immer um ein Element zu vergrößern. Als mich dann das exponentielle Wachstum des Problems aufzufressen drohte, habe ich die ersten Werte fix gesetzt und somit die Schleifen reduziert (zumindest hoffe ich dadurch keinen großen Fehler zu begehen, zumal die Summen der ersten Terme aufgrund des Wachstums der Folge kaum ergebnisrelevant sind). Nachdem ich schließlich eine erste Lösung hatte, habe ich mir noch ein paar Gedanken über die "Kurvenform" der Menge gemacht, was mir half, das Ergebnis noch einmal zu verbessern. Ich bin derzeit unter 700.

Ich zeige gerne meine Lösungen, aber ich möchte dir noch die Chance geben, ein wenig selbst zu knobeln. Da du ein besserer Analytiker als ich zu sein scheinst, kommst du vielleicht schlussendlich auf bessere Lösungen als ich ... und ich würde gerne noch was lernen.

Gruß Ulf
Parent - - By Frank Brenner Date 2016-08-20 21:04
Hallo Ulf,

oh, danke. Den Fehler in meiner Folge habe ich gar nicht bemerkt. Das kommt wenn man es beim Programmieren zu eilig hat

Es ist eine Kombination aus brute Force und Greedy:

Die ersten k Werte (zb k = 2,3,4,5,6) werden Brute force ausgerechnet.
Das so entstandende Anfangssegment wird mit der "Greedy" methode fortgesetzt auf insgesamt 12 Elemente.

Angenommen die ersten n Werte sind per Brute Force mit anschließendem Greedy bereits vorgegeben und das Maximum dieser n Werte ist max  dann wird der n+1. Wert wie folgt berechnet:
Der n+1 Wert ist die kleinste Zahl größer als max mit der Eigenschaft, dass Deine Bedingung erfüllt ist.

Um nicht jedesmal  alle Tripel auf paarweise unterschiedliche Summen zu überprüfen schleppe ich während der Iteration über das n. Element jeweils zwei Mengen mit mir mit:
-  die Menge der 3 Elementigen  Summen
-  und die Menge der 2 Elementigen Summen

Diese Mengen sind rech klein, bei 12 Folgeglieder nur max. 220 bzw 66 Elemente.

Die Menge der 3 Elementigen Summen muss unique sein (ist ja klar, so war ja Deine Bedingung)
Die Menge der 2 Elementigen Summen muss nur bei der Iteration 1...11 unique sein. Nur Wenn das zwölfte Glied dazu kommt ist es erlaubt dass die Summen zweier unterschiedlichen Zahlen identisch ist.
Bei mir war vorhin der Fehler schon bei 1,2,3,4 gegeben, (noch ohne die 7). Diese Folge 1,2,3,4 erfüllt zwar Deine Bedingung aber kann nicht mehr Fortgesetzt werden, weil bereits 2+3 = 5 und 1+4 = 5. Egal welche fünfte Zahl ich dazu aufnehme, es würden dann stets zwei unterschiedliche Tripel die gleiche Summe aufweisen.

Die beste Folge die ich habe ist:

1,2,9,17,33,35,37,57,105,150,195,333   Summe: 678

Hast du noch eine kürzere gefunden ?

Grüße
Frank
Parent - By Frank Brenner Date 2016-08-20 21:25
Je länger das Programm läuft umso besser ist das Ergebnis. Bin jetzt auf eine Summe von 656 gekommen.
Parent - - By Ulf Flörsheimer Date 2016-08-21 00:21
Hallo Frank,

ich bin derzeit bei 669 ... wie ich weiter unten bzw. oben drüber gelesen habe, kann ich damit aber keinen Blumentopf mehr gewinnen   Meine beste Lösung ist (1, 2, 3, 5, 8, 14, 25, 47, 93, 163, 223, 283)
Parent - - By Frank Brenner Date 2016-08-21 01:08
Hallo Ulf,

Deine Lösung mit 669 ist mir entwischt, weil der Greedy Algorithmus anstelle der 47 die (gierig kleinere) Zahl 45 gefunden hat.

Auf 656 kommst du mit dieser Folge:

1,9,11,13,17,26,33,55,97,140,183,333   Summe 656
Parent - - By Ulf Flörsheimer Date 2016-08-22 09:37
Hallo Frank,

deine 656 hat mein Programm inzwischen auch gefunden, aber nichts besseres. Die einzige Menge, die diesem Ergebnis noch nahe kam ist die (2, 10, 12, 14, 18, 27, 34, 56,  98, 141, 184, 334) mit der Summe 659

Jetzt werde ich mein Glück mal mit 4-Tupel bei 12 Elementen probieren.
Parent - - By Wolfram Bernhardt Date 2016-08-22 17:36
Mein Programm rechnet noch. Lohnt sich das, oder haben Eure Programme sicher erschöpfend alles durchsucht?
Parent - - By Ulf Flörsheimer Date 2016-08-22 21:37
Hallo Wolfram,

ich finde, das lohnt insofern immer, weil es sehr befriedigend ist zu sehen, wie immer bessere Lösungen auf dem Bildschirm erscheinen. Mir ging es jedenfalls so, als mein Programm endlich auch die 656 ausspuckte und ich habe mich gefreut, dass ich mit 659 noch eine ähnlich gute Alternative gefunden hatte. Also lass dich nicht entmutigen!

Aber ehrlich: Es wird schwer sein, die 656 zu unterbieten (falls es überhaupt geht). Mein Programm arbeitet im Prinzip so wie Frank es oben beschrieben hat: von {1,2,3} ausgehend wird das erste widerspruchsfreie 4. Element angehängt. Ich versuche in der Folge dann aber auch noch die nächsten 4 möglichen 4. Elemente. Damit will ich vermeiden, dass der Algorithmus zu gierig ist und Variationsmöglichkeiten geschaffen werden. Dann verfahre ich ausgehend von der jeweils aktuellen 4-elementigen Menge analog mit dem 5. Element. Da ich an jeder Stelle also 5 Elemente probiere, macht das insgesamt 5^9, was rund 2 Millionen untersuchten Lösungen entspricht. Da ich aber auch noch andere Ausgangstripel untersucht habe, kommt noch etwa der Faktor 50 dazu. Damit habe ich einiges untersucht, aber von einer vollständigen Suche bin ich meilenweit entfernt. Insofern könnten sich noch etliche dicke Fische im Lösungsraum tummeln. Vielleicht hast du ja noch eine geniale Idee für eine Suchheuristik.

Solange du Spaß an einer Aufgabe hast, lass' ihn dir nicht nehmen. Du musst dir nur stets vergegenwärtigen: "Es gibt keinen Neuschnee" wie der Titel eines wunderbaren Essays von Kurt Tucholsky (http://www.textlog.de/tucholsky-neuschnee.html) heißt.

Ulf
Parent - By Wolfram Bernhardt Date 2016-08-23 18:21
Hi Ulf!

Also eine wirklich bessere Idee hatte ich bisher auch nicht, also habe ich statt dessen versucht, den Ansatz so effizient wie möglich zu implementieren.
Ich suche dabei auch nicht vollständig, sondern ausgehend vom besten Ergebnis der jeweils um eins kleineren Menge. Oder anders: Ich fange mit der Menge der Länge 3 an, suche hier vollständig zu Ende und nehme das beste Ergebnis als Startpunkt für Länge 4 usw.
Bis Länge 9 abgeschlossen ist, dauert es jetzt 30sek. Länge 10 dauerte etwa 1h., aber in der Tat fehlt da noch einiges bis Länge 12.

Aber ich bleibe erstmal noch dran. 

Viele Grüße,
     Wolfram
Parent - - By Wolfram Bernhardt Date 2016-08-23 21:31 Upvotes 1
Könnt Ihr bitte kurz den überprüfen:

{1,7,11,13,15,26,29,51,91,136,181,333} =>  650.

Nach meiner letzten Falschmeldung bin ich leicht verunsichert

Danke und viele Grüße,
     Wolfram
Parent - - By Ulf Flörsheimer Date 2016-08-23 21:45 Upvotes 2
Korrekt! Herzlichen Glückwunsch!!! 650 ist das neue Jagdziel!
Parent - By Wolfram Bernhardt Date 2016-08-23 21:57
Weidmannsdank!
Parent - - By Ingo Althöfer Date 2016-08-23 21:58
Echt spannend - und Glückwunsch zum Treffer!

Wolfram Bernhardt schrieb:

{1,7,11,13,15,26,29,51,91,136,181,333} =>  650.

Nur mal zur Einordnung:
Es gibt (12 über 3) = 12*11*10/(3*2*1) = 220 Tripel aus 12 verschiedenen Zahlen.

Jede der zugehörigen Dreiersummen ist verschieden. Also hat man im überstrichenen
Intervall {19, ..., 650} mit seinen 631 Elementen eine "3er-Dichte" von besser als
1/3. Das ist schon was.

Ich finde das besonders spannend vor dem Hintergrund des verallgemeinerten
Geburtstags-Paradoxons:  Bei zufällig gewählten 12 Zahlen aus {1, 2, ...,333}
ist die Wahrscheinlichkeit sehr nah bei 1, dass mindestens zwei gleiche Dreiersummen
vorliegen.

Ingo.
Parent - - By Wolfram Bernhardt Date 2016-08-23 22:18
Hallo Ingo!

Das ist wirklich interessant. Da macht man sich gar keine großen Gedanken drüber, wenn man überlegt, wie man seinen Code tritt, damit er schneller wird.

Vom Gefühl her ist das auch noch nicht die endgültige Lösung (aber vielleicht die letzte, die ich finde, obwohl nicht noch weitermachen werde). Dann wird die Dreierdichte noch dichter...

Viele Grüße,
     Wolfram
Parent - By Frank Brenner Date 2016-08-23 23:58 Edited 2016-08-24 00:06
Danke dass du uns mithilfst bei der Suche, sonst wären wir bei 656 stehen geblieben.
Parent - - By Ingo Althöfer Date 2016-08-24 09:50
Hallo Wolfram,

Wolfram Bernhardt schrieb:
... Da macht man sich gar keine großen Gedanken drüber,
wenn man überlegt, wie man seinen Code tritt, damit er schneller wird.

lass mich eine Geschichte von 1996 erzählen. Damals
stand für die Jenaer Mathematiker ein grosser Umzug an:
raus aus dem Uniturm (heisst jetzt Intershop-Tower), rein in
das renovierte alte Zeisswerk.

Der Kanzler der Uni hatte verfügt, dass sich jeder Mitarbeiter neues
Mobiliar zulegen durfte; aus einer Liste mit gut 30 Posten.
Wichtig: Gesammtsumme des Mitarbeites durfte nicht größer sein
als 2.500,00 DM.
Die Preise in der Liste waren krumme Werte, z.B. 93,16 DM für einen
Stuhl usw.

In meiner damaligen Vorlesung sass ein Informatik-Doktorand, der auch
eine Mitarbeiterstelle hatte. Aus Interesse wollte er wissen, ob man den
Wert 2500,00 exakt erreichen konnte. Ich sei doch der Optimierer, was ich
dächte.

Naja, in der nächsten Übserie fand sich die Frage als Aufgabe wieder.
(Das Mobiliar sollte nicht nach Sinn zusammengestellt werden, sondern
nur nach dem Kriterium, dass die 2500,00 DM von unten möglichst nah
approximiert würden.)

Für uns alle die Überraschung: 2500,00 liess sich exakt erreichen, und
zwar auf etliche verschiedene Weisen (in einer Lösung gehörten 13 Mantelständer
zum Bestellumfang). Das war damals der Anfang meiner Beschäftigung mit
verallgemeinerten Geburtstags-Paradoxa.

****************************************************
Beim Schreiben kam mir gerade eine neue Idee:
Zu einer Zahlenmenge S={s1, s2, ..., s12} mit s1 < s2 < ... . < s12
erklärt man die Dichte wie folgt: Man ermittelt, wieviele Zahlen aus
dem Interval {s1+s2+s3, ..., s10+s11+s12} als Dreiersummen darstellbar
sind. Seien das k viele verschiedene.
Der Quotient
k / (s10+s11+s12 - (s1+s2+s3-1))
ist die erreichte Dichte.
FRAGE 1: Welche Menge S hat die größtmögliche Dichte?
FRAGE 2: Kann man beweisen, dass es nicht nur ein Supremum,
sondern wirklich ein Maximum gibt?

Natürlich könnte/sollte man die Fragen zuerst für Paare statt Tripel betrachten.

Ingo.
Parent - By Wolfram Bernhardt Date 2016-08-24 17:09
Hi Ingo!

Ach... das erstaunt mich auch. Was habt Ihr dann mit den 13 Mantelständern gemacht?
(Das erinnert mich an den Klassiker Otto... "Und was machen wir jetzt mit den 28 Torten?")

Da fällt mir gerade ein, dass ich im zarten Alter von 14 etwas ähnliches gemacht habe - als es noch kein Internet gab, aber teure, kleine Festplatten und billige FloppyDisks.
Aber Sammlung von Dateien (z.B. Fotos, mp3s gab auch noch nicht). Und oft hatte man ein paar tausend Bilder und wollte diese auf Floppy Disks kopieren, die auch nur wenig Speicher hatten. Meistens kopierte man in alphabetischer Reihenfolge. Und dann blieb auf jeder Floppy Disk ungenutzter Speicher, was dazu führte, dass man mehr Disks brauchte als man gedacht hatte.
Damals hatte ich ein Kopierprogramm geschrieben, dass Dateien so kopierte, dass eine Diskette wirklich voll wurde (0 bytes free) und nach dem Kopieren gleich löschte, damit man sie nicht nochmal kopierte.

Das war sehr praktisch. Jahre später ist mir aufgefallen, dass das aber mathematisch keine große Tat war. Man nimmt einfach immer die größtmögliche Datei, die noch auf die Diskette passt. Damit macht man nie etwas falsch und verbraucht nie mehr Disketten als nötig.
Meistens waren auch so viele kleine Dateien dabei, dass man prima immer komplett auffüllen konnte.

Überhaupt waren das himmlische Zeiten vor dem Internet. Ich war soooo stolz, als ich mir am Wannesee liegend einen Suchalgorithmus für 4Gewinnt ausgedacht hatte (Zivildienstzeit in Berlin). Und dann kam das Internet und ich erfuhr irgendwann, dass das alpha-beta-Suche heisst und dass ein gewisser Herr Shannon und ein noch gewisserer Herr Turing da noch ein paar Jahrzehnte früher dran waren.

Das Internet macht einen bescheiden.

Viele Grüße,
     Wolfram
Parent - By Frank Brenner Date 2016-08-23 22:36
Herzlichen Glückwunsch!

Wow! Ich werde dann doch noch mal etwas weitersuchen
Parent - - By Ulf Flörsheimer Date 2016-08-24 12:13
Ich mutiere langsam zum "Meister der zweitbesten Lösungen" , denn inzwischen habe ich das hier gefunden:

{2, 8, 12, 14, 16, 27, 30, 52, 92, 137, 182, 334}  ==> Summe 653
Parent - - By Wolfram Bernhardt Date 2016-08-24 12:32 Edited 2016-08-24 12:45
Hi!

Jo!
Das ist die 650er-Lösung mit jedem Element um 1 erhöht.

Denn folgendes war mir gestern aufgefallen: Da es nur um Summen geht, kann man jede Lösung "nach oben" erweitert, indem man in einer Lösung jedes Element um dieselbe Zahl erhöht.

Das heisst natürlich auch, dass das mit Abziehen ebenso funktioniert, was uns dazu bringt, dass die beste Lösung mit Sicherheit mit 1 beginnt.

Insofern haben wir das Problem auf eine Menge von 11 zu findenden Elementen reduziert. Und das gilt dann auch für jede Mengengröße, auch für die kleineren.
Ist ja auch schon ein Ergebnis. (Eigentlich klar, aber zumindest mir ist das gestern erst aufgefallen.)

Viele Grüße,
      Wolfram
Parent - - By Ulf Flörsheimer Date 2016-08-24 13:56
Oops! Eigentlich ja auch ganz logisch! Hätte mir eigentlich selbst auffallen können, das ein konstantes additives Glied n zu einer Ergebnisverschlechterung von 3n führt. Das hat man davon, wenn man nur aufs Programmieren fixiert ist, statt über ein Problem nachzudenken. Wenn man zudem nur auf das Ergebnis schaut anstatt auf die Strukturen, dann geht es einem genau so, wie es mir gerade gegangen ist.

Danke für die Aufklärung!
Parent - - By Wolfram Bernhardt Date 2016-08-24 16:49
Ging mir ja auch so
Finde ich aber auch nicht schlimm. Wir haben unsere Art uns Problemen zu nähern.
Natürlich denken wir schon auch erstmal über das Problem an sich nach. Dann legen wir schnell mit dem Implementieren los und stossen dabei dann sehr bald auf die eigentliche Knackpunkt.
Letztlich ist es ja immer die kombinatorische Explosion. Und wir können Ideen, wie man diese bei dem speziellen Problem eingrenzen kann, direkt ausprobieren und sehen unmittelbar die Wirkung. Das finde ich ein völlig legitimes Vorgehen.

Auf der anderen Seite bewundere ich eine mathematischere Herangehensweise auch jedesmal aufs Neue. Manchmal kommen da so wunderbare, einfache, elegante Lösungen bei raus, bei denen ich mich - sofern ich sie verstehe - immer wieder staunend frage, wie jemand auf so tolle Ideen kommt. Aber die können das irgendwie.

Würde mich bei diesem Problem auch nicht wundern, wenn jemand sagt "455 ist die optimale Lösung und das kann ich wie folgt beweisen."

Apropos: In Deinem Buch, aus dem das kommt - sind wohl keine Lösungen angegeben, oder?

Viele Grüße,
      Wolfram
Parent - By Ulf Flörsheimer Date 2016-08-24 17:16
Mit den Lösungen in dem Buch ist das so 'ne Sache. D.E. Shasha hat viele der Aufgaben ursprünglich in Dr. Dobbs Journal, eine Publikation für Programmierer und Tüftler, veröffentlicht. Etliche Lösungsansätze (von Lesern?) wurden dann in der Omniheurist Puzzle Cloumn veröffentlicht. Manche dieser Lösungen sind offenbar sehr gut bzw. optimal und manche eben absolut nicht (der Leser soll ja zum Nachdenken und selbermachen angeregt werden). In diesem Fall hatte die abgedruckte Leserlösung eine Summe von 1023. Frank Brenner hat hier ja sehr gut beschrieben, wie man mit ein wenig Mühe zumnindest bis auf die letzten drei Zahlen schon mit der Hand auf bessere Lösungen kommt.

Wer interessante Aufgabe präsentiert in machmal recht bizarren Geschichten mag, dem kann ich die Dr. Ecco Bücher von Dennis E. Shasha sehr empfehlen.
Parent - - By Frank Brenner Date 2016-08-24 12:51 Upvotes 2
Hallo Ulf,

Bei der ersten Zahl brauchst du eigentlich nur die "1" zu berücksichtigen.

Schau dir einmal Wolfram Bernhardts Lösung an: {1,7,11,13,15,26,29,51,91,136,181,333} =>  650

Diese Lösungen ist bis auf eine additive Konstante  +1 identisch zu deiner.

Deswegen erzielt deine Folge auch die gleiche "Dichte" nach Hern Althöfers Definition:220/( 650-(1+7+11) )  = 220/631   wie die von Wolfram Bernhardt.

Ich hab gestern abend mein Programm neu programmiert und über nacht  alle 12-Tupel die mit 1 anfangen berechnet (mit einigen Contraints:  zb darf die vorletzte Zahl nicht  größer als 250 sein, die drittletzte nicht größer als 207 und die viertletzte nicht größer als 138) . Wolfram Bernhardts Folge ist hierbei tatsächlich die einzige und beste Folge und die Dichte mit   220/631 ist maximal.

Auch im allgemeinen Fall, also wenn die Länge nicht 12 ist sondern eine beliebige natürliche Zahl ist die beste Dichte immer auch ein Maximalwert der auch tatsächlich erzielt werden kann, denn wenn einmal eine Dichte gefunden wurde  - zb 220/631 - dann gibt es nur endlich viele größere Dichten: der Zähler ist nach oben beschränkt durch (n über 3) und der Nenner kann nur endlich viele kleinere natürliche Zahlen als Werte annehmen.

Daher kann es also keine unendlich Sequenz an Folgen mit einer dazugehörender Sequenz an Dichten geben die gegen ein Supremum konvergieren aber dieses nie erreichen.

Grüße
Frank
Parent - - By Wolfram Bernhardt Date 2016-08-24 18:22
Hi!

Wie? Was? Du hast ALLE 12-Tupel berechnet, die mit 1 anfangen?
Wow!

Aber dann sind wir doch fertig, oder?

Und wenn Du dabei nichts Neues gefunden hast, haben wir mit 650 auch die optimale Lösung.

Wie hast Du das denn gemacht? Mein Programm würde noch ne Weile rechnen.
Entweder Du hast noch ziemliche gute Constraints gefunden oder Dein Implementierung ist noch viel schneller.
Ich habs in .Net/C# gemacht, was für solche Aufgaben natürlich nicht ideal ist. Aber immer sehr angenehm zu programmieren.
In C(++) oder so Assembler ist man noch ein paar Faktoren schneller, wenn man "nur" Zahlen hin- und herschiebt wie wir hier.

Viele Grüße,
     Wolfram
Parent - - By Frank Brenner Date 2016-08-24 23:24
Hallo Wolfram,

Meine Suche ist nicht 100% vollständig:

Der erste Wert ist fix auf "1".

Der Algorithmus für die restlichen 11 Stellen  funktioniert so:

Die gesamte Suche erfolgt zunächst einmal  mit dem Greedy Algorithmus.
D.h.  es  wird für die nächste Stelle die kleinste konsistente Zahl gefunden.
Eine Zahl ist konsistent wenn alle bisherigen (inklusive der neuen Zahl)  entstandenen Trippel paarweise verschieden und bis zur vorletzten Stelle auch die 2-Tupel paarweise verschieden sind.

Dieser Greedy Algorithmus ist sehr schnell und kann auch auf einem Blatt Papier gerechnet werden - findet aber bei weitem nicht die beste Lösung.

Also wurde der  Greedy algorithmus zum Brute-Force-Greedy abgeändert indem auch noch die k weiteren nächst größeren Elemente je Stufe in Betracht gezogen wurden.

Darüber hinaus wird die Suche abgebrochen wenn bestimmte Stellen bereits zu groß geworden sind. (Constraints)

Die Constraints habe ich gefühlt großzügig vergeben, weil ich mir nicht vorstellen kann , dass  zB die drittletze Zahl  in der besten Folge größer als 207  ist.

Ausgegeben werden alle Folgen die besser sind als 680

Mit k=12 wurden nicht alle solche Folgen gefunden.
mit k=15 kamen noch welche dazu.
Mit k=17 kamen keine mehr dazu, mit 20 auch nicht und mit k=22 habe ich es dann die Nacht durchlaufen lassen.

Programmiersprache ist C/C++ mit dem GCC 64 Bit Compiler, ohne assembler.

Grüße
Frank
Parent - - By Wolfram Bernhardt Date 2016-08-25 07:41
Hi!

Mein Algorithmus funktioniert im Grunde so ziemlich (wenn nicht exakt) genauso .
Allerdings erkenne ich hier nicht so richtig den Unterschied zwischen Brute Force und Greedy.

Sagen wir, wir sind am Start und haben bisher die LIst {1,2,3}.
Jetzt wird nächste konsistene Zahl gefunden (4) und der Liste hinzugefügt. Dann wird rekursiv vertieft.
Wenn auf einer Stufe alle möglichen Zahlen (dazu gleich mehr) geprüft sind, wird ge-backtrack-t. Also in die nächste höhere Stufe zurückgegangen, dort die nächste Zahl gesucht und wieder vertieft.

Und wenigstens etwas rauszuholen, habe ich folgende Constraints
- jede Zahl muss natürlich größer sein als die vorherig in der Liste.
- neue Zahlen dürfen die 2er- und die 3er-Summen nicht erhöhen.
- Das aktuell beste Lösung wird berücksichtigt. Sagen wir, diese ist in einem Moment 900. Nun wird die Suche auf einer Stufe abgebrochen, wenn absehbar ist, dass diese 900 nicht mehr unterschritten werden kann. Wenn also als 10. Zahlen eine 299 geprüft wird, ist klar, dass die nächsten Zahlen für Position 11 und 12 im besten Fall 300 und 301 sein können und damit wäre dioe 900 gerissen. Das mache ich konsequent auf jeden Stufe. Also Stufe 9 würde bei 298 abgebrochen, Stufe 8 bei 297 usw. Da wird natürlich immer auf die letzten 3 Position geschaut. Auf diese Weise habe ich eine natürliche Schranke nach oben für jede Stufe. Sobald eine neue Best-Lösung gefunden wird, wird natürlich fortan gegen diese gecheckt.

Tja, das ist eigentlich alles. Und das dann so effizient implementiert wioe ich es in hinbekommen habe. Der Code hat mit gutem C# nun allerdings nichts, aber auch gar nichts mehr zu tun

Viele Grüße,
     Wolfram
Parent - - By Frank Brenner Date 2016-08-25 11:08
Ich glaube du brichst die Suche am Ende zu selten ab:

Die Suche bricht bei mir ab wenn das  11. (vorletze) Element größer als 247 ist, oder das 10. (drittletzte) Element größer 189  ist, oder wenn das 9. (viertletzte) Element größer als 127 oder wenn das 8. (fünftletzte) Element größer als 77 ist.

Wenn du der Meinung bist, dass ich zu früh abbreche mit den Werten 247, 189,127 bzw 77 dann müsstest du mir wenigstens ein Beispiel nennen wo die Gesamtsumme der höchsten drei Werte kleiner ist  als 680 ist, aber der entsprechende Wert noch größer als bei mir das Abbruchkriterium ist, was durchaus der Fall sein könnte - dann hätte ich zu früh abgebrochen.

Ups ich sehe gerade, dass sich die etwas größeren Abbruchkriterien die ich 2 Postings  davor genannt habe auf eine Listenlänge von 13 beziehen.
Parent - By Ulf Flörsheimer Date 2016-08-25 12:16
Ja, über deine gar zu strikten Abbruchkriterien hatte ich mich auch gewundert; aber gegen die hier genannten ist nichts zu sagen. Aus der Kenntnis der wirklich guten Lösungen könnte man sie noch restriktiver fassen.

Auf jeden Fall finde ich es erstaunlich, dass zum Schluss ein Programm übrig bleibt, das - je nachdem, wie man nun exakt die Grenzen setzt - zwischen fünf Minuten und einer halben Stunde rechnet. Das hätte ich nie erwartet. Und auch das Ergebnis von 650 ist schlussendlich unerwartet gut.

Das Ganze hat echt Spaß gemacht! Vielen Dank für euer Interesse und euren Programmiereinsatz. Ich selbst habe mit Free Pascal 3.0 gearbeitet. Ich würde mich freuen, wenn wir das gelegentlich mit einer anderen Herausforderung wiederholen könnten.

Liebe Grüße
Ulf
Parent - - By Wolfram Bernhardt Date 2016-08-25 12:28
Hi!

Frank Brenner schrieb:

Die Suche bricht bei mir ab wenn das  11. (vorletze) Element größer als 247 ist, oder das 10. (drittletzte) Element größer 189  ist, oder wenn das 9. (viertletzte) Element größer als 127 oder wenn das 8. (fünftletzte) Element größer als 77 ist.

Wenn du der Meinung bist, dass ich zu früh abbreche mit den Werten 247, 189,127 bzw 77 dann müsstest du mir wenigstens ein Beispiel nennen wo die Gesamtsumme der höchsten drei Werte kleiner ist  als 680 ist, aber der entsprechende Wert noch größer als bei mir das Abbruchkriterium ist, was durchaus der Fall sein könnte - dann hätte ich zu früh abgebrochen.

Ups ich sehe gerade, dass sich die etwas größeren Abbruchkriterien die ich 2 Postings  davor genannt habe auf eine Listenlänge von 13 beziehen.


Das ist interssant, insbesondere da ich das so noch nicht verstehe.
Feste Abbuchkriterien scheinen mir nicht sinnvoll, diese sollten ja im Zusammenhang mit dem aktuell besten gefundenen Ergebnis stehen. Ich vermute, das meinst Du hier auch und gehst von 650 aus.

Wieso kann man dann abbrechen, wenn das drittletzte Element größer 189 ist? Als die drei letzten Elemente (also 10, 11 und 12) kommen doch 190, 191 und 192 in Frage, die zusammen nur 573 ergeben. Also wieso soll man die nicht prüfen müssen?

Dieselbe Frage für das viertletzte, wenn es größer 127 ist. Wieso kommen als die 4 letzten Elemente nicht 128,129,130,131 in Frage? (Summe der letzten drei nur 390).

Es geht ja nur um die Summe der größten drei. Insofern erscheint es mir in der Tat so, als würdest Du zu früh abbrechen.

Oder ich übersehe etwas Entscheidendes, aber das kriegen wir noch raus.

Viele Grüße,
     Wolfram
Parent - - By Frank Brenner Date 2016-08-25 12:58 Edited 2016-08-25 13:02

> Ich vermute, das meinst Du hier auch und gehst von 650 aus.


Nicht wirklich.

Bei frühzeitigen  Abbruchkriterien handelt man sich theoretisch mögliche Fehler ein. Man führt sie aber trotzdem durch damit der Algorithmus in absehbarer Zeit auch einmal terminiert.
Um dabei noch zu einem gefühlt sehr verlässlichen Ergebnis zu kommen muss man sich viel Mühe geben und viel Zeit aufwenden bei der optimierung der Abbruchkriterien, denn sonst könnte eine noch bessere Lösung übersehen werden.

Während der Suche habe ich alle Reihen ausgegeben die besser sind als 680, also auch solche Reihen die um 30 Punkte von der besten bisher gefundenen Lösung abweicht.
Dies habe ich nur deswegen  gemacht um die Abbruchkriterien und das k zu optimieren. Wird zu Häufig abgebrochen  oder ist das k zu klein, so werden auch Folgen im Bereich 650...679 übersehen, was dazu führen kann dass die Möglichkeit besteht dass noch sogar noch bessere Lösungen als 650 übersehen werden könnten.
Im Anschluß daran habe ich trotzdem noch auf die gefundenen Abbruchkriterien und auf das k noch bequeme Werte addiert um gefühlt noch sicherer zu sein, dass auch eine relativ exotische beste Reihe gefunden werden kann
(obwohl bei  allen gefundenen Reihen  unter 680 keine solche exotische suboptimale Lösung dabei war,  also selbst dann nicht als ich noch Schleifen hatte die bis 550 gingen in jedem Tupel)

>Dieselbe Frage für das viertletzte, wenn es größer 127 ist. Wieso kommen als die 4 letzten Elemente nicht 128,129,130,131 in Frage? (Summe der letzten drei nur 390).


Bitte nenne mir eine Folge deren Summe (die 3 größten)  kleiner ist als 680 bei der das viertletzte größer ist als 127 , oder zumindestens größer als 120.

Wenn du so eine Folge findest, wäre das ein gutes Indiz dafür dass meine Abbruchkriterien nicht optimal sind .
Parent - - By Wolfram Bernhardt Date 2016-08-25 15:48
Ah. Okay. Du suchst nicht vollständig. Das erklärt natürlich alles.
Ich hatte einfach angenommen, dass Du bei der Neuimplementierung auf "erschöpft" übergegangen wärst.

Gut, das ist einfach der wesentliche Unterschied.
Mein Ansatz sucht erschöpfend ist darum breche ich nur Stellen ab, bei denen ganz sicher nichts mehr gefunden werden kann.

Eine Folge, bei der die viertletzte größer als 127 und das Gesamtergebnis <680 ist, habe ich natürlich nicht parat.
Aus meiner "erschöpfenden Sicht" würde ich aber nicht sagen, dass das bedeutet, dass es keine gibt. Oder anders: Das wäre mir zu "schwach". Um dort abzubrechen und sicher zu sein, dass mir nichts entgeht, bräuchte ich eine stichfestere Erklärung.

Das Spannende an der Aufgabe ist ja auch, dass wir letztlich wenig echte Gesetzmäßigkeiten gefunden haben.

Viele Grüße,
     Wolfram
Parent - - By Ingo Althöfer Date 2016-08-25 17:14
Hallo Wolfram, hallo Leute,

Wolfram Bernhardt schrieb:
Das Spannende an der Aufgabe ist ja auch, dass wir letztlich
wenig echte Gesetzmäßigkeiten gefunden haben.


ich will jetzt keine neue Rechenlawine lostreten. Aber ein kanonischer Weg,
mehr Gesetzmässigkeiten zu finden, besteht darin, dass Tripelproblem nicht
nur für k=12 Summanden zu lösen, sondern auch für k=11, 10, 9, ...
um dann die besten Lösungen der verschiedenen k miteinander zu vergleichen.

Ingo.
Parent - - By Wolfram Bernhardt Date 2016-08-25 19:11 Upvotes 1
Hallo Ingo!

Die Ergebnisse haben die ja quasi nebenbei mit aufgesammelt:

k=03 : 1 2 3  = 6
k=04 : 1 2 3 4  = 9
k=05 : 1 2 3 5 8  = 16
k=06 : 1 2 3 5 8 14  = 27
k=07 : 1 2 3 5 8 14 25  = 47
k=08 : 1 2 3 5 8 14 25 45  = 84
k=09 : 1 4 6 7 8 15 26 45 80  = 151
k=10 : 1 4 6 7 8 15 26 45 80 134  = 259
k=11 : 1 7 11 13 15 26 29 51 91 136 181 = 408
k=12 : 1 7 11 13 15 26 29 51 91 136 181 333 = 650 (bisher)

Viele Grüße,
    Wolfram
Parent - - By Ingo Althöfer Date 2016-08-25 19:57
So, und jetzt wird es spannend.
Ich strukturiere mal die Lösungsfolge durch Freizeilen.

Wolfram Bernhardt schrieb:

k=03 : 1 2 3  = 6
k=04 : 1 2 3 4  = 9

k=05 : 1 2 3 5 8  = 16
k=06 : 1 2 3 5 8 14  = 27

k=07 : 1 2 3 5 8 14 25  = 47
k=08 : 1 2 3 5 8 14 25 45  = 84

k=09 : 1 4 6 7 8 15 26 45 80  = 151
k=10 : 1 4 6 7 8 15 26 45 80 134  = 259

k=11 : 1 7 11 13 15 26 29 51 91 136 181 = 408
k=12 : 1 7 11 13 15 26 29 51 91 136 181 333 = 650 (bisher)


und vermute ganz dreist: Für viele Parameter k gibt es eine optimale
2k-Lösung, die als Startstück eine optimale (2k-1)-Lösung enthält.

****************************************
Wahrscheinlich ist es zu hart, für das Dreier-Problem die Grössen 13 und 14
"durchzuchecken". Aber man könnte ja für das einfachere Problem mit Zweier-
Gruppen testen, ob dort ähnliche Strukturen sind.

Ingo.
Parent - - By Frank Brenner Date 2016-08-25 20:05
für k =13 habe ich schon die bisher beste Folge ausgerechnet.
Hier habe ich allerdings 2 Lösungen gefunden:

1,5,9,17,19,29,36,53,99,169,226,321, 416   => Summe 963   =>  Dichte = 286  /  (963-1-5-9)
1,15,17,19,23,24,29,57,97,169,222,321,420 => Summe 963  =>  Dichte  =  286 / (963-15-17-19)    

Nachdem ich diese beiden Folgen hatte fiel mir ein, dass wenn wir die Dichte maximieren wollen die zweite Folge die bessere Wahl ist und dass ich am besten von vorneherein  versucht hätte  die 3 maximalen MINUS die 3 minimalen zu minimieren.

Nun muss ich wohl nachher einen neuen Suchlauf starten
Parent - - By Frank Brenner Date 2016-08-26 01:50 Upvotes 2
Alle Werte von Wolfram Bernhardt kann ich als beste Summen der drei höchsten Werte bestätigen.

Um die Dichte zu berechnen (die es zu maximieren gilt) benötigen wie die Differenz  der Summe drei größten und der Summe der 3 kleinsten. (die es zu minimieren gilt).

für k=10 gibt es noch eine Folge mit einer gleich großen Differenz:   1, 23, 30, 39, 43, 45, 47, 55, 102, 145  =>   (55+102+145)-(1+23+30) = 248
Wolfram Berhnhards Folge  hat die gleiche Differenz:                        1,  4,   6,  7,   8,   15, 26, 45, 80,   134  =>  259-11 = 248

für k=9 gibt es noch 2 Folgen mit einer kleineren Differenz:
1,12,20,24,25,26,28,55,89   (28+55+89)-(1+12+20) = 139
1,13,20,24,26,28,55,90        (28+55+90)-(1+13+20) = 139

für k= 8 gibt es 8 Folgen mit  noch kleinerer Differenz
1,7,10,11,13,15,29,48 -> (15+29+48)- (1+7+10) = 74
1,8, 9,10,12,15,29,48 -> 74
1,12,20,22,23,24,28,55 -> 74
1,15,18,20,21,22,29,57 -> 74
1,20,34,36,38,39,42,48 -> 74
1,20,34,37,39,40,41,48-> 74
1,28,32,33,34,36,44,55 -> 74
1,29,36,37,38,40,43,57 -> 74

für k=7 gibt es auch sechs Folgen die eine noch kleinerer Dichte haben

1  4  6  7  8  15  26   Dichte: 38
1  7  11  12  13  15  29  
1  8  9  10  12  15  29 
1  12  19  20  21  23  26
1  15  17  18  19  23  29 
1  15  18  20  21  22  29

k=6 hat folgende Folge eine kleinere Differenz
1,8,9,10,12,15   => (15+12+10)- (1+8+9)

k=5, hier gibt einige mehr mit gleicher Differenz

1 5 6 7 9
1 4 6 7 8
1 3 4 5 9
Parent - By Frank Brenner Date 2016-08-26 16:19
Der neue Durchlauf für  Folgenlänge=13 ist auch schon durch mit einer neuen besten Folge, wo die dichte größer geworden ist. Die Summe der drei größten ist dagegen größer geworden:

1,23,31,34,41,43,45,59,117,180,237,326,415 ->  (237+326+415) - (1+23+31) = 978 - 55 = 923

Es gibt nur diese eine Folge mit größter Dichte  und die folgende (auch einzige) zweitbeste Folge, die aber die kleinste (beste) Summe der drei größten besitzt:

1,15,17,19,23,24,29,57,97,169,222,321,420 -> (222+321+420)-(1+15+17) =  963 - 33 =  930

Die zweitbeste Folge hat die geringste Summe der größten drei:  963
Parent - - By Wolfram Bernhardt Date 2020-10-20 14:28
Hallo allerseits, besonders an diejenigen, die sich vor 4 Jahren so intensiv mit diesem Rätsel beschäftigt haben!

Ich hatte eine Woche Urlaub und in einem Anflug von Nostalgie habe ich das Rätsel nochmal rausgeholt, weil ich im Hinterkopf hatte, dass wir alle nicht sicher waren (sein konnten), ob wir es vollständig gelöst hatten.

Darum habe ich mir meinen Code von damals noch einmal angeschaut und mir sind noch eklatante Verbesserungen ins Auge gesprungen, die nochmal ca. Faktor 100 gebracht haben.

Dann habe ich den Code noch parallelisiert.

Und als ich wieder zuhause war, konnte ich meinen Desktop-Rechner drauf ansetzen, der natürlich auch deutlich mehr Dampf hat als alles, was ich vor 4 Jahren hier so rumstehen hatte. Er hat Tiefe 12 vollständig durchsucht - in weniger als 24h.

Leicht enttäuschend ist, dass wir damals die beste Lösung gefunden hatten. Besser als 650 geht es nicht bei einer Menge mit 12 Elementen.

Insofern kann ich leider jetzt gar nichts spektakuläres Neues präsentieren (ein wenig hatte ich es natürlich gehofft ), aber zumindest können wir jetzt ganz sicher sein.

Viele Grüße
     Wolfram
Parent - - By Ulf Flörsheimer Date 2020-10-31 11:02
Vielen Dank für die Info. Auch ich hatte vor längerer Zeit noch mal an dem Problem rumgebastelt und nie etwas besseres als die besagten 650 gefunden. Ich freue mich, dass du dir so viel Mühe gemacht hast, um dieses Ergebnis zu bestätigen. Bleibt vielleicht noch eine Frage: Ist dein Programm geeignet, um nach Lösungen mit mehr als 12 Basiszahlen zu rechnen. Ich wäre echt neugierig, was für 13, 14 und 15 rauskommt?  Ich muss mal rumsuchen: an der 13 hatte ich mich mal versucht, finde aber so spontan nichts mehr, an größeren Basismengen bin ich seinerzeit rechenzeitbedingt gescheitert.
Parent - - By Wolfram Bernhardt Date 2020-10-31 13:09 Edited 2020-10-31 13:23
Hi Ulf!

Ja, geeignet ist das Programm auf jeden Fall, um auch nach längeren Folgen zu suchen und würde auch gute Ergebnisse finden.

Um aber zB 13 komplett durchzurechnen, bräuchte man schon wieder ziemlich viel Zeit oder entsprechend viele Rechenkerne. Mein Desktop-Rechner hat 16 Threads, was die Geschwindigkeit in etwa ver-16-facht hat im Vergleich zu vorher. Mit 64 Threads wäre man also noch 4mal schneller (wenn die Taktfrequenz gleich ist).

Ich weiss, ob hier jemand mitliesst, der einen aktuellen Threadripper zuhause stehen und Interesse hat, das mal laufen zu lasen

Wenn die Sache einen irgendwie gearteten Nutzen hätte, könnte man überlegen, ob man das mal in eine Cloud (Azure oder Amazon) wirft - dort kann man ja Rechenpower kaufen. Länge 13 wäre damit noch gut, fix und bezahlbar durchzurechnen, vermute ich. 14 technisch auch noch gut machen, wäre aber schon teuer. Und ich glaube, bei 15 wäre Schluß.

Es kommt ja immer eine Zahl dazu und die liegt beim Sprung von 12 auf 13 wohl zwischen 300 und 400. Man kann also sagen, der Aufwand von 12 auf 13 ist ganz ganz grob 350x so groß. Von 13 auf 14 noch etwas größer, vielleicht bei 400x. Also kostet der Sprung von 12 auf 14 schon etwa 160.000 mal mehr Rechenleistung. (Zahlen ohne Gewähr, sind jetzt so aus dem Ärmel geschüttelt, müsste ich nochmal genauer gucken).

Viele Grüße
    Wolfram
Parent - - By Ulf Flörsheimer Date 2020-11-01 11:57
Hi Wolfram,

vielleicht kann ich ja deinem Jagdfieber etwas auf die Sprünge helfen: Mit einem läppischen, 45 zeiligen Python-Programm habe ich für k=13 folgende Lösung gefunden:

k=13 : 1 5 9 17 19 29 36 53 99 169 226 321 416 = 963

An k=14 versuche ich mich gerade ...

Schönen Sonntag
Ulf
Parent - - By Wolfram Bernhardt Date 2020-11-02 18:36
Ich werfe 13 gleich mal an, mal sehen, wie gut das vorankommt.

Du hast bei Deiner 963 für 13 offenbar "vorne" angefangen zu suchen, oder? Hattest Du mal versucht, die 650er-Lösung als "Startpunkt" zu nehmen. Damit hatten wir ja damals recht gute Erfolge gehabt.
Parent - - By Ulf Flörsheimer Date 2020-11-03 22:49
Hi Wolfram,

nein, ich habe in der Tat immer "von vorne" gesucht, mit relativ engen Restriktionen. Ansonsten habe ich noch:

k=14 : 1 5 9 17 18 19 29 53 101 171 248 325 440 632 = 1397
k=15 : 1 5 7 9 17 29 30 53 99 193 248 357 466 647 937 = 2050
k=16 : 1 2 3 5 9 16 29 53 103 193 262 381 511 711 1006 1301 = 3018

Aber da findest du oder finden andere sicher Besseres.

Grüße, Ulf
Up Topic Hauptforen / CSS-Forum / ... und Spiele: Mengen und Teilmengen
1 2 Previous Next  

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill