Algorithmus zur Termzerlegung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:13 So 27.12.2009 | | Autor: | ggg |
Hallo,
Ich suche ein Algorithmus, womit ich einen Term zur seinen einzelnen alternierenden Komponenten zerlegen kann, wobei der Term hier nur eine Zahl ist.
Beispielsweise lässt sich die 10 in 1;2;3;4 zerlegen
und die 14 in 2;3;4;5 zerlegen.
Jedoch je größer der Term ist, desto aufwendiger wird die Suche. Deshalb suche ich ein Algorithmus dafür. Google sagt mir dafür nichts. Wahrscheinlich weil ich kein geeigneten Namen für das Problem finde. Ich habe auch keine Universitätsbücher, da ich noch kein Student bin. Ich würde euch für jede Hilfe dankbar sein
mfg
Jonas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:02 So 27.12.2009 | | Autor: | fencheltee |
> Hallo,
> Ich suche ein Algorithmus, womit ich einen Term zur seinen
> einzelnen alternierenden Komponenten zerlegen kann, wobei
> der Term hier nur eine Zahl ist.
> Beispielsweise lässt sich die 10 in 1;2;3;4 zerlegen
> und die 14 in 2;3;4;5 zerlegen.
> Jedoch je größer der Term ist, desto aufwendiger wird die
> Suche. Deshalb suche ich ein Algorithmus dafür. Google
> sagt mir dafür nichts. Wahrscheinlich weil ich kein
> geeigneten Namen für das Problem finde. Ich habe auch
> keine Universitätsbücher, da ich noch kein Student bin.
> Ich würde euch für jede Hilfe dankbar sein
>
> mfg
> Jonas
also ne zahl >=10 soll darauf untersucht werden, ob sie als summe von 4 aufeinanderfolgenden natürlichen zahlen geschrieben werden kann oder wie?
gruß tee
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:44 So 27.12.2009 | | Autor: | ggg |
Die 10 war nur ein Beispiel.
Eigentlich suche ich einen Algorithmus für einen Algemeinen Fall.
Die Anzahl der alternierenden Komponenten muss schon größer gleich 2 sein, ansonsten ist es nicht alternierend. Und genau, die Komponenten sind natürliche Zahlen.
Ich versuche noch einmal an Hand von Beispielen zu verdeutlichen was ich meine:
1 kann man in 0 und 1 zerlegen da 0 + 1 = 1 ist
9 kann man 2;3;4 zerlegen da 2 + 3 + 4 = 9 ist
10 kann man in 1;2;3;4 zerlegen da 1 + 2 +3 + 4 = 10 ist
635 kann man in 125;126;127;128;129 zerlegen, da die Summe der alternierenden Komponenten gleich 635 ergeben.
Apropos, wenn es nicht ganz so klar ist, mit alternierend meine ich aufeinanderfolgend.
Ideal wäre es wenn man den Term in einem Algoritmus eingeben würde und er dann die einzelnen alternierenden Komponeneten ausspucken könnte oder wenigstens den ersten Komponent und den letzten Komponent zurück geben würde.
Aber wenn du ein Algorithmus parat hast, der die Zusammensetztung eines Termes nur für 4 alternierenden Komponeneten zurück gibt, dann nehme ich ihn auch 
mfg
Jonas
|
|
|
| |
|
Hiho,
erstmal *brrrr*
Bitte nicht mit Fachausdrücken um sich werfen, wenn man nicht weiss, was sie bedeuten.
Das verwirrt mehr als das es nützt, denn
> Apropos, wenn es nicht ganz so klar ist, mit alternierend
> meine ich aufeinanderfolgend.
Schön dass du das meinst, das heisst es aber nicht, siehe ![[]](/images/popup.gif) hier..... aber egal jetzt.
Zu deinem Problem: ob es eine solche Reihe von Zahlen gibt kannst recht leicht berechnen.... nur der Aufwand wird für grosse Zahlen recht hoch, aber erstmal zur allgemeinen Lösung:
Sei $x$ deine Zahl, in deinem Fall, $m+1$ die Anzahl der Summanden (in deinem Beispiel gleich 4), dann soll ja gelten:
$n + (n+1) + (n+2) + ... + (n + m) = x$
umstellen gibt
$(m+1)n + (1 + 2 + ... + m) = x$
$(m+1)n + [mm] \bruch{1}{2}m(m+1) [/mm] = x$
Den Kram nach n umstellen, also:
$n = [mm] \bruch{x}{m+1} [/mm] - [mm] \bruch{1}{2}m [/mm] $
Nun musst für jedes x und m nur prüfen, ob n eine ganze Zahl ist.
Schon hast zu jeder Zahl eine entsprechende Reihe (oder halt nicht, wenn n nie ganz wird).
Natürlich ist die Zahl m gedeckelt (wodurch, bitte eine einfache obere Schranke die man sofort sieht und eine aufwandsarme für dein Programm  )
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:42 Mo 28.12.2009 | | Autor: | ggg |
Absolute Spitze, ich danke dir sehr. Ich will gerne noch wissen wie du umgeformt hast. Es fällt mir etwas schwer diese Stelle nach zu vollziehen:
$ (m+1)n + (1 + 2 + ... + m) = x $
$ (m+1)n + [mm] \bruch{1}{2}m(m+1) [/mm] = x $
Wenn du mir das genauer zeigst, wäre ich dir sehr verbunden.
mfg
Jonas
|
|
|
| |
|
> Absolute Spitze, ich danke dir sehr. Ich will gerne noch
> wissen wie du umgeformt hast. Es fällt mir etwas schwer
> diese Stelle nach zu vollziehen:
>
>
> [mm](m+1)n + (1 + 2 + ... + m) = x [/mm]
>
> [mm](m+1)n + \bruch{1}{2}m(m+1) = x[/mm]
hier wurde der kleine gauß angewandt...
[mm] 1+2+3+....+m=\sum_{i=1}^m [/mm] i [mm] =\frac{m(m+1)}2
[/mm]
>
> Wenn du mir das genauer zeigst, wäre ich dir sehr
> verbunden.
>
> mfg
> Jonas
gruß tee
|
|
|
| |
|
Hallo ggg,
Wikipedia ist ja eine ewige Baustelle. Der Eintrag "alternierend", den Gonozal verlinkt hat, ist noch nicht fertig. Entsprechend seiner Herleitung aus dem Lateinischen bedeutend "alternierend" abwechselnd und wird in verschiedenen Wissenschaften - wie Wikipedia ja schon andeutet - in verschiedener Weise benutzt. In der Mathematik ist das wahrscheinlich häufigste Vorkommen im Bereich von Folgen und Reihen, wo das Wort normalerweise bedeutet, dass Folgenglieder abwechselnd positiv und negativ sind.
Das Fremdwort, das Du suchst, heißt konsekutiv und findet sich in der deutschen Wikipedia auch noch nicht, auch nicht in der englischen. Interessant eigentlich...
Aber zur Sache:
Du willst wissen, ob eine natürliche Zahl n als Differenz zweier Dreieckszahlen [mm] \Delta_i-\Delta_j [/mm] dargestellt werden kann.
Dabei scheinst Du auch die Null als Dreieckszahl zuzulassen, bewegst Dich also in [mm] \IN_0.
[/mm]
Eine weitere Einschränkung ist, dass die Ordinalzahlen (Indizes) der beiden Dreieckszahlen um mehr als 1 differieren sollen. Das ist eine nötige Einschränkung, weil sonst ja immer gilt [mm] n=\Delta_n-\Delta_{n-1}.
[/mm]
Ab hier ist die Aufgabe allerdings nicht mehr so einfach. So wirst Du z.B. feststellen, dass die 198 auf genau drei Weisen als Summe konsekutiver Zahlen dargestellt werden kann, die 128 aber überhaupt nicht.
Um das anders als experimentell zu ermitteln, müsstest Du aber wahrscheinlich mehr über Zahlentheorie wissen, als ich annehme, dass Du schon weißt. Es gehören Restklassen dazu, vielleicht auch quadratische Reste (obwohl mir scheint, dass man diese hier sogar irgendwie vermeiden kann), und natürlich Faktorenzerlegungen. Eine allgemeine Lösung scheint es trotzdem nicht zu geben, sondern nur Bedingungen, wann eine Lösung existiert und wann nicht. Die Wahrscheinlichkeit, dass n so dargestellt werden kann, steigt mit der Größe von n. Vielleicht gibt es sogar ein größtes n, dass nicht so dargestellt werden kann. Das glaube ich aber nicht. Die Fragestellung scheint auf den ersten Blick so vertrackt, dass bei mir sofort Gödels Unvollständigskeitssatz zu klingeln beginnt. Andererseits habe ich durchaus eine Lösungsidee, wie die Nichtexistenz eines größten n gezeigt werden könnte...
All das ist mit brutaler Gewalt (brute force) nicht gut zu untersuchen. Wenn Du da wirklich schon mehr daran arbeiten willst, empfehle ich Dir das Buch von Armin Leutbecher: Zahlentheorie. Eine Einführung in die Algebra. Vielleicht gibt es Dir auch schon einen Eindruck davon, was Dich im Mathematikstudium erwartet. Es ist eigentlich mit Schulwissen (zumal LK) durchaus verständlich, aber sicher ungewohnt in Darstellung und Geschwindigkeit des Fortschreitens.
Herzliche Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:15 Mo 28.12.2009 | | Autor: | ggg |
Ich danke dir reverend für dein Beitrag, das hat mich sehr zum nachdenken erregt. Und danke noch einmal wegen der Worterklärung. Wenn ich mal fragen darf, könntest du mir mal zeigen wieso aber 198 auf genau drei Weisen als Summe konsekutiver Zahlen dargestellt werden kann.
mfg
Jonas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:16 Mo 28.12.2009 | | Autor: | reverend |
Hallo Jonas,
sorry, da war ich zu schnell. Es gibt vier Möglichkeiten, aber keine mehr:
198=65+66+67
198=48+49+50+51
198=18+19+20+21+22+23+24+25+26
198=13+14+15+16+17+18+19+20+21+22+23
Die zweite Möglichkeit habe ich vorhin übersehen, weil mein Ansatz unvollständig war.
Wenn Du die Zahl n aus m aufeinanderfolgenden (konsekutiven) Summanden erzeugen willst, dann heißt das ja:
[mm] n=\summe_{i=0}^{m-1}(k+i)=m*k+\summe_{i=0}^{m-1}i=m*k+\bruch{m(m-1)}{2}
[/mm]
Hieraus folgt schnell, dass für ungerade m Dein n durch m teilbar sein muss, und für gerade m Dein n bei Teilung durch m den Rest [mm] \tfrac{m}{2} [/mm] lassen muss. Das ist allerdings nicht die einzige Bedingung. Du kannst ja auch den "mittleren" Summanden ausrechnen (der natürlich genau [mm] \tfrac{n}{m} [/mm] ist), der aber entweder eine natürliche Zahl (bei ungeradem m) sein muss oder in der Mitte zwischen zwei natürlichen Zahlen (bei geradem m) liegen muss. Das schränkt die Auswahl doch schon erheblich ein.
Außerdem muss der mittlere Summand [mm] \overline{s}\le\bruch{m}{2} [/mm] sein, bzw. bei Betrachtung in [mm] \IN_0\quad \overline{s}\le\bruch{m-1}{2}, [/mm] weil sonst mindestens ein negativer Summand aufträte.
Die Zahl der zu untersuchenden Fälle ist daher nicht groß und ohne jede Probe eindeutig lösbar. Die Untersuchung setzt aber eine vollständige Liste aller Teiler von n voraus und geht über sie hinaus. (am Beispiel 198: 4 ist ja kein Teiler von 198, dennoch gibt es eine Zerlegung in vier Summanden).
lg
reverend
|
|
|
|
