22 Kasım 2018

Euler Projesi 255. Soru

Yuvarlanmış Kare Kökler

Bir n pozitif tam sayının yuvarlanmış kare kökünü, n'nin kare kökünün en yakın tam sayıya yuvarlanmış değeri olarak tanımlarız.

Aşağıdaki işlemle (özellikle tam sayı aritmetiğine uyarlanmış Heron yöntemi) n'nin yuvarlanmış kare kökü bulunur:

n sayısının basamak sayısı d olsun.
d tek ise $x_0=2\times 10^{\frac{(d-1)}{2}}$ olsun.
d çift ise $x_0=7\times 10^{\frac{(d-2)}{2}}$ olsun.
$x_{k+1}=x_k$ olana kadar $$x_{k+1}=\lfloor \frac{x_k+\lceil \frac{n}{x_k}\rceil}{2}\rfloor$$tekrarlayalım.

Örneğin n=4321 sayısının yuvarlanmış kare kökünü bulalım.
n sayısının 4 basamağı var, yani $x_0=7\times 10^{\frac{(4-2)}{2}}=70$ olur. $$x_{1}=\lfloor \frac{70+\lceil \frac{4321}{70}\rceil}{2}\rfloor=66$$ $$x_{2}=\lfloor \frac{66+\lceil \frac{4321}{66}\rceil}{2}\rfloor =66$$
$x_2=x_1$ olduğundan burada dururuz.
Böylece sadece iki iterasyon ile 4321 sayısının yuvarlanmış karekökünün 66 olduğunu bulduk (gerçek kare kökü ise 65,7343137...).

Bu yöntemde gereken iterasyon sayısı şaşırtıcı derecede azdır.
Örneğin 5 basamaklı bir tam sayının ($10.000\le n\le 99.999$) yuvarlanmış kare kökünü yaklaşık 3,2102888889 (10 ondalık basamağa yuvarlanmış yaklaşık değer) iterasyonda bulabiliriz.

Yukarıda tanımlanan işlemle 14 basamaklı bir sayının ($10^{13}\le n< 10^{14}$) yuvarlanmış kare kökünü bulmak için gereken yaklaşık iterasyon sayısı kaçtır?
Cevabınızı 10 ondalık basamağa yuvarlayarak verin.

Not: $\lfloor x\rfloor$ ve $\lceil x\rceil$ sembolleri sırasıyla taban ve tavan fonksiyonlarını ifade eder.

Cevap: 4.4474011180