![]() |
---|
Hallo, ich beschäftige mich zur Zeit mit der Frage, welche Zahlen - gegeben relativ prime Zahlen und - als Linearkombination dieser Erzeugenden darstellbar sind. Sei die Schranke, ab der alle Zahlen als Linearkombination von und mit Koeffizienten aus darstellbar sind. (Tatsächlich gibt es eine solche für alle relativ prime die ich finden konnte) [2, 3]:1 [2, 5]:3 [3, 5]:7 [2, 7]:5 [3, 7]:11 [5, 7]:23 [5, 11]:39 [7, 11]:59 [11, 13]:119 [11, 19]:179 [13, 19]:215 [2, 31]:29 [3, 37]:71 [5, 29]:111 [7, 31]:179 [11, 23]:219 [17, 19]:287 [21, 29]:559 Die zugrunde liegende Formel lautet Ist das schon bekannt oder betrete ich hier Neuland? Gruß Sukomaki Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
![]() |
Hallo, also, > [2, 7]:5 kann nicht sein, da ebenfalls darstellbar ist. Mfg Michael EDIT: Jedenfalls interpretiere ich > Sei s die Schranke,[...] > ab der alle Zahlen als Linearkombination von A und B mit Koeffizienten aus ℕ0 darstellbar sind. so, dass die KLEINSTE untere Schranke sei und eben auch Null als Koeffizienten erlaubt. |
![]() |
Das ist ein bekannter Fakt, und lässt sich auch relativ einfach nachweisen: Für gegebenes betrachten wir für die Diophantische Gleichung zunächst die zugeordnete Kongruenzgleichung . Die ist eindeutig lösbar hinsichtlich der Restklassen sowie . Betrachten wir nun die kleinsten nichtnegativen Repräsentanten jener Lösung, dann wissen wir wegen sowie für die Zahl auf jeden Fall und zudem . Die Annahme ist dann gleichbedeutend mit , folglich . Das bedeutet: 1) Für ist , wegen können wir nun beispielsweise Lösung unserer Diophantischen Lösung angeben. 2) Für klappt das hingegen nicht, denn man kann sich leicht davon überzeugen, dass in diesem Fall und ist, mit Ergebnis . -------------------------------------------------------------------- Es gab mal eine IMO-Aufgabe (Nr. 3 von 1983), die ging einen kleinen Schritt weiter: Für paarweise teilerfremde positive Zahlen ist nachzuweisen, dass die Zahl die größte ganze Zahl ist, die sich NICHT in der Form mit nichtnegativen ganzen Zahlen dastellen lässt. |
![]() |
@michaL Hab deinen Beitrag erst jetzt gelesen: Die klarere Formulierung wäre gewesen, dass die größte ganze Zahl ist, die sich nicht so darstellen lässt (vgl. IMO-Aufgabe). Dass es kleinere Zahlen gibt, die dennoch so darstellbar sind, bleibt davon unbenommen. EDIT: Die fehlende Reaktion von Sukomaki deute ich mal als Enttäuschung, kein Neuland betreten zu haben. ;-) |
![]() |
> Die fehlende Reaktion von Sukomaki deute ich mal als Enttäuschung, kein Neuland betreten zu haben. ;-) Sorry, ich bin nun mal nicht der Schnellste im Verarbeiten und Antworten. Das solltest Du inzwischen bemerkt haben. Das hat mit Enttäuschung nichts zu tun. Im Gegenteil : es freut mich, dass jemand denselben Gedankengang hatte. Und in diesem Zusammenhang : Ich habe mal wieder zu kompliziert gedacht. Auf Deinen Post komme ich in Bälde zurück. (Ich hatte heute morgen einiges zu tun) |
![]() |
> mit Ergebnis Typo? zu 1) Probe, dass die Lösung richtig ist : zu 2) , was nicht zulässig ist. Daraus folgt, dass für keine Lösung existiert. Und weil die Lösung eindeutig ist, kommt auch kein anderes in Frage. Ich denke, ich habe es soweit verstanden :-) |
![]() |
Ja klar, Copy+Paste-Typo. Immer Au und Bv, in allen Indexvarianten. ;-) In deiner Argumentation zu 2) gibt es einen Schönheitsfehler: Du darfst da nicht mit der speziellen Lösung von 1) argumentieren - es könnte jemand kommen und sagen: "OK, mit der speziellen Lösungsdarstellung in 1) klappt es hier nicht, aber vielleicht ja mit einer anderen?" Richtig ist, dass im Fall man dann stets wegen sowie entweder oder aber wählen müsste, was in beiden Fällen der geforderten Nichtnegativität der Lösung widerspricht. Und noch was: ist was anderes als . Das Beispiel von michaL zeigt klar, das es auch mit geben kann. |
![]() |
Ist an meinen Überlegungen etwas auszusetzen? Schon interessant, dass für sämtliche Zahlen darstellbar sind. Ach ja genau : Wie kommt die Tatsache ins Spiel, dass und relativ prim sein müssen? Das heißt, wenn ich zum Beispiel und nehme : Warum kann ich nur (außer ) mit mit als Linearkombination darstellen? Oder wenn ich zum Beispiel und nehme : Warum kann ich nur mit mit als Linearkombination darstellen? Eigentlich trivial, aber ich hätte es gerne korrekt formuliert. |
![]() |
> Die ist eindeutig lösbar hinsichtlich der Restklassen sowie . Bei nicht teilerfremden kannst du diese Aussage in die Tonne treten. ;-) Angesichts dessen, dass du laut Überschrift ja das Lemma von Bezout zu kennen scheinst, stellst du reichlich seltsame Fragen in diesem deinen letzten Beitrag... Alle Linearkombinationen sind trivialerweise durch teilbar, was im Fall ... |
![]() |
Mir ging es nur darum, zu sagen, dass höchstens gleich mit sein kann. :-D) Und für relativ prime Zahlen und ist eben Eins. Ist doch richtig, oder? |
![]() |
Habe ich das Argument wie folgt richtig verstanden : Wenn und , dann muss ich etwas von abziehen. Das bedeutet aber nichts anderes als, dass ich von ein , bzw. von ein abziehen müsste (weil die potentielle Lösung eindeutig modulo B, bzw. modulo A ist). Das widerspricht der Nichtnegativität. Ergo existiert keine Lösung. Es gibt aber auch kleiner s, die eine gültige Lösung haben. (wie in dem Beispiel von michaL) |
![]() |
Wir wissen nur sicher: Für klappt es, für nicht. Für hingegen sieht man einen Flickenteppich: Für manche klappt die Darstellung, für andere wieder nicht. Nimm z.B. : Für klappt es nicht. Für klappt es dann aber immer. |
![]() |
Der chaotische, nichttriviale Bereich macht die Angelegenheit doch erst interessant. Ich schaue mir diesen Flickenteppich mal für größere und an. Vielleicht erkenne ich ein Muster darin. |
![]() |
Also, ist einfach : in Binärdarstellung steht für die Darstellbarkeit von . Das läuft über einen Links-Shift (also Multiplikation mit ) mit anschließender Addition von Eins : [2, 3] : [1, 0] 1 [2, 5] : [1, 0, 1, 0] 5 [2, 7] : [1, 0, 1, 0, 1, 0] 21 [2, 9] : [1, 0, 1, 0, 1, 0, 1, 0] 85 [2, 11] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 341 [2, 13] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 1365 [2, 15] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 5461 [2, 17] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 21845 Daraus folgt die Rekursion und daraus wiederum die obige Formel. Jetzt bin ich gerade bei . Mal schauen was draus wird :-) Nur so hier die ersten zu dem : [3, 4] : [100 110] 25 [3, 5] : [100 101 10] 105 [3, 7] : [100 100 110 110] 1737 [3, 8] : [100 100 101 101 10] 6985 [3, 10] : [100 100 100 110 110 110] 112201 [3, 11] : [100 100 100 101 101 101 10] 449097 [3, 13] : [100 100 100 100 110 110 110 110] 7189065 [3, 14] : [100 100 100 100 101 101 101 101 10] 28758601 Es kristallisieren sich erste Muster heraus :-) |
![]() |
Ich kann dir nicht folgen: Wovon redest du überhaupt? Hast du dich im Thread geirrt? Falls doch kein Irrtum: Was zeichnet 341 aus hinsichtlich der Darstellbarkeit von Zahlen in der Form ??? EDIT: Jetzt kapiere ich erst - du willst (warum auch immer) die GESAMTMENGE aller darstellbaren Zahlen in einer Zahl kodieren über deren Binärdarstellung. Allerdings hörst du einfach bei Bitposition auf, die Binärzahl zu bilden, aus verständlichen Gründen: Denn alle Bits ab Position müssten ja 1 sein, womit immer unendlich herauskommt. Wäre es da nicht logisch stringenter, stattdessen die darstellbaren Zahlen mit Binärbit 0 zu kodieren, und die nicht darstellbaren Zahlen mit Bit 1 ? Dann braucht es diese künstliche Stoppbedingung nicht. |
![]() |
und ist darstellbar. ist nicht darstellbar. ist darstellbar. ist nicht darstellbar. ist darstellbar. ist nicht darstellbar. ist darstellbar. ist nicht darstellbar. ist darstellbar. ist nicht darstellbar. Ich ordne "nicht darstellbar" die Null und "darstellbar" die Eins zu. Das gibt mir die Folge . Im Binärsystem interpretiert ist das 341. Das heißt es geht nicht um die Darstellbarkeit von 341. Sondern die 341 enthält die Information über die Darstellbarkeit von So weit nachvollziehbar? Dann schalte ich jetzt einen Gang hoch : Sei und Falls , dann und Falls , dann und Das - im Binärsystem interpretiert - verrät, welche darstellbar sind. |
![]() |
> Wäre es da nicht logisch stringenter, stattdessen die darstellbaren Zahlen mit Binärbit 0 zu > kodieren, und die nicht darstellbaren Zahlen mit Bit 1 ? Dann braucht es diese künstliche > Stoppbedingung nicht. Stimmt. Das habe ich nicht bedacht. Ich probiere das mal aus, was sich dadurch ändert in den Formeln. |
![]() |
Zu : Gemäß Deiner inversen Zuordnung wird aus das nur unwesentlich kompliziertere Das zuständige Bit, das die Darstellbarkeit von codiert, lässt sich beschreiben als wobei "<<" und ">>" die Shift-Operationen sind. Aber das weißt Du schon. Die Formeln für gibt es später. |
![]() |
Nun zu und : Wenn ist, ist und Wenn ist, ist und Durch Zerlegung von lassen sich sämtliche hinsichtlich Darstellbarkeit überprüfen. |
![]() |
Wenn ich mich nicht täusche habe ich ein nettes Zwischenergebnis : Gegeben ein und ein dazu relativ primes . mit Es ist der Funktion nicht sofort anzusehen, aber sie ist tatsächlich symmetrisch. Und noch einfacher ausgedrückt ist EDIT : Oder nach Belieben auch In dieser Form ist die Symmetrie gut einzublicken :-) Und jetzt bist Du dran :-) Sukomaki |
![]() |
@HAL9000 Ist es okay für Dich, wenn ich den Thread hiermit schließe? Ach, ich mache es einfach. Danke für den Tipp mit der inversen Zuordnung. Er har mir sozusagen geholfen, mich zu ordnen :-) Für eine verwandte Frage mache ich einen neuen Thread auf. Sukomaki |