20 Lösung / Solution

[WolfgangR]

[...]

Abschätzung nach unten (alle Summanden werden 5 mal addiert): K(2^n)<5*(K(2^(n-2)+1)+...+K(2^(n-1)))<5*2^(n-2)*K(2^(n-1))<...<5*2^((n-2)+(n-3)+...+0)*K(2)=15*2^((n-1)*(n-2)/2)
Also folgt: C<15*2^(54*53/2)<2^1435<10^432

Somit Antwort Nr. 5

Die andere Richtung kann ich nachvollziehen, aber was passiert hier bei den "<...<"? Wenn ich die Abschätzung K(2^n) < 5*2^(n-2)*K(2^(n-1)) wiederholt anwende, müsste dann nicht jedes mal auch noch ein Faktor 5 dazukommen?

Stimmt, habe ich übersehen. Es kommt noch ein Faktor 5^53 zu meiner Grenze dazu, dann haben wir insgesamt C<10^470.

[hg1]

Ich habe versucht die Wachstumsrate der Folge zu untersuchen. Die exakte Zahl c(n) der Schafe erfüllt

c(x) - c(x-1) = 2 c(x/2)    (x/2 aufgerundet)

Die Folge
- wächst schneller als ein Polynom x^k  (denn da wäre die linke Seite von der Ordnung O(x^(k-1)) < die rechte Seite O(x^k))
- wächst langsamer als exponentiell b^x (denn da wäre die linke Seite O(b^x) > die rechte Seite O(b^(x/2)))

Also irgendetwas zwischen polynomiell und exponentiell.

Mein Ansatz: Wenn die asymptotische Wachstumsrate durch eine (stetige, glatte) Funktion f beschrieben werden kann, dann sollte sie (wegen der obigen Gleichung für c) die Differentialgleichung

f'(x) = 2 f(x/2)

erfüllen. Das ist keine gewöhnliche Differentialgleichung wegen der unterschiedlichen Argumente x und x/2, aber bei vorgegebem Anfangswert z.B. f(0) = 1 sollte sie trotzdem eine eindeutige Lösung haben.
Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)

Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.
Hier ist eine Tabelle:

Code:

k       f(k)/1.255    c(k)
       (approx.)     (exakt)
-----------------------------
2^1     10^0.923      10^0.477
2^2     10^1.488      10^1.176
2^3     10^2.240      10^2.045
2^4     10^3.197      10^3.085
2^5     10^4.372      10^4.310
2^6     10^5.776      10^5.742
2^7     10^7.417      10^7.398
2^8     10^9.302      10^9.291
2^9     10^11.436     10^11.430
2^10    10^13.825     10^13.821
2^11    10^16.472     10^16.470
2^12    10^19.382     10^19.380
2^13    10^22.555     10^22.555
2^14    10^25.996     10^25.996
2^15    10^29.706     10^29.706
2^16    10^33.687     10^33.687
2^17    10^37.942     10^37.942
2^18    10^42.471     10^42.471
2^19    10^47.276     10^47.276
2^20    10^52.359     10^52.359
2^21    10^57.720     10^57.720
2^22    10^63.360     10^63.360
2^23    10^69.281     10^69.281
2^24    10^75.483     10^75.483
2^25    10^81.967     10^81.967
2^26    10^88.734     10^88.734
2^27    10^95.785     10^95.785
2^28    10^103.119    10^103.119
2^29    10^110.739   
2^30    10^118.644   
2^31    10^126.834   
2^32    10^135.312   
2^33    10^144.075   
2^34    10^153.127   
2^35    10^162.465   
2^36    10^172.092   
2^37    10^182.007   
2^38    10^192.211   
2^39    10^202.704    10^202.704073 (von Georg J. aus D.)
2^40    10^213.486   
2^41    10^224.558   
2^42    10^235.920   
2^43    10^247.573   
2^44    10^259.515   
2^45    10^271.748   
2^46    10^284.273    10^284.272647 (von Georg J. aus D.)
2^47    10^297.088   
2^48    10^310.195   
2^49    10^323.593   
2^50    10^337.283   
2^51    10^351.265   
2^52    10^365.540   
2^53    10^380.106   
2^54    10^394.965   
2025^5  10^408.970   
2^55    10^410.117   
2^56    10^425.561   
2^57    10^441.299   
2^58    10^457.329   
2^59    10^473.653   
2^60    10^490.270   

Aufgrund der guten Übereinstimmung mit den exakt berechneten Werten an 2er-Ptenzen gehe ich daher davon aus, dass 

Code:

C ≈ 10^408.970

[Georg J. aus D.]

Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)

Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.

Ich kann leider deine Tabellenwerte nicht nachvollziehen.

f(2^4)/1,255 = 2^(1/2 * 4^2)/1,255 = 2^8/1,255 = 256/1,255 = 203,984... = 10^2,309... und nicht 10^3,197...

Wo steckt der Fehler?

[hg1]

Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)

Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.

Ich kann leider deine Tabellenwerte nicht nachvollziehen.

f(2^4)/1,255 = 2^(1/2 * 4^2)/1,255 = 2^8/1,255 = 256/1,255 = 203,984... = 10^2,309... und nicht 10^3,197...

Wo steckt der Fehler?

Ah, da habe ich mich wohl etwas missverständlich ausgedrückt. Die Funktion f, die ich in der Tabelle ausgewertet habe, ist die tatsächliche Lösung der Differentialgleichung, für die ich ja wie gesagt keine geschlossene Formel habe.

Aber zumindest lässt sich eine Darstellung als unendliche Potenzreihe finden:

Da habe ich als Ansatz eine Potenzreihe f(x) = sum_{k>=0} a_k x^k genommen, und durch Ausrechnen von f'(x) und 2f(x/2) und anschließendem Koeffizientenvergleich folgt
a_0 = 1
a_1 = 2
a_{k+1}/a_k = 1/((k+1)*2^(k-1))    für alle k >= 1

explizit ausgedrückt: a_k = 1/(k! 2^(k(k-3)/2))


Wegen des Faktors 2^(k^2 / 2) wächst der Nenner extrem schnell, sodass die Summandenterme selbst für "große" x sehr schnell sehr klein werden (selbst für x = 2025^5 genügen etwas über 100 Terme vollkommen). Daher ist die numerische Berechnung von f gar kein Problem.

[Georg J. aus D.]

Danke. Jetzt kann ich die Werte nachvollziehen.