Forum:  Zahlentheorie
Thema: Stammbruchzerlegung - Primteilermethode
Themen-Übersicht
MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Themenstart: 2019-12-07 19:15

Hi... ich hab mir ausgehend von dem Thread: hier eine Methode zur Zerlegung eines positiven Bruches in Stammbrüche überlegt.

Mich würde interessieren, ob es dieses Verfahren schon gibt?
Und unten am Ende hab ich noch 2 Fragen...



Hier die Methode:
Gegeben sei ein positiver, vollständig gekürzter Bruch \(q\) kleiner als 1:
\(q = \frac{z}{n}; z,n \in \IN^+; \gcd(z,n) = 1; z < n\)

Dir Primfaktorzerlegung des Nenners \(n\) sei dann:
\(n = \prod p_i^{a_i}; a_i \in \IN^+\)

Wir definieren nun den größten Primteiler (inklusive Potenz):
\(P = \max(p_i^{a_i})\)
[dies entspricht Pmax im Programm]

Damit der Bruch \(q\) eine Zerlegung in Stammbrüche besitzt, muss der Nenner von mindestens einem Stammbruch ein Vielfaches von \(P\) sein - da ansonsten \(P\) kein Teiler des kleinsten, gemeinsamen Nenners aller Stammbrüche wäre und somit auch kein Teiler des Nenners \(n\) sein könnte. Wir suchen somit eine Zerlegung von \(q\) in Stammbrüche mit Vielfachen von \(P\):
\(q = \frac{z}{n} = \sum \frac{1}{f_i \cdot P} + \frac{z'}{n'}\)

