Euler Projesi 266. Soru

Sözde Karekök

12 sayısının bölenleri: 1,2,3,4,6 ve 12.
12'nin karekökünü geçmeyen en büyük böleni 3.
Bir n sayısının karekökünü geçmeyen en büyük bölenine, bu sayının sözde karekökü (PSR) diyelim.
Bu durumda PSR(3102)=47 olduğu görülebilir.

190'dan küçük asal sayıların çarpımı p olsun.
PSR(p) mod 10¹⁶ kaçtır?

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.