erste Reihe:
297
298
300
303
307
usw. also a = 297 + (x^2+x)/2
zweite Reihe:
328
327
326
325
usw. also b = 328-x
Frage: Gibt es eine Formel, mit der ich x berechnen kann, wenn gelten soll:
a mod b = 0 ?
Viele Grüße,
Marc :)
Aetna
13.01.2004, 22:39
Hallo Marc,
wenn ich mich nicht verrechnet habe, gibt es nur die "trivialen" Lösungen
x=327 und x=329
Ansonsten gilt immer a mod b <>0
Woher kommt denn die Aufgabe?
nobody
13.01.2004, 22:59
Hallo Aetna!
Naja, diese Lösungen meine ich natürlich nicht.
:-)
Es gibt auch noch x=89
Jemand sagte mir, es ginge da was mit Polynomdivision, wobei x dann so gewählt werden müßte, daß eine Ganzzahl da rauskommt. Das konnte ich aber nicht virifizieren (was nicht heißt, daß es nicht geht).
Diese Aufgabe ist ein Teilbereich einer Knobelei, die ich mir vorgenommen habe. Es würde nichts bringen, den Rest auch noch anzugeben. Es würde viel zu unübersichtlich und das Problem reduziert sich letztlich auf eben diese Frage.
Viele Grüße,
Marc
Lim_Dul
13.01.2004, 23:17
x=89 kann keine Lösung sein, da 297 + (x^2+x)/2 für ein ungerades x ein Zahl mit mit ,5 am Ende liefert. Und das geteilt durch eine ganze Zahl lässt immer einen Rest.
nobody
13.01.2004, 23:38
Aber nein. 297 + (89^2+89)/2 ergibt 4302 :-)
Der Teiler bezieht sich ja auf den Inhalt der ganzen Klammer - sollte Dein Irrtum darauf beruhen.
Viele Grüße,
Marc
Lim_Dul
13.01.2004, 23:42
Stimmt, ich war zu doof zum rechnen, hab 89^2 für eine gerade Zahl gehalten *pfeif*
Aetna
14.01.2004, 11:31
Hallo Marc,
da habe ich mich wohl gestern Abend doch verrechnet.
Mein Ansatz ist der folgende:
a mod b = 0 bedeutet, es gibt ein k aus Z mit
297 + (x^2+x)/2 = k*(328-x)
daraus folgt für x:
x = <font class="serif">±</font>1/2 * wurzel(4k2+2628k-2375)
Da x und k ganzzahlig sind, muß der Radikant eine Quadratzahl (n2) sein, d.h.
n2 = (2k+657)2 - 434024
bzw.
(n-2k-657)*(n+2k+657) = 434024
Da links ein Produkt aus ganzen Zahlen steht, können diese nur aus (positiven oder negativen!) Teilern von 434024 = 1*2*2*2*227*239 bestehen.
Also z.B. 1*434024 = 434024, woraus n=434025/2 folgt, was offensichtlich keine ganze Zahl ist. Die entsprechende negative Lösung (-1)*(-434024) fällt damit auch weg.
Deine Lösung x=89 entspricht hier dem Produkt
(-478)*(-908) = (-2*239) * (-4*227) = 434024,
woraus n=<font class="serif">±</font>215 , k=18 und x=89 folgt.
Insgesamt, bei Durchprobieren aller Faktoren, erhalte ich 8 Lösungen:
x = 89, 101, 326, 327, 329, 330, 555, 567
mit den zugehörigen (ersten) Faktoren von 434024:
-478, -454, -4, -2, 2, 4, 454, 478
L.G.
Aetna
Ergänzung:
Ich habe oben immer nur als ersten Faktor den Kleineren der beiden genommen, da ich dachte, dass aus Symmetriegründen keine neuen Lösungen entstehen. Das stimmt nicht. Somit ergeben sich weitere 4 positive Lösungen für x:
x = 782, 806, 54581, 108834
mit den zugehörigen (ersten) Faktoren von 434024:
908, 956, 108506, 217012.
Ausserdem gibt es noch 4 negative Lösungen (die Dich aber wohl nicht interessieren, denke ich):
x = -126, -150, -53925, -108178.
nobody
16.01.2004, 12:29
Hallo Aetna!
Vielen Dank für Deine ausführlichen Gedanken und Ideen! In der Tat ist Dein Ansatz wirklich sehr interessant. Leider habe ich vergessen, zu sagen, daß die Berechnung auch bei sehr großen Zahlen funktionieren muß. Und da klappt es ja leider mit der Faktorisierung nicht mehr, die Du einsetzt. Meinst Du, es geht vielleicht auch ohne Faktorisierung?
Viele Grüße,
Marc
Aetna
16.01.2004, 20:07
Hallo Marc,
wie groß können die Zahlen denn werden?
Mein Verfahren führt ja auf einen Typ von Diophantischer Gleichung (die auch unendlich viele Lösungen haben können). Ob diese Gleichung auch ohne Faktorisierung auskommt, weiß ich nicht. Kann ich mir aber nicht vorstellen, da die Anzahl der Lösungen (bei diesem Typ) eng mit der Anzahl der Faktoren der rechts auftretenden Zahl (hier 434024) verknüpft ist.
Zahlen bis etwa 10^16 lassen sich aber meist noch faktorisieren. Da diese Zahl jedoch im wesentlichen aus quadratischer Ergänzung der ursprünglichen linearen Folge entsteht, würden sich Folgen mit Konstanten in der Größenordnung 10^8 wohl noch berechnen lassen.
Vielleicht kann man ja auch Folgen mit großen Konstanten durch Indextransformation in kleinere umwandeln? Du müßtest mal ein Beispiel für ein Problem mit großen Konstanten angeben.
Gruß
Aetna
P.S.: In welchem Zusammenhang treten solche Aufgaben denn auf?
nobody
16.01.2004, 20:20
Hallo Aetna!
Nanu? Nicht unterwegs am Freitag Abend?
Tja, die Zahlen können schon sehr groß werden. So um 10^300. Wenn Du willst, kann ich natürlich auch entsprechende Beispielzahlen für Dich konstruieren.
Das "Hauptproblem" selbst ist eigentlich sogar noch ein anderes. Das scheint mir intuitiv sogar einfacher lösbar zu sein. Da ich es aber nicht hinbekommen hatte, habe ich das Problem auf eine andere Ebene transformiert, nämlich die oben angegebene. Du warst aber schon so nett und hast so viel Zeit investiert, da will ich Dich jetzt nicht noch mit einem - auf den ersten Blick - anderen Rätsel belasten. Es sei natürlich, Du möchtest das. Das werde ich es gerne posten. :-)
Viele Grüße aus Dortmund,
Marc
Aetna
16.01.2004, 22:48
Hallo Marc,
natürlich interessiert mich das!
Nun schieß schon los!
Grüße aus Köln (Bergheim)
Aetna
nobody
16.01.2004, 23:37
Hallo Aetna!
Bergheim gehört zu Köln? Na,na,na! Habe ein halbes Jahr in Köln-Weiden gewohnt. Ich weiß Bescheid mit Berheimern. ;-)
Also gut. Hier kommt das Haupträtsel:
Ich habe zwei Zahlenfolgen und suche eine Formel für unten stehende Frage (oder zumindest einen Algo, dessen Rechenaufwand NICHT linear mit der Größe der Initialwerte der Zahlenfolgen zunimmt).
Zur Zahlenreihe 1 muß ich nicht viel erklären. Aber zur Zahlenreihe 2:
Sie startet per Definition bei 56. Die folgende Zahl ist , ebenfalls per
Definition, um 47 höher. Die darauf folgende um 48 usw. Du siehst nun, daß
nach der 250 plötzlich ein Bruch in der Zahlenreihe eintritt und sie
plötzlich wieder bei 20 anfängt. Dann ist die nächste nicht um 47 höher,
sondern um 53. Dann 54 usw.
Erklärung: Dieser Bruch tritt immer dann auf, wenn ein weiteres Aufsummieren
der anstehenden Zahl die Summe größer werden lassen würde als die parallele
Zahl der ersten Zahlenreihe. Eigentlich sollte anstelle der 20 also eine 301
dort stehen. 301 wäre aber größer als die paralle Zahl der ersten
Zahlenreihe, also die 281. Daher fängt die Zahlenreihe wieder bei 20 an
(301-281). Nun folgt auf die 20 die 73. Der Abstand ergibt sich auch hier
wieder aus der Zunahme um jeweils einen Zähler. Bei jeder Sprungstelle wird
aber noch einmal ein Zähler zusätzlich draufgesetzt. Alles klar sowei?
Und nun die Frage: Wie lautet die parallele Zahl aus Zahlenreihe 1, wenn in
Zahlenreihe 2 die "10" erreicht ist? Es gilt natürlich nicht, das konkrete Ergebnis, sondern eine Formel rauszukriegen, die nicht auf Faktorisierung angewiesen ist.
Harter Tobac, was? :-)
Das klingt jetzt etwas chaotisch, aber wenn Du die Zahlenfolgen visuell vor Augen hast, ist das alles schon ziemlich klar und schein (mir) intuitiv auch lösbar zu sein. Immerhin gibt es da einen eindeutigen Wert, den man suchen kann und man ist nicht auf Modulo irgendwas angewiesen.
Wenn Du möchtest, schicke ich Dir gerne eine Excel-Tabelle. Dort ist das viel griffiger.
Aetna, wenn Du das hinbekommst, werde ich Dich reich belohnen. Ich schwöre es! Ich rätsele schon so lange daran rum. Allerdings komme ich nicht aus der Mathematik, wie Du anscheinend. Daher gibt es natürlich noch eine relle Chance, daß das hier lösbar ist.
Viele Grüße,
Marc
Aetna
17.01.2004, 01:06
Hallo Marc,
das Problem habe ich, denke ich, verstanden.
Ich nehme an, dass in Deiner Erklärung
Dieser Bruch tritt immer dann auf, wenn ein weiteres Aufsummieren der anstehenden Zahl die Summe größer werden lassen würde als die parallele Zahl der ersten Zahlenreihe.
größer gleich gemeint ist.
Dann läßt sich die zweite Folge (zn) , n = 0 , 1, 2, 3 ... schreiben als
zn = 1/2 * (n2+93n+112) mod (286-n)
Damit kann man Dein Problem so definieren, dass Du diese Gleichung nach n (und damit nach 286-n) auflösen willst.
Wie wir oben gesehen haben, ist die Lösung aber nicht eindeutig. Es können sogar unendlich viele, oder gar keine Lösungen existieren. Möchtest Du ggf. die kleinste Lösung, d.h. den Wert der ersten Folge, bei erstmaligem Auftreten von 10 in der 2. Folge?
Ich schaue mal, ob der obige Ansatz zum Ziel führt.
Allerdings sehe ich noch nicht, wo hier große Zahlen auftreten. Gibt es eine allgemeinere Formulierung (dieser spezielle Fall ist ja ähnlich, wie Deine erste Frage) des Problems?
Aus welchem Gebiet (Informatik, Physik, etc.) kommt denn die Aufgabe? Mit welchem Problem ist sie verbunden?
Bis dann,
Aetna
P.S.: Ich habe Köln geschrieben, weil Bergheim wohl keiner kennt (dachte ich). Aber BM ist bei (ehemaligen) Kölnern wohl berüchtigt ;-)
Aetna
17.01.2004, 01:39
Erstes Ergebnis:
Die Lösung läßt sich für vorgegebenes zn genau wie oben bestimmen:
n = k - 93/2 <font class="serif">±</font>1/2 * wurzel((2k-665)2 - 434024 + 8zn)
für ein k aus Z (falls ich mich nicht verrechnet habe).
D.h. man bräuchte die Faktorzerlegung von 434024-8*zn = 8*(54253 - zn) um die Lösungen wie oben zu erhalten. Da also der Faktor 2 bzw. -2 immer in der Zerlegung auftaucht (ebenso, wie 4, 8 und die entsprechenden Kofaktoren), hat man wahrscheinlich zumindest ein paar Lösungen. Eine Berechnung hierzu mache ich morgen.
Immerhin sieht man, dass es nur endlich viele Lösungen (evtl. auch keine) geben kann.
Ob es noch eine andere Möglichkeit der Lösungsherleitung gibt, überlege ich mal am Wochenende.
L. G.
Aetna
nobody
21.01.2004, 16:35
Hallo Aetna!
Hey, Du hast ja schon längst geantwortet!! Ich dachte, ich bekomme dann automatisch eine E-Mail. Naja, könnte auch an meinen ca. 100 Spammails liegen, die ich täglich erhalte. Da geht schon mal was unter.
Hey, Du bist echt gut! Mathematik ist wohl mehr als Dein Hobby, stimmt´s?
Vielleicht noch eine Zusatzbemerkung zu meinem Problem: Ich weiß vorher schon, daß es eine Bestimmte Anzahl an Lösungen gibt. Es reicht in der Tat, die erste zu finden, also wo das erste Mal "ist gleich 10" auftritt.
Wenn Du mehr Hintergründe erfahren möchtest, dann per Mail. Scheib´mich dann bitte kurz an: marc@waesche.org
Nun suche ich das x, bei dem f(x) ein Vielfaches von 328 ist oder f(x) mod 328 = 0
Auch hier gilt natürlich: Faktorisierung nicht erlaubt :-)
Viele Grüße,
Marc
P.S.: Das richtige x ist 90
Marvek
22.01.2004, 12:50
Originalnachricht erstellt von marcimarc
Ich dachte, ich bekomme dann automatisch eine E-Mail
Wenn Du unten auf "Thema abonnieren" http://www.studenten-city.de/forum/images/subscribe.gif klickst, dann sollte die Benachrichtigung bei Antworten im Thread funktionieren.