theory of numbers

作业

  1. 求 $\pi(200)$ 的值。

    $\sqrt{200}$ 内的素数有 2,3,5,7,11,13。$\pi(\sqrt {200}) = 6$ ,

    $P(\sqrt{200})=2\cdot3\cdot5\cdot7\cdot11\cdot13$

    $\pi(200)=\pi(\sqrt{200})-1+\sum\limits_{d\mid P(\sqrt{200})}\mu(d)[\frac {200} d] $

    $=6-1+200-267+132-24=46$

  2. 求 $\sum\limits_{d\mid n}\mu(d)\sigma(d)$ 的值。

    背景知识已经证明 $\mu(n),\sigma(n)$ 都是积性函数,即 $f(n)=\mu(n)\sigma(n)$ 也是积性函数。故 $F(n)=\sum\limits_{d \mid n}f(n)$ 也是积性函数,那么可知 则若 $n=p_1^{\alpha^1}\cdots p_r^{\alpha_r}$

    $F(n)=F(p_1^{\alpha_1})\cdots F(p_r^{\alpha_r})=(-1)^rp_1\cdots p_r$

实例

  1. 求不超过 100 且与 2,3,5 均互素的正整数的个数。(背景知识 3)

    这里取 $A=\lbrace1,2,\cdots,100\rbrace,K=2\cdot3\cdot5$

  2. 求不超过 100 的素数个数 $\pi(100)$ 。(利用 eratosthenes 筛法)

    $\sqrt {100}=10$ 的素数为 2,3,4,5,7,$\pi(10)=4$ ,背景知识 4 的式子(1)的 x 取 100,

    $P(10)=2\cdot3\cdot5\cdot7=210$ ,得到

背景知识

  1. $M \ddot o bius$ 函数 $\mu(n)$ 定义在 N 上, 可以推出 $\mu(n)$ 是积性函数,但不是完全积性的。

  2. 设 n 是正整数,得到 证明:首先证明 $I(n)$ 是积性的,得到 $I(1)=1$ ,然后知道 $I(p^\alpha)=1+\mu(p)=0,\alpha\ge 1$

    利用这个式子我们可以提出一个一般方法:对给定的有限整数序列 A 及整数 K,如何去求序列 A 中所有与 K 既约的整数个数。

  3. 设 A 是一个给定的有限整数序列,K 是给定的正整数,再设 $A_d$ 表示 A 中被正整数 d 整除的所有整数组成的子序列,$p_1,\cdots,p_s$ 是 K 的所有的不同的素因数,以及 $\mid A_d \mid$ 表序列 $A_d$ 中的整数个数。那么序列 A 中所有与 K既约的数的个数

    $S(A;K)=\sum \limits_{\alpha\in A,(a,k)=1}1=\sum\limits_{d \mid K}\mu(d)\mid A_d\mid$

  4. eratosthenes 筛法