Der letzte Bruch \(\frac{z'}{n'}\) beschreibt dabei einen gekürzten Restbruch, für den gelten soll:
\(P  \nmid n'\)

Der kleinste Faktor \(f\) ist dabei mindestens:
\(\frac{1}{f_{min} \cdot P} \leq \frac{z}{n} \to f_{min} \geq \frac{n}{z \cdot P}\\
f_{min} = \lceil \frac{n}{z \cdot P} \rceil\)
[dies entspricht Fmin im Programm]


Die obige Zerlegung in Stammbrüche soll dabei zu einem möglichst kleinen \(f_{max}\) führen, so dass der Nenner des Restbruches nicht mehr durch \(P\) teilbar ist:
\(\frac{z}{n} = \sum_{i=0}^{d} \frac{\epsilon_i}{(f+i) \cdot P} + \frac{z'}{n'}\\
\epsilon_i \in \{0;1\}; \epsilon_d = 1; f = f_{min} = \lceil \frac{n}{z \cdot P} \rceil; f+d = f_{max}; P  \nmid n'\)
[im Programm: die Binär-Darstellung von komb speichert die Epsilon, wobei das letzte immer 1 ist (komb ist ungerade); Fkomb speichert dann die verwendeten Faktoren f+i; Fdif entspricht dem d; Fmax dem f+d]


Nun definieren wir das Produkt:
\(\pi = \prod_{i=0}^d (f+i)^{\epsilon_i}\)
[dies entspricht Fprod im Programm]

Mit \(\pi \cdot n\) lässt sich jetzt die Gleichung erweitern:
\(\pi \cdot z = \left( \frac{n}{P} \right) \cdot \sum_{i=0}^{d} \left( \epsilon_i \cdot \frac{\pi}{(f+i)} \right) + \frac{z'}{n'} \cdot \left( \pi \cdot n \right)\)


Wir definieren noch die Summe ( = eine ganze Zahl, da \(\pi\) durch die verwendeten Faktoren \((f+i)\) immer teilbar ist und \(n\) per Definition durch \(P\)):
\(\sigma = \frac{n}{P} \cdot \sum_{i=0}^{d} \left( \epsilon_i \cdot \frac{\pi}{(f+i)} \right) \in \IN\)
[dies entspricht Fsum im Programm]

\(\sigma\) lässt sich nur von beiden Seiten der Gleichung abziehen:
\(\pi \cdot z - \sigma = \frac{z'}{n'} \cdot \left( \pi \cdot n \right)\)


Die rechte Seite ist hierbei durch \(P\) teilbar, da dies ein Teiler von \(n\) ist, aber \(n'\) diesen nicht mehr als Teiler besitzen soll. Wir suchen also ein passendes \(d\) samt \(\epsilon_i\), so dass auch die linke Seite durch \(P\) teilbar ist. Da jeder Bruch \(q\) eine Zerlegung in Stammbrüche besitzt, muss es ein solches minimales \(d\) samt \(\epsilon_i\) geben (siehe auch den nachfolgenden Abschnitt).
[Im Programm wird nacheinander Fdif = d erhöht und immer alle ungeraden (Binär)Zahlen, die die entsprechenden Kombinationen der Epsilon entsprechen, überprüft, bis ein entsprechendes Fdif und i (komb) gefunden wurde, und der Erfolg mit check verzeichnet wurde]

Man kann sogar zeigen, dass es immer für ein \(d < P\) eine Lösung mit entsprechenden \(\epsilon_i\) gibt. Sei \(\epsilon_{i<d} = 0\), so ergibt sich:
\(\frac{z}{n} = \frac{1}{(f + d) \cdot P} + \frac{z'}{n'}\\
\to (f + d) \cdot z = \frac{n}{P} + \frac{z'}{n'} \cdot (f + d) \cdot n\)
Wir suchen also ein \(d\), so dass:
\(d \cdot z \equiv \frac{n}{P} - f \cdot z \mod P\)
\(z\) und \(P\) sind dabei per Definition teilerfremd (da \(q\) ein vollständig gekürzter Bruch war). Somit wird jeder mögliche Rest modulo \(P\) für \(0 \leq d < P\) genau einmal erreicht, so dass für ein \(d < P\) gilt: \(d \cdot z \equiv \frac{n}{P} - f \cdot z \mod P\).
Damit ist gezeigt, dass dieses Verfahren immer mindestens eine Lösung für \(d < P\) besitzt. Für andere Verteilungen der \(\epsilon_i\) ergeben sich mitunter kleinere \(d\).


Hat man also ein entsprechendes, minimales \(d\) samt passender \(\epsilon_i\) gefunden, so gilt:
\(\pi \cdot z - \sigma \equiv 0 \mod P\)
bzw.
\(\frac{\pi \cdot z - \sigma}{P} = \frac{z'}{n'} \cdot \left( \pi \cdot \frac{n}{P} \right) \in \IN\)


Nun können wir die neuen Zähler und Nenner definieren:
\(g = \gcd \left(\frac{\pi \cdot z - \sigma}{P} , \pi \cdot \frac{n}{P} \right)\\
z' = \frac{\pi \cdot z - \sigma}{g \cdot P}\\
n' = \pi \cdot \frac{n}{g \cdot P}\)
[dies entspricht Zn und Nn im Programm, inkl. dem nachfolgenden Kürzen]



Hierbei habe ich noch 2 Fragen. Kann man zeigen, dass dann auch wirklich immer gilt: \(P \nmid n'\)? \(P\) war per Definition die \(a\)-te Potenz einer Primzahl \(p\), welche \(n\) genau \(a\)-mal teilt:
\(P = p^a\)
Demnach ist \(p \nmid \frac{n}{P}\).
Aber dann stört ja noch das \(\pi\)... Kann man vielleicht zeigen, dass \(f+i\) nie ein Vielfaches von \(p\) ist? (vermute, dass dies gelten müsste, und dann wäre auch \(p \nmid \pi\)).

Die zweite Frage betrifft \(z'\) - dies muss ja auch positiv sein. Kann man sicherstellen, dass es immer mindestens eine positive Lösung geben wird (also eine Lösung, so dass \(\pi \cdot z > \sigma\)). Wenn ich das richtig sehe, müsste dass auch schon für den Beweis, dass es ein \(d < P\) geben muss, gelten?

Wenn man die beiden Fragen so zeigen kann (muss ich mir wohl noch mehr überlegen, oder jemand schaut mal drüber), dann kann man damit einen Bruch \(q\) sukzessive in Stammbrüche umwandeln, indem man auf \(q' = \frac{z'}{n'}\) wieder dieses Verfahren anwendet, usw. usf. Da die Primteiler des Nenners dabei immer mehr reduziert werden und \(q < 1\) ist, muss das Verfahren irgendwann selbst zu einen Stammbruch \(\frac{1}{N}\) als Restbruch führen, welcher im nächsten Schritt selbst abgezogen wird.

Hier noch mein bisheriges Programm... wobei ich in sowas aufschreiben nicht gut bin (und man das sicherlich noch verbessern kann):
JavaScript
<html><body onload="start()"><script>
function start () {
//Bruch Z/N
var Z = 1
var N = 26
 
//Kürzen von Z/N
var Zt = Z
var Nt = N
while (Zt != Nt) {
  if (Nt > Zt) {Nt -= Zt}
  if (Zt > Nt) {Zt -= Nt}
}
Z /= Zt
N /= Nt
 
//Primteilerzerlegung von N als Array P
var n = N
var p = 2
var P = []
var i = 0
while (n > 1) {
  if (n%p == 0) {
    P[i] = p; n /= p
    while (n%p == 0) {P[i] *= p; n /= p}
    i++
  }
  else {p++}
}
 
//maximale Primteilerpotenz Pmax
var Pmax = 1
for (i = 0; i < P.length; i++) {
  if (Pmax < P[i]) {Pmax = P[i]}
}
 
//kleinste Vielfache von Pmax
var Fmin = Math.ceil(N/(Z*Pmax))
 
//Anzahl nötiger Stambrüche minimieren
var Fdif = 0
var Fmax = 0
var Fprod = 0
var Fsum = 0
var check = 0
var Zn = 0
var Znt = 0
var Nn = 0
var Nnt = 0
 
while (check == 0) {
  //maximaler Faktor merken
  Fmax = Fmin + Fdif
 
  //Alle ungeraden, binär Zahlen von 1 bis 1...1 (fdif+1 Stellen) - dies entspricht einer Kombination aus fmin bis fmax Fakoren
  for (i = 1; i < Math.pow(2,Fdif+1); i += 2) {
    //Die aktuelle Kombination (Binärzahl) merken... die letzte Stelle (1) nimmt sicher fmax dazu
    var komb = i
 
    //Array mit den Faktoren / der Kombination erstellen
    var Fkomb = []
    var j = Fmax
    while (komb > 0) {
      if (komb%2 == 0) {j--; komb /= 2}
      else {Fkomb.push(j); j--; komb--; komb /= 2}
    }
 
    //Produkt der Faktoren
    Fprod = 1
    for (j = 0; j < Fkomb.length; j++) {
      Fprod *= Fkomb[j]
    }
 
    //Summe der Quotienten Produkt/Faktor
    Fsum = 0
    for (j = 0; j < Fkomb.length; j++) {
      Fsum += Fprod/Fkomb[j]
    }
    //Summe mit N/Pmax erweitern
    Fsum *= N/Pmax
 
    //möglichen neuen Zähler definieren
    Zn = (Z*Fprod - Fsum)/Pmax
 
    //Zn muss natürlich sein = der neue Zähler lies sich durch Pmax kürzen
    if (Zn%1 == 0 && Zn >= 0) {
      //entsprechenden neuen Nenner definieren
      Nn = Fprod*N/Pmax
 
      //Kürzen von Zn/Nn - falls noch rein Rest bleibt
      if (Zn > 0) {
        Znt = Zn
        Nnt = Nn
        while (Znt != Nnt) {
          if (Nnt > Znt) {Nnt -= Znt}
          if (Znt > Nnt) {Znt -= Nnt}
        }
        Zn /= Znt
        Nn /= Nnt
      }
 
      //Zerlegung notieren
      document.write(Z+"/"+N+" = ")
      for (j = 0; j < Fkomb.length; j++) {
        document.write("1/"+Fkomb[j]+"*"+Pmax+" + ")
      }
      document.write(Zn+"/"+Nn+"<br>")
 
      //Erfolg notieren
      check = 1
    }
  }
  //wenn alle Kombinationen durchgegangen, fdif erhöhen
  Fdif ++
}}
</script></body></html>


Vielleicht mag jemand mit über die Methode schauen, und mit zeigen, ob / dass diese auch immer so funktioniert (meine beiden Fragen am Ende). Oder vielleicht gibt es das Verfahren ja in der Weise schon...
Aber bisher kann ich damit gut Brüche in Stammbrüche zerlegen ^^


querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 327
Aus:
Beitrag No.1, eingetragen 2019-12-09 20:48

Hallo Martin,

wenn ich es recht verstehe möchtest du mit diesem Algorithmus eine Zerlegung mit möglichst kleinen Nennern finden? (meist sucht man ja eine Zerlegung mit möglichst wenigen Stammbrüchen).

Welche Zerlegung erhältst du mit deinem Verfahren für 2/115 ?


Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 1199
Aus: Deutschland
Beitrag No.2, eingetragen 2019-12-10 01:26

Hallo MartinN,

ich habe Dein Programm mal in Mathematica-Syntax umgesetzt und erste Tests laufen lassen. Für eine Vielzahl von Fällen scheint Dein Algorithmus zu passen. Es scheint darunter aber auch Fälle zu geben, bei denen mindestens eine der While-Schleifen zur Endlosschleife wird.

Das scheint z. B. bei folgenden Brüchen der Fall zu sein:
7/82384
554/35433
2450/90250

LG Primentus


Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 1199
Aus: Deutschland
Beitrag No.3, eingetragen 2019-12-10 16:16

Hallo MartinN,

ich muss mich insofern korrigieren, dass die drei Brüche, die ich in Beitrag #2 genannt habe, wohl doch keine Endlosschleife erzeugen, sondern die Berechnung dauert dort lediglich sehr lange, weil jeweils einer der Stammbrüche einen Nenner größer als $10^{16}$ hat.

Aber ich teste mal noch weiter.

Manchmal ermittelt das Programm Summen, die nicht ausschließlich aus Stammbrüchen entstehen, aber wenn ich Dich richtig verstanden habe, soll ein solcher Summand dann nochmals mit Hilfe Deines Algorithmus zerlegt werden, sozusagen so lange, bis irgendwann nur noch Stammbrüche als Summanden erzeugt werden. (Edit: Ich hatte noch einen Fehler bei der Ermittlung von Pmax im Programm.)

LG Primentus

Edit:
Beim Bruch 10/867 rödelt sich der Algorithmus zu Tode, obwohl eigentlich 1/87 + 1/25143 herauskommen müsste. Der Bruch 10/867 wird korrekt in eine Stammbruchsumme zerlegt.


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Beitrag No.4, vom Themenstarter, eingetragen 2019-12-10 21:53

Ich hab selbst schon festgestellt, dass er bei 3/4 kein 1/4 + Restbruch daraus macht. Wenn ich Zeit habe, muss ich mal den Fehler suchen... Dann kann ich auch eure Werte mal eingeben. (oder andere Beispiele wie 5/16 sollten zu 1/16 + x führen oder hatte noch paar andere gefunden)

Edit: also zumindest bei mir muss da noch iwo ein fehler sein. Ihr habt das vielleicht besser programmiert xD


Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 1199
Aus: Deutschland
Beitrag No.5, eingetragen 2019-12-10 23:29

Hallo MartinN,

habe doch noch Fälle festgestellt, bei denen in der Stammbruchzerlegung noch ein Nicht-Stammbruch vorkommt. Die Brüche 697/674 und 1325/8342 sind hierbei sehr interessant. Da gibt das Programm jeweils mehrere Stammbruchzerlegungen aus, aber der letzte Bruch hat stets einen Zähler ungleich Eins. Man kann dann höchstens für diesen einen Bruch den Algorithmus erneut aufrufen, dann hat man möglicherweise irgendwann eine komplette Stammbruchzerlegung, sofern die weiteren Nenner nicht zu groß werden.

Ich habe jedenfalls Dein Programm ziemlich exakt nachprogrammiert, nur die beiden Passagen, wo die Primteilerzerlegung und Pmax ermittelt werden, hab ich leicht abweichend programmiert, weil es dafür eine praktische Standardfunktion in Mathematica gibt.

LG Primentus


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Beitrag No.6, vom Themenstarter, eingetragen 2019-12-12 16:17

Also meinen Fehler hab ich jetzt gefunden, ich hab z' falsch definiert, es genügt, wenn z' durch pmax teilbar ist (es muss nicht durch Pmax teilbar sein). pmax ist dabei die Basis des maximalen Primzeilers Pmax.
JavaScript
//maximale Primteilerpotenz Pmax mit Primuzahl pmax
var Pmax = 1
var pmax = 1
for (i = 0; i < P.length; i++) {
  if (Pmax < Math.pow(P[i],A[i])) {
    pmax = P[i]
    Pmax = Math.pow(P[i],A[i])
  }
}

Später definiere ich dann zuerst die neuen Zähler und Nenner, nun soll der Zähler positiv sein und mindestens einmal durch die Primzahl pmax teilbar sein (Erklärung weiter unten); dann Kürzen und schauen, dass der neue Nenner nun wirklich nicht mehr durch Pmax teilbar ist, durch pmax^i < Pmax darf er noch teilbar sein (das hatte ich im alten Programm ausgeschlossen, aber hatte ich eugentlich nicht gefordert in meiner Methode)
JavaScript
    //möglichen neuen Zähler und Nenner definieren
    Zn = Z*Fprod - Fsum
    Nn = Fprod*N
 
    //Zn sei positiv und mindestens einmal durch pmax teilbar
    if (Zn >= 0 && Zn%pmax == 0) {
      Zn /= pmax
      Nn /= pmax
 
      //Kürzen von Zn/Nn - falls häufiger durch pmax und anderes teilbar
      if (Zn > 0) {
        Znt = Zn
        Nnt = Nn
        while (Znt != Nnt) {
          if (Nnt > Znt) {Nnt -= Znt}
          if (Znt > Nnt) {Znt -= Nnt}
        }
        Zn /= Znt
        Nn /= Nnt
      }
 
      //Nun soll der Nenner zumindest nicht mehr durch Pmax teilbar sein
      if (Nn%Pmax != 0) {
        //Zerlegung notieren
        document.write(Z+"/"+N+" = ")
        for (j = 0; j < Fkomb.length; j++) {
          document.write("1/"+Fkomb[j]+"*"+Pmax+" + ")
        }
        document.write(Zn+"/"+Nn+"<br>")
 
        //Erfolg notieren
        check = 1
      }
    }


Der Fehler tritt im Startpost bei mir hier auf:
\(\pi \cdot z - \sigma = \frac{z'}{n'} \cdot \left( \pi \cdot n \right)\)
Die rechte Seite ist tatsächlich durch \(P\) (Pmax) teilbar, aber nur wenn \(n'\) weder durch \(P\) noch durch keine kleinere Potenz der zugrundeliegenden Primzahl teilbar ist.
Die linke Seite muss also nur durch die zugrundeliegende Primzahl (\(p\) = pmax) teilbar sein, und man definiert:
\(g = \gcd \left(\frac{\pi \cdot z - \sigma}{p} , \pi \frac{n}{p} \right)\\
z' = \frac{\pi \cdot z - \sigma}{g \cdot p}\\
n' = \pi \cdot \frac{n}{g \cdot p}\\
P \nmid n'\)
Das letzte ist eine zusätzliche Bedingung, die erfüllt sein soll.


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Beitrag No.7, vom Themenstarter, eingetragen 2019-12-12 17:14

2019-12-09 20:48 - querin in Beitrag No. 1 schreibt:
Hallo Martin,

wenn ich es recht verstehe möchtest du mit diesem Algorithmus eine Zerlegung mit möglichst kleinen Nennern finden? (meist sucht man ja eine Zerlegung mit möglichst wenigen Stammbrüchen).

Welche Zerlegung erhältst du mit deinem Verfahren für 2/115 ?

Ja, ich mag möglichst kleine Nenner xD

2/115 = 1/9*23 + 1/7*23 + 2/315
[wobei man 2/315 weiter zerlegen muss]
2/315 = 1/19*9 + 1/1995

Günstiger wäre da 5 als Primzahl (Pmax und pmax) zu wählen:
2/115 = 1/14*5 + 1/322
...hieran sieht man sicherlich, dass Pmax und pmax nicht die beste Wahl sind und mann muss vielleicht alle Primzahlen versuchen.

Auch für 2/315 (aus der ersten Zerlegung mit dem eigentlichen Pmax) war deren nachfolgende Zerlegung nicht die beste:
2/315 = 1/19*9 + 1/1995
2/315 = 1/34*5 + 1/2142
2/315 = 1/26*7 + 1/1170
[wenn man alle p(i)^a(i) durchgeht]


2019-12-10 01:26 - Primentus in Beitrag No. 2 schreibt:
Hallo MartinN,

ich habe Dein Programm mal in Mathematica-Syntax umgesetzt und erste Tests laufen lassen. Für eine Vielzahl von Fällen scheint Dein Algorithmus zu passen. Es scheint darunter aber auch Fälle zu geben, bei denen mindestens eine der While-Schleifen zur Endlosschleife wird.

Das scheint z. B. bei folgenden Brüchen der Fall zu sein:
7/82384
554/35433
2450/90250

LG Primentus
Bei 7/82384 rechnet es ewig :S [vermutlich die nötigen Faktoren (f+d) für Pmax zu groß und es geht dann ja alle Möglichkeiten durch]- aber, dass es immer eine Möglichkeit geben muss, hab ich ja schon im ersten Post gezeigt.


554/35433 liefert (wenn ich alle Primteilerpotenzen durchgehe):
554/35433 = 1/8*9 + 55/31496
554/35433 = 1/9*31 + 1/5*31 + 32/5715
554/35433 = 1/6*127 + 1/4*127 + 1/1*127 + 5/1116
(127 wäre dabei jene Variante mit Pmax)

5/1116 weiter zerlegt ergibt (wieder über alle Primteilerpotenzen):
5/1116 = 1/57*4 + 1/10602
5/1116 = 1/26*9 + 1/4836
5/1116 = 1/18*31 + 1/12*31 + 0/7776

Somit komme ich insgesamt auf:
554/35433 = 1/6*127 + 1/4*127 + 1/1*127 + 1/18*31 + 1/12*31

Hier fällt mir auf, dass es bei 5/1116 nicht die Zerlegung (mit p = 4) findet:
5/1116 = 1/279*4 + 1/1116
[weil es vorher schon bei 57 eine Zerlegung findet, so dass n' nicht durch Pmax teilbar wäre; und 1116 in dieser Variante wieder durch Pmax teilbar wäre [wobei das nicht so schlimm wäre, da es schon ein Stammbruch ist]]
Muss ich mir mal überlegen, in wie weit mich das stört / verbessern kann.


2450/90250 kürzt es erstmal und findet dann:
49/1805 = 1/9*5 + 16/3249
49/1805 = 1/4*361 + 1/1*361 + 9/380
Pmax wäre hier die Zeile mit 361

9/380 = 1/11*4 + 1/1045
9/380 = 1/9*5 + 1/684
9/380 = 1/5*19 + 1/4*19 + 0/400
Pmax wäre hier die Zeile mit 19 [ich geh gerade immer alle Primzahlen durch in der aktuellen Version xD]

insgesamt: 49/1805 = 1/4*361 + 1/1*361 + 1/5*19 + 1/4*19

Aber auch hier muss die Wahl von Pmax nicht die beste sein, da:
16/3249 = 1/25*9 + 13/27075
16/3249 = 1/4*361 + 1/1*361 + 1/684

Dies liefert mindestens diese bessere Zerlegung:
49/1805 = 1/9*5 + 1/4*361 + 1/1*361 + 1/684


Ja, bisher gibt zumindest mein Programm eine mögliche Zerlegung des Bruchs aus und einen Rest-Bruch, den man wieder zerlegen müsste. Das mag ich dann noch abändern, dass es den automatisch weiter zerlegt... aber wie beim Beispiel von querin genügt es wohl nicht, nur Pmax zu betrachten.


Ich finde bei 10/867 btw:
10/867 = 1/31*3 + 7/8959
10/867 = 1/2*289 + 1/102
(das mit 289 ist wieder die Pmax-Zeile)


697/674 hat erstmal die Eigenschaft > 1 zu sein xD
Über alle Primteilerpotenzen:
697/674 = 1/1*2 + 180/337
697/674 = 1/10*337 + 1/6*337 + 31/30
697/674 = 1/10*337 + 1/9*337 + 1/8*337 + 1/6*337 + 1/5*337 + 1/2*337 + 371/360
697/674 = 1/10*337 + 1/9*337 + 1/7*337 + 1/6*337 + 1/4*337 + 1/3*337 + 1/2*337 + 1297/1260
697/674 = 1/10*337 + 1/9*337 + 1/7*337 + 1/4*337 + 1/1*337 + 1297/1260
Hierbei gibt es mit 337 mehrere Pmax-Varianten (später würde ich wohl automatisch jene wählen lassen, deren Nenner-Summe am kleinsten ist).

Ich würde jetzt 697/674 = 1/10*337 + 1/6*337 + 31/30 daher hierbei wählen, aus dem Rest-Bruch macht es aber:
31/30 = 1/1*2 + 8/15
31/30 = 1/1*3 + 7/10
31/30 = 1/1*5 + 5/6 [Pmax-Variante]
[1/6*5 + 1/1 macht es nicht, da es vorher schon Varianten findet, so dass der Nenner des Rest-Bruchs nicht durch 5 teilbar ist]

5/6 = 1/1*2 + 1/3
5/6 = 1/1*3 + 1/2 [Pmax-Variante]

Hierbei sieht man auch:
31/30 = 1/1*5 + 1/1*3 + 1/2 kommt mit Nennern auf, die kleiner als 30 sind, auch wenn 1/30 + 1/1 die naheliegendere Variante wäre.

Insgesamt: 697/674 = 1/10*337 + 1/6*337 + 1/1*5 + 1/1*3 + 1/2


1325/8342:
1325/8342 = 1/5*2 + 1227/20855
1325/8342 = 1/5*43 + 1/1*43 + 127/970
1325/8342 = 1/8*97 + 1/5*97 + 1/4*97 + 263/1720
1325/8342 = 1/8*97 + 1/7*97 + 1/6*97 + 1/3*97 + 1/2*97 + 351/2408
1325/8342 = 1/8*97 + 1/7*97 + 1/1*97 + 351/2408 [diese Pmax-Variante gewählt]

351/2408 = 1/1*8 + 25/1204
351/2408 = 1/1*7 + 1/344 [diese evtl. günstiger, da geringere Nennersumme]
351/2408 = 1/5*43 + 1/1*43 + 33/280 [diese weiter betrachtet]

33/280 = 1/3*8 + 8/105
33/280 = 1/2*5 + 1/56 [kleinere Nennersumme]
33/280 = 1/5*7 + 1/3*7 + 1/24 [Pmax-Variante]

Man sieht hierbei, dass man mit Pmax zwar (zumindest in dem Bsp) die kleineren Nenner findet, aber die Summe der Nenner nicht unbedingt am kleinste sein muss.


Soviel erstmal zu euren Beispielen, aber ja... man muss sicherlich öfters Zerlegen, ehe man nur zu Stammbrüchen kommt. War auch nie anders geplant:
"indem man auf \(q' = \frac{z'}{n'}\) wieder dieses Verfahren anwendet, usw. usf."


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Beitrag No.8, vom Themenstarter, eingetragen 2019-12-12 17:28

Noch zu 7/82384, wo es ewig rechnet... nehme ich erstmal den Bruch*16, so findet es:
7/5149 = 1/55*19 + 6/14905
7/5149 = 1/13*271 + 1/12*271 + 1/7*271 + 5/20748

Bzw beide Seiten /16:
7/82384 = 1/55*19*16 + 6/14905*16
7/82384 = 1/13*271*16 + 1/12*271*16 + 1/7*271*16 + 5/20748*16 [Pmax-Variante]

Zumindest dies wären erste mögliche Zerlegungen, wobei es auch mit kleineren Nennern eine geben könnte, aber dafür rechnet es sich tot :S

5/20748 = 1/1039*4 + 2/5389293
5/20748 = 1/1385*3 + 3/9578660
5/20748 = 1/597*7 + 1/589836
5/20748 = 1/327*13 + 1/173964
5/20748 = 1/226*19 + 1/123396 [Pmax-Variante]
[die könnte man wieder durch 16 teilen und erhält schon eine Zerlegung]

Somit wäre eine mögliche Zerlegung (die es finden müsste):
7/82384 = 1/16 * [1/13*271 + 1/12*271 + 1/7*271 + 1/226*19 + 1/123396]


querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 327
Aus:
Beitrag No.9, eingetragen 2019-12-12 17:53

2019-12-12 17:14 - MartinN in Beitrag No. 7 schreibt:
Ja, ich mag möglichst kleine Nenner xD
...
Auch für 2/315 (aus der ersten Zerlegung mit dem eigentlichen Pmax) war deren nachfolgende Zerlegung nicht die beste:
2/315 = 1/19*9 + 1/1995
2/315 = 1/34*5 + 1/2142
2/315 = 1/26*7 + 1/1170
[wenn man alle p(i)^a(i) durchgeht]

Beachte die Zerlegungen
2/315 = 1/280 + 1/360
7/82384 = 1/82384 + 1/41192 + 1/20596


pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 1647
Aus: Thüringen
Beitrag No.10, eingetragen 2019-12-12 18:39

Vermutung zum ewigen Rechnen..

Bedenkt, dass durchaus der erforderliche Zahlenbereich die 64bit-Genauigkeit verlässt.


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1203
Aus: Bayern
Beitrag No.11, vom Themenstarter, eingetragen 2019-12-12 18:52

2019-12-12 17:53 - querin in Beitrag No. 9 schreibt:
2019-12-12 17:14 - MartinN in Beitrag No. 7 schreibt:
Ja, ich mag möglichst kleine Nenner xD
...
Auch für 2/315 (aus der ersten Zerlegung mit dem eigentlichen Pmax) war deren nachfolgende Zerlegung nicht die beste:
2/315 = 1/19*9 + 1/1995
2/315 = 1/34*5 + 1/2142
2/315 = 1/26*7 + 1/1170
[wenn man alle p(i)^a(i) durchgeht]

Beachte die Zerlegungen
2/315 = 1/280 + 1/360
7/82384 = 1/82384 + 1/41192 + 1/20596
Zumindest das Bsp mit 2/315 zeigt mir, dass es wohl deutlich bessere Methoden gibt / geben muss, um auf kleine Nenner zu kommen... da der Rest-Bruch wie 1/1995 usw. deutlich größere Nenner haben kann, als es insgesamt notwendig wäre.

- und 7/82384 ist so ein klassisches Bsp, was man im Kopf wohl leichter zerteilt bekommt, wenn man 7 = 1+2+4 sieht - aber wenn man mal die komische 271 raushaut:
7/304 = 1/5*19 + 1/80
Damit kommt man auf eine Zerlegung mit maximalen Nenner: 5*19*271 = 25745




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244756=90
Druckdatum: 2020-10-31 22:18