Apakah ada fungsi penghitungan umum yang terkait dengan fungsi penghitungan prima?

Question

Apakah ada fungsi penghitungan umum yang terkait dengan fungsi penghitungan prima?

Katakanlah misalnya saya ingin semua kelipatan bilangan bulat positif tiga kurang dari atau sama dengan N, apakah ada kelipatan 3 kurang dari atau sama dengan fungsi penghitungan N?

Kadang-kadang, saya mungkin ingin semua perkalian bilangan bulat positif dari hasil kali bilangan prima, misalnya 15, apakah ada kelipatan positif dari 3 dan 5 kurang dari atau sama dengan fungsi penghitungan N?

Answer 1

Hanya untuk memperluas komentar saya: Jika Anda bisa membayangkannya, itu ada. Ini harus didefinisikan dengan baik jika hanya menghitung apakah bilangan bulat memiliki properti atau tidak. Anda dapat melihat fungsi penghitungan apa pun sebagai jumlah kumulatif dari fungsi indikator yang bernilai 1 atau 0 untuk setiap bilangan bulat.

Pertimbangkan fungsi indikator untuk properti Anda $A$, $\chi_A(n)$. Seperti yang telah Anda tunjukkan, Anda dapat menentukan fungsi penghitungan$\pi_A(n)$ sebagai [dengan asumsi kami tertarik pada bilangan bulat positif] $$ \pi_A(n) = \sum_{k=1}^n \chi_A(k) $$Hasil menarik terkait hal ini termasuk fungsi penghasil perbedaan. Untuk bilangan prima$p_k$, dan fungsi penghitungan utama $\pi_p(n)$ $$ \sum_{k=p_1}^\infty x^{\pi_p(k)} = \sum_{k=1}^\infty (p_{k+1}-p_k)x^k $$ secara umum untuk fungsi penghitungan apa pun, untuk angka $a_k$, terkait dengan kondisi $A$ $$ \sum_{k=a_1}^\infty x^{\pi_A(k)} = \sum_{k=1}^\infty (a_{k+1}-a_k)x^k $$ Misalnya, fungsi penghitungan angka $\chi_n(n)=1$, memberi $\pi_n(n)=n$ dan $$ \sum_{k=1}^\infty x^{\pi_n(k)} = \sum_{k=1}^\infty (k+1-k)x^k=\frac{x}{1-x} $$ pada kasus ini $\pi_n(n)$ adalah fungsi penghitungan yang tumbuh paling cepat dan meningkat secara linier.

Pertimbangkan fungsi indikator persegi $\chi_{\square}(n)$, dengan syarat $\square(n):\sqrt{n}\in \mathbb{N}$, maka kita punya $$ \pi_\square(n) = \sum_{k=1}^n \chi_\square(k) $$ kemudian $$ \sum_{k=1}^\infty x^{\pi_\square(k)} = \sum_{k=1}^\infty ((k+1)^2-k^2)x^k = \frac{3x-x^2 }{(x-1)^2} $$ salah satu favorit saya adalah $\pi_p(\pi_p(n))$yaitu fungsi penghitungan prima bersarang, yang terkait dengan urutan A073131 sebagai$$ \sum_{k=3}^\infty x^{\pi_p(\pi_p(k))} = \sum_{k=1}^\infty (p_{p_{k+1}} - p_{p_k})x^k $$ jadi kita bisa lihat $\pi_p(\pi_p(n))$ menghitung bilangan prima terindeks utama , seperti 3, 5, 11, 17, 31, 41, 59, 67, 83, 109, ... atau A006450 . Kita dapat melihat bahwa setiap urutan bilangan bulat yang meningkat secara ketat akan memiliki fungsi indikator, dan oleh karena itu fungsi penghitungan, dan juga fungsi penghasil perbedaan. Kita dapat mengumpulkan berbagai jenis fungsi penghitungan, misalnya$$ \sum_{k=3}^\infty x^{\pi_\square(\pi_p(k))} = \sum_{k=1}^\infty (p_{(k+1)^2} - p_{k^2})x^k $$ memberitahu kami $\pi_\square(\pi_p(k))$ menghitung bilangan prima yang indeksnya persegi , dan ini mengajarkan kita bahwa rantai komposisi umum memberi$$ \sum_{k=x}^\infty x^{\pi_{A} \circ \pi_{B} \circ \cdots \pi_{Z} \circ k} = \sum_{k=1}^\infty (z \circ \cdots \circ b \circ a \circ (k+1) - z \circ \cdots \circ b \circ a \circ (k))x^k $$dan bahwa komposisi fungsi penghitungan juga merupakan fungsi penghitungan , karena sisi kanan ini hanyalah selisih suku.

Contoh Anda: Kelipatan bilangan bulat positif dari tiga sama saja$3,6,9,12,...$, fungsi indikator berpotensi ditulis sebagai $$ \chi_{m3}(n) = \bmod(1+2n^2,3) $$ fungsi penghitungan yang terkait dengan ini adalah $$ \pi_{m3}(n) = \left\lfloor \frac{n}{3} \right\rfloor $$yang menggunakan notasi untuk fungsi lantai. Kita bisa menggunakan konsep bersarang untuk kelipatan 15, kita punya$$ \pi_{m15} = \pi_{m3}(\pi_{m5}(n)) = \pi_{m5}(p_{m3}(n)) = \left\lfloor \frac{\left\lfloor \frac{n}{5} \right\rfloor}{3} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{n}{3} \right\rfloor}{5} \right\rfloor $$ ini harus menghitung angka yang habis dibagi $5$yang indeksnya habis dibagi$3$ atau sebaliknya.