$\displaystyle\sum_{k=1}^{n} \varphi(k)$ toplamı neye eşittir ?

Question

$\varphi$, Euler'in $\varphi$ fonksiyonunu göstermek 

üzere

$\displaystyle\sum_{k=1}^n \varphi(k)$ kaça eşittir ?

Sorunun cevabı : $\dfrac{1}{2}\displaystyle{\left(1+\sum_{k=1}^{n}\mu(k)\left\lfloor \frac{n}{k}\right\rfloor^2 \right)}$

Acaba bunu nasıl ispatlarız ? $\displaystyle\sum_{k=1}^n \varphi(k)$ toplamında ki toplanan sayıları $n$'yi bölenler ve bölmeyenler($k$ sayısı için) diye 2'ye ayırsak ardından 

$\displaystyle{\sum_{k/n}^n \varphi(k)}=n$ formülünü kullanarak bir şey elde etmeye çalıştım ama olmadı. Çünkü $n$'yi bölmeyen sayıların $\varphi$ fonksiyonu altındaki toplamlarını bulmak için yol yok gibi.

Eşitliği ispatlamak için izleyebileceğim bir yol var mı? Cevaplarınız için şimdiden teşekkürler.

Comments

Cevap olarak verdiğin tam sayı değil? 

---

1/2 toplanın yanında olmalı.

Mü'nün kare içerenleri sıfırladığını kullandın mı? 

---

evet hocam kullandım. birkaç tane n değeri için de formül sağlıyordu. siz tamsayı olmadığı nasıl buldunuz ?

---

Bi formüle baştan baksana. 1/2 parantez dışında değil, toplanın yanında olmalı.

Şu soruyu soralım:

1 sayısı 1den n'ye kadar kaç tane sayı ile arasında asal

2 sayısı 1den n'ye kadar kaç tane sayı ile arasında asal

3 sayısı 1den n'ye kadar kaç tane sayı ile arasında asal

... 

Daha sonra bu sayıları toplayalım.

---

hocam bu sayıları neden topluyoruz  $\varphi$ fonksiyonu için 

1'den 1'e kadar 1 ile aralarında asal sayıların sayısı

1'den 2'ye kadar 2 ile aralarında asal sayıların sayısı

.....

1'den n'e kadar n ile aralarında asal sayıların sayısı bulmak gerekmezmiydi ?

---

$$\begin{matrix}\boxed{1}& 1 & 1 & 1 \\ \boxed{1}  & 2 &1 & 2 \\ \boxed{1}& \boxed{1} & 3 & 1 \\ \boxed{1} & 2 & \boxed{1}& 4\end{matrix}$$

Satir ve sutunlara gore ebob aldim. Bizden karelerin sayisi isteniyor.  Olusan sekil simetrik oldugundan bunu kare olarak dusunup bastaki $1$i once disa alip sonra ikiye bolup tekrar toplariz. Bu da formule oturuyor.

Yapmamiz gereken tum $1$leri saymak.

---

$4^2-4$ yaptık simetriği kendisi olanları attık şimdi $\dfrac{12}{2}=6$ oldu. Bu 6'dan da  $\displaystyle\sum_{k=2}^4 k-1-\varphi(k)$' yı çıkarırsak sonuç çıkar.

Genel halde şu mu olur o zaman ?

$\displaystyle\sum_{k=1}^n \varphi(k)=\dfrac{n^2-n}{2}+1-\displaystyle\sum_{k=2}^n (k-\varphi(k)-1)$

---

evet böyle yazabiliyormuşuz. denklemi düzenleyince şaşırtıcı şekilde $1=1$ denklemi kaldı.

---

Eboblarinda $2$ carpani barindiranlarin sayisi satirlarda $\left\lfloor\frac{n}{2}\right\rfloor$ sutunlarda  $\left\lfloor\frac{n}{2}\right\rfloor$. Yani toplamda $$-\mu(2)\left\lfloor\frac{n}{2}\right\rfloor^2$$ kadar.

Answer 1

$n=9$ icin bir ornek verelim. Bu kutuyu satir ve sutunun eboblari ile olusturduk. Burada yapmamiz gereken kutu icerisindeki $1$leri saymak.  $$\begin{matrix}\boxed{1}& 1 & 1 & 1 & 1 & 1 & 1 &1 &1\\ \boxed{1}  & 2 &1 & 2 &1 &2 &1 &2 &1\\ \boxed{1}& \boxed{1} & 3 & 1 &1 &3 &1 & 1 &3\\ \boxed{1} & 2 & \boxed{1}& 4 &1 & 2 &1 &8 & 1 \\ \boxed{1} & \boxed{1} & \boxed{1}& \boxed{1} &5 &1&  1 & 1 & 1  \\\boxed{1}& 2& 3 &2 &\boxed{1} & 6 & 1 & 2& 3  \\ \boxed{1} &\boxed{1} &\boxed{1} &\boxed{1} &\boxed{1}  &7 &1&1 &1  \\ \boxed{1} & 2 & \boxed{1} & 4 &\boxed{1} & 2 &\boxed{1} & 8 & 1 \\ \boxed{1} &\boxed{1} & 3 &\boxed{1} &\boxed{1} & 3 &\boxed{1} &\boxed{1} & 9 \end{matrix}$$

Genel olarak eboblarinda asal carpan olanlari sayacagiz. Bir $p$ asali icin bu tarz bir karede toplamda eboblarinda $p$ asali barindiran  $$\left\lfloor\frac{n}{p}\right\rfloor \cdot \left\lfloor\frac{n}{p}\right\rfloor=\left\lfloor\frac{n}{p}\right\rfloor^2=-\mu(p)\left\lfloor\frac{n}{p}\right\rfloor^2$$ kadar girdi vardir.

Icleme dislama prensibi geregi (kume kesisimlerini de baza alirsak ve kare olanlarin $\mu$ goruntusu sifir oldugundan) $1$ olmayanlarin sayisi $$-\sum_{k=2}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2$$ degerine esit olur.

Dolayisiyla kutudaki $1$lerin sayisi $$\frac{1}{2}\left( n^2--\sum_{k=2}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2+1\right)$$ olur. $n^2$ toplamda $k=1$ yerini alabileceginden istenen deger $$\frac12\left(1+\sum_{k=1}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)$$ olur.