2 ganzzahlige Zahlen finden < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:17 Mi 24.12.2008 | | Autor: | Rudy |
| Aufgabe 1 | 4*k*j + k + j = m
m ist gegeben.
|
| Aufgabe 2 | 4*k*j + 3*k + j = m
m ist gegeben. |
| Aufgabe 3 | 4*k*j + 3*k + 3*j + 2 = m
m ist gegeben. |
Hallo,
ich suche zu den oben genannten Aufgaben, ein verfahren/Algorithmus, um k und j zu bestimmen.
k und j sollten dabei ganzzahlig sein.
Hoffe mal es gibt so ein Verfahren. Weil alles austesten ist bei großen m nicht sonderlich effizient.
Vielen Dank schon mal.
|
|
| |
|
> 4*k*j + k + j = m
> m ist gegeben.
>
> 4*k*j + 3*k + j = m
> m ist gegeben.
> 4*k*j + 3*k + 3*j + 2 = m
> m ist gegeben.
> Hallo,
>
> ich suche zu den oben genannten Aufgaben, ein
> verfahren/Algorithmus, um k und j zu bestimmen.
>
> k und j sollten dabei ganzzahlig sein.
>
> Hoffe mal es gibt so ein Verfahren. Weil alles austesten
> ist bei großen m nicht sonderlich effizient.
>
> Vielen Dank schon mal.
Sind jeweils alle ganzzahligen Lösungspaare
gesucht oder genügt es, jeweils ein Lösungs-
paar anzugeben ?
Im letzteren Fall kann man z.B. mit k=0 die
ersten beiden Gleichungen leicht nach j auflösen,
mit k=-1 die dritte.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:58 Do 25.12.2008 | | Autor: | Rudy |
Danke für deine schnelle antwort.
Ich bräuchte dann alle, bzw. die nicht triviale Lösung.
Bin momentan davon ausgegangen, dass es eine eindeutige positive ganzzahlige Lösung für das Problem gibt.
Das mit 0 und -1 setzen ist eine tolle Idee, aber leider nicht die, die ich gesucht habe.
Bei dem Problem bin ich mir auch nicht sicher, ob es ein Verfahren gibt, das es in angemessener Zeit löst (alles durchzuprobieren ist nicht das wahre).
Es ist ja sowas wie eine Faktorisierung. Nur wenn ich mal mit ein paar Testwerten rumspiele, sind k und j nicht zwangsläufig Primzahlen.
Aber man kann davon ausgehen, dass es zu jeden m, auch ganzzahlige j und k gibt, das hast du ja eigentlich schon gezeigt, dass k=0 bzw. k=-1, für die einzelnen Formeln gelten würde.
Frohe Weihnachten.
|
|
|
| |
|
Da ja weder j,k noch m zur Zeit gegeben sind und Du "nur" einen Algorithmus suchst, würde ich Dir den ![[]](/images/popup.gif) Chinesischen Restsatz empfehlen. Vielleicht ist dazu auch diese Seite hilfreich.
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:04 Fr 26.12.2008 | | Autor: | Rudy |
Vielen Dank.
muss nur mal schauen, wie ich das jetzt anwenden kann :-/
Kann dir aber gerne mal ein paar Beispiele für m geben 
Für 1. Aufgabe:
m=645 -> j = 7 ; k = 22
m=121 -> j = 24; k = 1
Es ist ziemlich spät geworden für mich.
Werde mich die Tage daran setzen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:05 Fr 26.12.2008 | | Autor: | felixf |
Hallo
Wenn du die urspruengliche Gleichung nach $j$ aufloest, erhaelst du sowas wie $j = [mm] \frac{m - k}{4 k + 1}$. [/mm] Dies ist nur dann loesbar, wenn $|4 k + 1| [mm] \le [/mm] |m - k|$ ist (ansonsten waer der Bruch vom Betrag kleiner 1) oder wenn $m = k$ ist. Wenn insbesondere $k$ gegen unendlich geht, ist irgendwann $|4 k + 1| > |m - k|$. Du bekommst also eine endliche Menge von Werten, die $k$ annehmen kann.
(Um eine Schranke zu finden kannst du $|m - k| [mm] \le [/mm] |m| + |k|$ abschaetzen: ist $k [mm] \ge [/mm] 0$, so ist $|4 k + 1| = 4 k + 1$ und somit $|4 k + 1| [mm] \le [/mm] |m| + |k| [mm] \Longleftrightarrow [/mm] k [mm] \le \frac{|m| - 1}{3}$, [/mm] und ist $k < 0$, so ist $|4 k - 1| = -4 k - 1$ und $|4 k + 1| [mm] \le [/mm] |m| + |k| [mm] \Longleftrightarrow [/mm] k [mm] \ge -\frac{|m| + 1}{3}$. [/mm] Insgesamt bekommst du also [mm] $-\frac{|m| + 1}{3} \le [/mm] k [mm] \le \frac{|m| - 1}{3}$ [/mm] als Suchbereich fuer $k$, also ca. [mm] $\frac{2}{3}|m|$ [/mm] moegliche Werte.)
Diese kannst du natuerlich alle durchprobieren und fuer jeden moeglichen Wert von $k$ testen, ob $m - k$ durch $4 k + 1$ teilbar ist; wenn dies der Fall ist, hast du eine Loesung $(j, k)$ gefunden.
> Aber wie hast du dir das gedacht, dass man den
> chinesischen Restsatz anwenden kann?
Ich weiss nicht, ob man ihn hier wirklich so toll anwenden kann: modulo einer Primzahl ist die Gleichung fuer so ziemlich jedes $k$ nach $j$ aufloesbar. Insofern denke ich nicht, dass es Sinn macht ihn zu verwenden.
Prinzipiell kann man den CRT (Chinese Remainder Theorem) so benutzen: man findet Loesungen modulo Primzahlen [mm] $p_1, \dots, p_t$, [/mm] und kann diese dann zu allen Loesungen modulo [mm] $\prod_{j=1}^t p_j$ [/mm] zusammensetzen. Und wenn man weiss, dass die Loesungen in [mm] $\IZ$ [/mm] gesucht sind und alle vom Betrag her $< [mm] \frac{1}{2} \prod_{j=1}^t p_j$ [/mm] sind, dann sind unter den Loesungen modulo [mm] $\prod_{j=1}^t p_j$ [/mm] bereits alle aus [mm] $\IZ$ [/mm] enthalten und man kann diese durch durchgehen der Loesungen finden.
Das Problem ist hier halt, dass man fuer fast jedes $k$ aus [mm] $\IZ [/mm] / [mm] (\prod\nolimits_{j=1}^t p_j) \IZ$ [/mm] eine Loesung findet, aber die meisten nicht von Loesungen aus [mm] $\IZ$ [/mm] stammen -- hier bringt das also nichts.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:40 Fr 26.12.2008 | | Autor: | abakus |
> 4*k*j + k + j = m
> m ist gegeben.
Diese Gleichung ist äquivalent zu (4k+1)(4j+1)=4m+1.
Je nach gegebenem m dürfte es nur eine begrenzten Anzahl von Möglichkeiten geben, 4m+1 zu faktorisieren.
Gruß Abakus
>
> 4*k*j + 3*k + j = m
> m ist gegeben.
> 4*k*j + 3*k + 3*j + 2 = m
> m ist gegeben.
> Hallo,
>
> ich suche zu den oben genannten Aufgaben, ein
> verfahren/Algorithmus, um k und j zu bestimmen.
>
> k und j sollten dabei ganzzahlig sein.
>
> Hoffe mal es gibt so ein Verfahren. Weil alles austesten
> ist bei großen m nicht sonderlich effizient.
>
> Vielen Dank schon mal.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:14 Fr 26.12.2008 | | Autor: | felixf |
Hallo
> > 4*k*j + k + j = m
> > m ist gegeben.
>
> Diese Gleichung ist äquivalent zu (4k+1)(4j+1)=4m+1.
> Je nach gegebenem m dürfte es nur eine begrenzten Anzahl
> von Möglichkeiten geben, 4m+1 zu faktorisieren.
Stimmt. Zumindest solange $4 m + 1$ nicht zu gross wird und es sich nicht mehr faktorisieren laesst :)
Bei den naechsten beiden kann man genauso vorgehen. Wie das dann genau aussieht ist dem Fragesteller ueberlassen nachzurechnen :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:01 Fr 26.12.2008 | | Autor: | Rudy |
| Aufgabe | | Könnte man dieses Problem nicht mit einer Diophantische Gleichung Lösen? |
Naja, viel hilft mir das leider nicht, denn davon kam ich ja.
(4*k+1)*(4*l+1) = n
war meine Ausgangsgleichung..
Bin nur davon ausgegangen, dass 4*k*j + k + j = m einfacher zu lösen sei (m wäre in diesen Falle immer ganzzahlig, da ich nur diesen Fall betrachte, wenn (n-1)/4 ganzzahlig ist, ansonsten nehme ich eine von der anderen Form:
(4*k+1)*(4*l+3)=n
(4*k+3)*(4*l+3)=n
und diesmal ist n auch immer wieder ganzzahlig (auch nach dem umstellen zu m)
Aber zum ursprünglichen Problem.
wie schon oben in meiner Frage steht, könnte man dieses Problem nicht mit einer Diophantische Gleichung Lösen?
Ich habe es zwar versucht, aber bin daran gescheitert, weil ich nicht weiß wie man l*k behandeln soll.
Wenn ich eins einfach nur als "konstante" betrachte, dreh ich mich nur im kreis.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:47 Fr 26.12.2008 | | Autor: | felixf |
Hallo
> Könnte man dieses Problem nicht mit einer Diophantische
> Gleichung Lösen?
>
> Naja, viel hilft mir das leider nicht, denn davon kam ich
> ja.
Das haettest du dann auch gleich erwaehnen koennen.
> (4*k+1)*(4*l+1) = n
> war meine Ausgangsgleichung..
> Bin nur davon ausgegangen, dass 4*k*j + k + j = m
> einfacher zu lösen sei
Wieso sollte es?
> (m wäre in diesen Falle immer
> ganzzahlig, da ich nur diesen Fall betrachte, wenn (n-1)/4
> ganzzahlig ist, ansonsten nehme ich eine von der anderen
> Form:
> (4*k+1)*(4*l+3)=n
> (4*k+3)*(4*l+3)=n
> und diesmal ist n auch immer wieder ganzzahlig (auch nach
> dem umstellen zu m)
>
> Aber zum ursprünglichen Problem.
> wie schon oben in meiner Frage steht, könnte man dieses
> Problem nicht mit einer Diophantische Gleichung Lösen?
Du kannst es natuerlich als eine Diophantische Gleichung formulieren. Aber fuer solche gibt es im Allgemeinen keine schnellen Loesungsalgorithmen.
> Ich habe es zwar versucht, aber bin daran gescheitert, weil
> ich nicht weiß wie man l*k behandeln soll.
> Wenn ich eins einfach nur als "konstante" betrachte, dreh
> ich mich nur im kreis.
Es ist keine Konstante.
Die einfachste Moeglichkeit diese Gleichung zu loesen ist wohl ueber's faktorisieren.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:44 Sa 27.12.2008 | | Autor: | Rudy |
Danke.
Dann ist das Thema für mich abgeschlossen.
Thx für eure Hilfe.
|
|
|
|
