(Euler 9) Pisagor Üçlüsü
Pisagor üçlüsü \(a^2 + b^2 = c^2\) eşiliğini sağlayan \(a < b < c\) üçlüsüne verilen isimdir. Örneğin, \(3^2 + 4^2 = 9+16 = 25 = 5^2\) gibi.
\(a+b+c=1000\) olan tek bir pisagor üçlüsü vardır. Bu üçlüde \(a \cdot b \cdot c\) çarpımını bulunuz.
İlk akla gelen yöntem, teker teker tüm ihtimalleri denemek.
|
from math import sqrt
|
|
|
|
def euler9():
|
|
|
|
for b in range(2, 1001):
|
|
for a in range(b, 0, -1):
|
|
|
|
c = sqrt(a ** 2 + b ** 2)
|
|
|
|
if a + b + c == 1000:
|
|
return (a,b,c)
|
Her zamanki gibi, Euler Problemlerinde ilk akla gelenden daha iyisi var. \(a^2 + b^2 = c^2\) eşitliğini sağlayan terimlerin her birini sabit bir sayıyla çarpığınızda eşitlik bozulmaz. Şu şekilde gösterelim;
$$\begin{align} a^2 + b^2 = c^2 && \text{Bunu doğru kabul ediyoruz.} \\ k^2(a^2 + b^2) = k^2 \cdot c^2 && \text{Eşitliğin her iki tarafını } k^2 \text{ ile çarpalım} \\ k^2 \cdot a^2 + k^2 \cdot b^2 = k^2 \cdot c^2 && k^2 \text{ terimini parantez içine dağıtalım} \\ (k \cdot a)^2 + (k \cdot b)^2 = (k \cdot c)^2 && \text{kareli terimleri parantez içine gruplarsak, önermemizi kanıtlamış olduk.} \end{align}$$
O halde, eğer \(a^2 + b^2 = c^2\) olduğunda \(\frac{1000}{a + b + c} = k\) dersek, \((k \cdot a)^2 + (k \cdot b)^2 = (k \cdot c)^2 \) eşitliğinde terimler toplamı 1000 olur. Öyleyse, kodları tekrar gözden geçirelim;
|
from math import sqrt
|
|
|
|
def euler9_v2():
|
|
|
|
for b in range(2, 1001):
|
|
for a in range(b, 0, -1):
|
|
|
|
c = sqrt(a ** 2 + b ** 2)
|
|
|
|
k, n = divmod(1000, a + b + c)
|
|
|
|
if n == 0:
|
|
return (k*a, k*b, k*c)
|
Sanırım bu problemde yapılabilecek en iyisi bu, o yüzden karşılaştırmaya geçebiliriz.
|
>>> timeit.timeit("euler9()", "from euler9 import euler9", number=1000)
|
|
16.17503372204979
|
|
>>> timeit.timeit("euler9_v2()", "from euler9 import euler9_v2", number=1000)
|
|
0.05705214216433774
|
Yaklaşık 284 kat hızlandık. Gayet başarılı.
Gelecek Problem
10'dan küçük asal sayıların toplamı \(2 + 3 + 5 + 7 = 17\) dir.
İki milyondan küçük asal sayıların toplamını bulunuz.