2 üzeri 1000 (çözüldü)

[proble_m]

Kendisinden küçük ve kendisi ile aralarında asal 2¹⁰⁰⁰ tane sayı olan kaç tane tamsayı vardır?

[Lokman Gökçe]

Problemin çözümü olan tam 32 tane tamsayı vardır

ÇÖZÜM:

p > 2 olmak üzere p = 2^k + 1 şeklinde kaç tane asal p sayısı vardır. bazıları 3, 5, 17, 257, 65537 dir. 2^k + 1 nın asal olması için k tamsayısının da tek tamsayı böleni olmaması gerektiğini biliyorum. Yani k = 2ⁿ formatında olmalıdır. Bu sayılar F_n = 2⁽²ⁿ⁾ formatındadır.

Bunlara fermat sayıları denir. Tabii her n için bunlar da asal olmuyor.

F₅ = 641 x 6700417 şeklinde iki sayının çarpımından müteşekkildir. n nin bayaa büyük değerleri için Fermat sayılarının asallığı bilgisayarlarla denenmiş ve n > 5 için F₂₁ e kadar asal olmadığı görülmüş. Bu nokta önemlidir. Çünkü bizim problemimizde,

2⁽²²¹⁾ sayısı, işimiz olmayacak kadar büyük bir sayı.Sonuçta p = 3, 5, 17, 257, 65537 sayılarına dikkat etmeliyiz.

Şimdi biz Φ(n) = 2¹⁰⁰⁰ denkleminin çözüm sayısını bulacağız.

n = 2¹⁰⁰¹, 3.2¹⁰⁰⁰, 5.2⁹⁹⁹, 3.5.2⁹⁹⁸ gibi sayılar çözüm olmakta. (Bunların birer çözüm olduğunu euler'in phi fonksiyonunun özelliklerinden kolayca anlayabiliyoruz) Demek ki 3, 5, 17, 257, 65537 sayılarından bir kısmını en fazla bir tane çarpan olarak bulunduran sayıları arıyoruz. {3, 5, 17, 257, 65537} kümesi 5 elemanlı olduğundan 2⁵ = 32 tane alt kümeye sahiptir. Sorumuzun cevabı 32 dir.

[proble_m]

Sayın hocam tebrikler..
Sorunun kaynağı:
http://www.qbyte.org/puzzles/puzzle16.html
Soru 152
Çözümü verilmemişti. Ama ipuçları benzer çözüm verileceğini gösteriyor.

[Lokman Gökçe]

evet hocam, ipuçlarına baktım biraz önce. Problemin F_n Fermat sayılarıyla ilgili olduğu anlaşılıyor. Bir de ipuçlarında Euler phi fonksiyonu olan Φ(n) fonksiyonunda n nin çift ya da tek olması hallerine göre bazı eşitliklerin ispatlanması ön adım olarak tavsiye edilmiş. Herhalde sitenin vereceği çözüm de bu istikammette olacak. Ben, Ali Nesin bey'in bir yazısını incelemiştim. F₅ den F₂₁ e kadar olan sayılar asal değildir ve F₂₂ için asal olup olmadığı henüz bilinmeyen en küçük Fermat sayısıdır denilmiş. Bu yardımcı bilgiye sahip olunca problem kolaylaşıyor. Daha büyük bir değer olarak şu problemi de yöneltebilirim:


Kendisinden küçük ve kendisiyle ile aralarında asal 2⁽²²¹⁾ tane sayı olan kaç pozitif tamsayı vardır?

Bu problemin cevabı da aynı düşünce ile 32 dir . Son olarak bahsettiğim yazının linkini veriyorum:

http://geomania.org/forum/fantezi-cebir-arsivi/asal-sayilar/