Kesirli bulmaca
Bu, hem bilgisayar bulmaca etiketi hem de bilgisayar olmayan etiketi içeren bir bilmecedir .
Aşağıdaki beş kesir listemiz var:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Bir tamsayı ile başlayan $x$, aşağıdaki işlemi gerçekleştiriyoruz: her adımda çarpın $x$ Yukarıdaki listedeki ilk kesire göre (soldan sağa) bir tamsayı sonucu verir.
Listede böyle bir kesir yoksa, prosedür biter ve değeri $x$ nihai sonuçtur.
Örnek: ile başlamak $x = 2$
ilk adım: ile çarpın $21/2$hangi verir $21$.
ikinci adım: ile çarpın $5/7$hangi verir $15$.
üçüncü adım: ile çarpın $11/5$hangi verir $33$.
dördüncü adım: ile çarpın $1/11$hangi verir $3$.
Bunu görüyoruz $x = 3$ çarparak nihai sonuçtur $3$ Beş kesirden herhangi biri tamsayı olmayan bir sonuç verecektir.
Soru: şununla başlarsak $x = 2^{1234567}$, o zaman nihai sonucun son üç rakamı ne olacak?
Açıklama:
Bu bir dereceye kadar iyi biliniyor ve kasıtlı olarak adından bahsetmiyorum, çünkü çözmek için fazladan bilgiye ihtiyaç duyulmayacak kadar basit olmalı.
Elbette, cevabınızda adı belirtebilirsiniz!
Yanıtlar
Bunu gözlemliyoruz
sadece bir kesrin paydası 2'dir
X = 2 ^ 1234567'ye sahip olduğumuz için, onu yerleştirmeyi deneyebiliriz. İşleri kolaylaştırmak için sayıların asal çarpanlara ayırmasını kullanacağız.
Önce 21/2 ile çarparak 2 ^ 1234566 * 3 * 7 elde ederiz. 21 / 2'den önceki tüm kesirler 2, 3 veya 7'den farklı bir asal çarpana sahip olduğundan, fonksiyonun 21/2 ile çarpmaya devam edeceğini biliyoruz. kadar 2 faktör kalmayana kadar. Bu bize 3 ^ 1234567 * 7 ^ 1234567 bırakır.
Sonraki,
5/7 ile çarparız. Listedeki ilk kesrin paydası 5 olduğundan, 5/7 ile çarptığımız her seferde esasen 11/7 ile çarpacağımızı biliyoruz. Çarpıp 3 ^ 1234567 * 7 ^ 1234566 * 11 elde ederiz. 30/77 çarpılacak sonraki kesirdir. 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565 ile sonuçlanırız. 11/5 ile çarpmak bize 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11 verir.
Bunu fark ettik
Çünkü o kadar büyük miktarda 7'miz var ki, 7 saniyemiz bitene kadar 30/77 ve 11/5 ile çarpmaya devam edeceğiz. 7'lerin sayısı her 1 azaldığında, 2'lerin sayısının 1 arttığını ve 3'lerin sayısının 1 arttığını anlıyoruz. 2 ve 3'ün faktör sayısını 1234565 artırıyor ve elde etmek için 7'nin tüm faktörlerini kaldırıyoruz. 2 ^ 1234566 * 3 ^ 2469133 * 11. 11'in faktörünü kaldırmak ve 2 ^ 1234566 * 3 ^ 2469133 elde etmek için 1/11 ile çarpıyoruz.
Bu bizi başlangıçla aynı yerde bırakır, ancak
3 faktörlü bir grup var ve 2'nin faktör sayısı 1 azaldı.
Paydaların hiçbirinin çarpanı 3 olmadığı için,
öncekiyle aynı şeyi, sadece daha az sayıda yapacağız. Tüm 2'leri ortadan kaldırmak bize 3 ^ 3703699 * 7 ^ 1234566 verir. 3 ^ 3703699 * 7 ^ 1234565 * 11 elde etmek için 5/7 ve ardından 11/5 ile çarpıyoruz. 2 ^ 1234565 elde etmek için 2 ve 3'ün tüm kuvvetlerini ve 7'nin tüm kuvvetlerini ve 11'in bir kuvvetini kaldırıyoruz. * 3 ^ 4938264.
Bunu fark ettik
ilk kez 3'ün gücü (1234567 + 1234566) arttı ve bu sefer 3'ün gücü (1234566 + 1234565) arttı. Bu, 2'nin kuvveti için 3'ün gücünü (2x-1) artıracağı anlamına gelir. Bu, 3'ün gücünün olacağı anlamına gelir$\sum_{i=1}^{1234567} 2i-1$ Toplama özelliklerini elde etmek için kullanabiliriz $2*\sum_{i=1}^{1234567} i - 1234567$. İlkinin toplamının$n$ pozitif tamsayılar $\frac{n*(n+1)}{2}$, yani $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, yani $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Bunu görüyoruz
son cevap 3 ^ 1524155677489'dur ve 3 ^ x'in son 3 rakamı her 100 defa tekrarlandığı için, sadece 89 olan 3'ün (mod 100) kuvvetini almamız gerekir.
Bu, sadece son 3 hanesini bulmamız gerektiği anlamına gelir
3 ^ 89.
Son 3 basamağının
3 ^ 10 049,
yani son 3 rakamı
3 ^ 20, 49 ^ 2'nin veya 401'in yalnızca son 3 hanesidir,
yani son 3 rakamı
3 ^ 40, 401 ^ 2 veya 801'in yalnızca son 3 basamağıdır,
yani son 3 rakamı
3 ^ 80, 801 ^ 2 veya 601'in yalnızca son 3 basamağıdır,
yani son 3 rakamı
3 ^ 89, 601 * sayısının son 3 basamağıdır (3 ^ 9'un son 3 basamağı).
Son 3 basamağının
3 ^ 9 yalnızca 683'tür, yani 3 ^ 89'un son 3 basamağı 601 * 683'ün son 3 basamağı olan 483'tür.
Bu, son cevabımızın
483.
Sorumluluk reddi: Hesaplamalarım biraz karışık ve tek bir yanlış hesaplama tüm cevabı yanlış yapacaktır, ancak genel çözüm yine de doğru olmalıdır.
Züppe olarak görünmek istemiyorum ama bir şeyi ekonomik olarak kanıtlamanın / hesaplamanın değeri var. Öyleyse ispatın ikinci yarısını (delice yüksek tamsayı gücünün son üç basamağını hesaplayarak) doğru bir şekilde yapalım. İlk önce türetiyoruz$3^{100}\equiv 1 \mod 1000$ (Euler kullanmadan $\phi$):
den başlayarak $3^5 = 243$ Beşinci kuvveti iki kez daha alalım: Sadece son üç rakama ihtiyacımız olduğu için bu, iki terimli teoremi kullanarak oldukça basittir çünkü üçüncü ve sonraki tüm terimlerin 1000'e bölünebildiği ve bu nedenle göz ardı edilebileceği kolayca görülebilir. $3^{25} \equiv (240+3)^5 \equiv 243 + 5\times 81\times 240 + 10\times 27\times 240^2 + ... \equiv 443 \mod 1000$ $3^{125} \equiv (440+3)^5 \equiv 243 + 5\times 81\times 440 \equiv 443 \mod 1000$
Bu, her iki durumda da aynı değerdir. 3 ve 1000 göreceli olarak asal olduğundan,$3^{100} \equiv 1 \mod 1000$
Bu kurulduktan sonra, acısız bir bilgi işlem yöntemi bulalım
$3^{89}$. Az önce gösterdiklerimizle sahip olduğumuz$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Şimdi, bunun tersinin tahmin edilmesi kolaydır.$3$ modulo $1000$ dır-dir $-333$, bu $9$ dır-dir $-111$. Böylece:$3^{89}\equiv 3^{-11} \equiv 333\times 111^5 \equiv 333\times \left ( 1 + 5 \times 110 \right ) \equiv 333 \times 551 \equiv 333 + 650 + 500 \equiv 483 \mod 1000$