Also, hier erstmal eine recht einfache Funktionsdefinition F( n, m ) für natürliche Zahlen n und m:
F( 0, m ) = m + 1 F( n, 0 ) = F( n - 1, 1) F( n, m ) = F( n - 1, F( n, m - 1 ) )
Welchen Wert hat F( 4, 4 )? Und für Rechenfreunde: Welchen Wert hat F( 5, 5 )?
Genaue Antworten, bitte.
Peace, LXP
Verstöße: 33 (Anarchist in Ausbildung)
P.S.: Wer die Antworten schon kennt, bitte nicht verraten - wir wollen den Mathefreunden ja nicht den Spaß verderben, oder?
2009-08-31T04:36:14Z
Das kleine, unscheinbare Funktiönchen hat es faustdick hinter den Ohren. Und dabei handelt es sich um Titanenfäuste.
Bereits der Wert von F( 4, 2 ) hat als Dezimalzahl 19729 Stellen.
F( 4, 4 ) ist größer als 10^10^10^19000. Zum Vergleich: die geschätzte, größte Zahl, die real vorkommen kann, ist wohl die Anzahl der Elementarteilchen im gesamten Universum, und die liegt bei vergleichsweise läppischen 10^70.
F( 5, m ) ist allgemein mit normaler mathematischer Notation nicht mal mehr darstellbar.
Natürlich handelt es sich um nichts Anderes als die stark vereinfachte Version der "prominenten" Ackermann-Funktion.
@Michael: Beweis per vollständige Induktion ( http://de.wikipedia.org/wiki/Induktionsbeweis ). Wenn f(0) gilt, und die Relation aus f(n-1) folgt f(n), dann gilt f(m) für alle m>=0. Also bei F(1,0)=2, und F(1,m)=F(1,m-1)+1 prüfe ich die Hypothese F(1,m)=m+2: F(1,0)=0+2=2 : Stimmt! F(1,m)=F(1,m-1)+1 (nun die Induktionsannahme:) = ((m-1)+2)+1 = m+2. Aussage bewiesen. Bei F(3,m) steht der Induktionsschritt schon da: 2^(3+(m+1))-3=2*[2^(3+m)-3]+3, hier steht in den eckigen Klammern die F(3,m), darauf die Formel angewandt, und Du bist bei F(3,m+1), der linken Seite. F(2,m) kannst Du ja im Detail ausführen, alles wesentliche ist da :) Wenn Du wissen willst, wie ich auf die Hypothese gekommen bin, so habe ich einfach die Formel... angeschaut: F(1,*): 1 mehr. -> m+x. F(2,*): 2 mehr. ->2m+x. F(3,*): das doppelte plus etwas. -> 2^(m + x)+y Und um x bzw. x und y rauszubekommen habe ich F(*,0) (bzw ein paar mehr bei F(3,*) angeschaut.
F(4,2) wird übrigens die meisten Rechner an Ihre Grenzen bringen, wenn Du sie mit einem Programm ausrechnen willst, und F(4,4) ist weiiiiiit außerhalb der Numerik.
Dafür würde ich mir ein Programm schreiben mit eben den Abruchbedingungen n = 0 und m=0... mit F(n, m) hat man ja eine ziemlich nette Definition der Funktion.
Wenn ich es habe wird es gleich nachgeliefert.
Theoretisch läßt sich das ganze in eine (Java) funktion kapseln:
public static long f(long n, long m) { long retValue=0; if (n==0) { retValue=m+1; } else if (m==0) { retValue=f(n-1,1); } else { long a=f(n,m-1); retValue=f(n-1,a); } return retValue; }
Praktisch gibt es ziemlich viele Rekursionen, wodurch sich nur für kleine n und m ein Ergebnis darstellen läßt:
F(3,2)=29; F(3,3)=61; F(3,4)=125;
Weiter kommt man erst mal nicht - aber man sieht, es liefert Ergebnisse. Das Problem ist, dass für m>1 und n>1 ziemlich chaotische Werte herauskommen. Ich lege mich mal fest und sage, dass der Algorithmus einfach nicht stabil ist.
Ich bin mal fies und zeige mal ein Ergebnis ...4 mio. Rekursionen sind auch nicht von schlechten Eltern. maxm ist das maximal erreichte m bis zum Abbruch. maxn ist das maximal erreichte n bis zum Abbruch.
Ergebnis f(0, 0)=1 ------------------- Ergebnis f(0, 1)=2 Max m = 1 ------------------- Ergebnis f(0, 2)=3 Max m = 2 ------------------- Ergebnis f(0, 3)=4 Max m = 3 ------------------- Ergebnis f(0, 4)=5 Max m = 4 ------------------- Ergebnis f(0, 5)=6 Max m = 5 ------------------- Ergebnis f(1, 0)=2 Rekursionen = 1 Max m = 1 ------------------- Ergebnis f(1, 1)=3 Rekursionen = 2 Max m = 2 ------------------- Ergebnis f(1, 2)=4 Rekursionen = 3 Max m = 3 ------------------- Ergebnis f(1, 3)=5 Rekursionen = 4 Max m = 4 ------------------- Ergebnis f(1, 4)=6 Rekursionen = 5 Max m = 5 ------------------- Ergebnis f(1, 5)=7 Rekursionen = 6 Max m = 6 ------------------- Ergebnis f(2, 0)=3 Rekursionen = 3 Max m = 2 ------------------- Ergebnis f(2, 1)=5 Rekursionen = 8 Max m = 4 ------------------- Ergebnis f(2, 2)=7 Rekursionen = 15 Max m = 6 ------------------- Ergebnis f(2, 3)=9 Rekursionen = 24 Max m = 8 ------------------- Ergebnis f(2, 4)=11 Rekursionen = 35 Max m = 10 ------------------- Ergebnis f(2, 5)=13 Rekursionen = 48 Max m = 12 ------------------- Ergebnis f(3, 0)=5 Rekursionen = 9 Max m = 4 ------------------- Ergebnis f(3, 1)=13 Rekursionen = 58 Max m = 12 ------------------- Ergebnis f(3, 2)=29 Max m = 2 ------------------- Ergebnis f(3, 3)=61 Max m = 3 ------------------- Ergebnis f(3, 4)=125 Max m = 4 ------------------- Ergebnis f(3, 5)=253 Rekursionen = 16129 Max m = 252 ------------------- Ergebnis f(4, 0)=13 Rekursionen = 59 Max m = 12 ------------------- Stopped calc of f(4, 1) afer 4364815 recursions. Max m = 3447 ------------------- Stopped calc of f(4, 2) afer 4361368 recursions. Max m = 3445 ------------------- Stopped calc of f(4, 3) afer 4357923 recursions. Max m = 3443 ------------------- Stopped calc of f(4, 4) afer 4354480 recursions. Max m = 3441 ------------------- Stopped calc of f(4, 5) afer 4351039 recursions. Max m = 3439 ------------------- Stopped calc of f(5, 0) afer 4361368 recursions. Max m = 3445 ------------------- Stopped calc of f(5, 1) afer 4357923 recursions. Max m = 3443 ------------------- Stopped calc of f(5, 2) afer 4354480 recursions. Max m = 3441 ------------------- Stopped calc of f(5, 3) afer 4351039 recursions. Max m = 3439 ------------------- Stopped calc of f(5, 4) afer 4347600 recursions. Max m = 3437 -------------------
Das ist ja 'ne hübsche Funktion. Aber allzu weit bin ich noch nicht. Bisher weiß ich erst mal, dass F(0,0) = 1 F(0,1) = 2 F(1,0) = F(0,1) F(1,1) = F(0,F(1.0) ) = F(0,2) = 3
F(2,0) = F(1,1) = 3 und F(2,1) = F(1,2)
Ich weiß, das ist noch nicht viel, aber ich pirsche mich so langsam rekursiv ran und der Sonntag hat ja gerade mal erst angefangen.