Welchen Wert hat die Funktion F( n, m )?

Question

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?

Aeroleo · Accepted Answer

F(0,0) = 1

F(1,0) = F(0,1) =2 
F(1,m)=F(0,F(1,m-1))= F(1,m-1)+1
mit F(1,0)=2 haben wir F(1,m)=m+2

F(2,0) = F(1,1)=3
F(2,m)=F(1,F(2,m-1))= F(2,m-1)+2
mit F(2,0)=3 haben wir F(2,m)=2m+3

F(3,0) = F(2,1) = 5
F(3,m)=F(2,F(3,m-1))= 2F(3,m-1)+3
mit F(3,0)=5 haben wir F(3,m)=2^(3+m)-3 
 denn: 2^(3+(m+1))-3=2*[2^(3+m)-3]+3

F(4,m)=F(3,F(4,m-1))= 2^(3+F(4,m-1))-3
F(4,0)=F(3,1)=13
F(4,1)=2^16-3
F(4,2)=2^(2^16)-3
F(4,3)=2^(2^(2^16))-3
F(4,4)=2^(2^(2^(2^16)))-3

F(5,5) dürfte dann wohl ziemlich groß werden :)

@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.

Michael · Answer

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
-------------------


@Aeolio:
Woher kommst Du auf die Vereinfachung?

Wurzelgnom · Answer

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.

Bis später

Welchen Wert hat die Funktion F( n, m )?

3 Antworten