20 Lösung / Solution

[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