素数的 Willans 公式是否正确？

2023-03-01 05:03| 来源: 网络整理| 查看: 265

这些个奇形怪状的素数公式, 无非就是一个命题/定理中找出一个断言, 然后用谓词重写这个断言, 然后用数学符号重写这些谓词.

Willson 定理

p>1 是素数, 当且仅当 (p-1)!=-1\bmod p, p=1 时同样满足此关系.

注: Willson 定理是 1 被踢出素数的受害者, 当时提出的时候可是不用对1特殊处理的...

所以对于素数和1, 我们可以下断言: \frac{(x-1)!+1}{x}\in \mathbb{Z}

换个表述也就是说:

如果 x\in \mathbb{P}\cup\{1\} , 那么 \frac{(x-1)!+1}{x} 就除的尽, 反之合数就除不尽.

我们给他配个有界函数, 比如 \cos^2(x), 然后调整下周期, 让它只有在断言成立的时候能取到最大值1

不成立的时候下取整变成0就行, 与是我们得到了一个万能的判定素性的布尔函数:

\mathtt{isPrime}(x) = \left\lfloor \cos^{2} \frac {(x - 1) ! + 1} {x}\pi \right\rfloor =\begin{cases} 1, x\in \mathbb{P}\cup\{1\}\\ 0, \mathrm{others} \end{cases}

然后对所有小于 n 的自然数判断一遍加起来就能得到计数函数:

\mathtt{countPrime} (n) = \sum_{x = 1}^{n} \mathtt{isPrime}(x)- 1

计数记得去掉1个, 1 现在规定它不是素数.

这个函数解析数论里常记作 \pi(x) .

给定自然数 n , 满足 \pi(m)

【本文地址】

公司简介

联系我们