萌新求助Miller-Rabbin

形式化的说，设

n

是给定的奇合数，令

n-1=2^pq

（其中

p,q\in\mathbb{N}

，

q

为奇数），定义

c(n)

为同时满足： a.

1\leq x\leq n-1,x\in\mathbb{N_+}

x^{n-1}\equiv1\pmod n

x^q=1

或

\exists0\leq l<p,l\in\mathbb{N},x^{2^lq}\equiv-1\pmod n

的

x

的数量，定义

f(n)=\frac{c(n)}{n-1}

.
回答并证明：

证明： $f(n)\leq\frac14$
判定 1) 中取等的 $n$ 为有限或无限多个
求 $\dfrac{\sum_{i=1}^n[i\text{ 为奇合数}]f(i)}{\sum_{i=1}^n[i\text{ 为奇合数}]}$ 或 $n\to+\infty$ 时上式的一个估计

讨论操作