素数判别猜想

王守恩

各位网友，您能举出反例来？谢谢！

n=2, 3, 4, 5, 6, 7, .......

\(\D \left\lceil\left[\frac{(n+\lceil n/2\rceil )!\ \ }{n*n!\ \lceil n/2\rceil !\ \ }-\frac{\ 1\ }{n}\right]\right\rceil\) =0，则：n 为素数。

\(\D \left\lceil\left[\frac{(n+\lceil n/2\rceil )!\ \ }{n*n!\ \lceil n/2\rceil !\ \ }-\frac{\ 1\ }{n}\right]\right\rceil\) =1，则：n 为合数。

\(\lceil\ \ \rceil\) 表示小数部分作 1，   [  ] 表示取小数部分,

{0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1,
  1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
  1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0,
  1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, ...}

TSC999

这个公式应该是对的。

1. p = 0; nn = 1000;
   
2. Do[a = \[LeftCeiling]FractionalPart[((n + \[LeftCeiling]n/
   
3.              2\[RightCeiling])!/(
   
4.         n! \[LeftCeiling]n/2\[RightCeiling]!) - 1)/n]\[RightCeiling];
   
5.   If[a == 0, p = p + 1; Print[n, " 是素数"],
   
6.    Print["                  ", n, " 是合数"]], {n, 2, nn}];     
   
7. Print["-----------------------------"]
   
8. Print[nn, " 以内的素数共有", p, " 个。"]

复制代码

运行结果：

2 是素数
3 是素数
                  4 是合数
5 是素数
                  6 是合数
7 是素数
                  8 是合数
                  9 是合数
                  10 是合数
11 是素数
                  12 是合数
13 是素数
                  14 是合数
                  15 是合数
                  16 是合数
17 是素数
                  18 是合数
19 是素数
                  20 是合数
                  21 是合数
                  22 是合数
23 是素数
                  24 是合数
                  25 是合数
                  26 是合数
                  27 是合数
                  28 是合数
29 是素数
                  30 是合数
31 是素数
                  32 是合数
                  33 是合数
                  34 是合数
                  35 是合数
                  36 是合数
37 是素数
                  38 是合数
                  39 是合数
                  40 是合数
41 是素数
                  42 是合数
43 是素数
                  44 是合数
                  45 是合数
…………………………………               
991 是素数
                  992 是合数
                  993 是合数
                  994 是合数
                  995 是合数
                  996 是合数
997 是素数
                  998 是合数
                  999 是合数
                  1000 是合数
-----------------------------
1000 以内的素数共有168 个。

TSC999

主帖中的两个判断，第二个可以去掉，第一个可以简化为：如果中括号内的那个数为整数，即它的小数部分等于零，则 n 为质数。此时验证程序为：

1. p = 0; nn = 1000;
   
2. Do[a = FractionalPart[((n + \[LeftCeiling]n/2\[RightCeiling])!/(
   
3.        n! \[LeftCeiling]n/2\[RightCeiling]!) - 1)/n];
   
4.   If[a == 0, p = p + 1; Print[n, " 是素数"],
   
5.    Print["                  ", n, " 是合数"]], {n, 2, nn}];     
   
6. Print["-----------------------------"]
   
7. Print[nn, " 以内的素数共有", p, " 个。"]

复制代码

再进一步，为了简化 \(\lceil{n/2}\rceil \)，因为 \(n\) 为偶数时它除了 2 以外都不是质数，因此可设  \(n=2k+1\) 为奇数。这时 \(\lceil{n/2}\rceil =k+1\)。
于是当\((\frac{(3k+2)!}{(2k+1)!(k+1)!}-1)/(2k+1)\) 是整数时 \(n\) 一定是质数。

判断程序为：

1. Do[a = ((3 k + 2)!/((2 k + 1)! (k + 1)!) - 1)/(2 k + 1);
   
2.   b = FractionalPart[a];
   
3.   If[b == 0, Print[2 k + 1, " 是素数，", a]], {k, 1, 50}];     

复制代码

运行结果为：

3 是素数，3
5 是素数，11
7 是素数，47
11 是素数，1125
13 是素数，5963
17 是素数，183797
19 是素数，1054211
23 是素数，36280513
29 是素数，7927986795
31 是素数，48491374487
37 是素数，11477188636427
41 是素数，449096510607529
43 是素数，2824545240027293
47 是素数，112769668965801817
53 是素数，29009804371092465443
59 是素数，7606022310808815494125
61 是素数，48854966689227567975467
67 是素数，13065818757364631400798647
71 是素数，546031659191785041005141179
73 是素数，3536219141211332339295440813
79 是素数，966724457763419120195019467447
83 是素数，40918043907667176391511840640003
89 是素数，11339650621723233348853877941814391
97 是素数，20702264189708229960360102755270342567
101 是素数，888019485210345218014769523770429379379

所以主帖的问题可归结为：

证明：如果\((\frac{(3k+2)!}{(2k+1)!(k+1)!}-1)/(2k+1)\) 是整数，证明 \(2k+1\) 一定是质数。

例如，当 \(k=50\) 时，由于 \((\frac{(3k+2)!}{(2k+1)!(k+1)!}-1)/(2k+1)=888019485210345218014769523770429379379\) 是一个整数，所以  \(2k+1=101\) 是一个质数。

这个问题能不能归结到判断质数的威尔逊定理呢？ 这个定理说，如果 \((n-1)!+1\) 能被 \(n\) 整除，那么  \(n\) 一定是一个质数。

王守恩

TSC999 发表于 2021-8-21 18:51
主帖中的两个判断，第二个可以去掉，第一个可以简化为：如果中括号内的那个数为整数，即它的小数部分等于零 ...

说得好：这个问题能不能归结到判断质数的威尔逊定理呢？ 这个定理说，如果(n-1)!+1 能被 n 整除，那么 n 一定是一个质数。

主帖(1楼)可以化简。

n=1, 2, 3, 4, 5, 6, 7, .......

\(\D \left\lceil\left[\frac{n!+1\ }{n+1}\right]\right\rceil\) =0，则：n+1 为素数。

\(\D \left\lceil\left[\frac{n!+1\ }{n+1}\right]\right\rceil\) =1，则：n+1 为合数。

\(\lceil\ \ \rceil\) 表示小数部分作 1，   [  ] 表示取小数部分,

{0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1,
  1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
  1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0,
  1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, ...}

参考 A005171：通项公式与这里不同。       
看\([\frac{n!+1}{n+1}]\)就清楚了。

王守恩

王守恩 发表于 2021-8-22 09:44
说得好：这个问题能不能归结到判断质数的威尔逊定理呢？ 这个定理说，如果(n-1)!+1 能被 n 整除，那么  ...

咋化简的？还得回到上一个帖子(我还不知道怎么连接，在那里我也不敢太捣乱),我们有
\(F(n,m)=(\frac{n!/m}{m!(n-m)!}+\frac{(m-1)\lfloor n/m\rfloor}{m})\)(33楼mathe)\(=(\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor)\)(3楼)
即：\((\frac{n!/m}{m!(n-m)!}+\frac{(m-1)\lfloor n/m\rfloor}{m})-(\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor)\)
\(=\frac{n!/m}{m!(n-m)!}-\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\frac{(m-1)\lfloor n/m\rfloor}{m}-\frac{m*\lfloor n/m\rfloor}{m}+\lfloor\frac{n}{m^2}\rfloor\)
\(=\big[\frac{n!/m}{m!(n-m)!}\big]-\frac{\lfloor n/m\rfloor}{m}+\lfloor\frac{n}{m^2}\rfloor\)
设\(n=m+\lfloor m/2\rfloor\)来到1楼主帖：\(\big[\frac{(m+\lfloor m/2\rfloor)!}{m*m!\lfloor m/2\rfloor!}\big]-\frac{1}{m}+0\)  

王守恩

TSC999 发表于 2021-8-21 18:09
这个公式应该是对的。

这样更直观。把 0 删除，就是《素数表》。好心的网友，这些 0 怎么删除？

n=5, 6, 7, 8, 9, ....    \(\D n^2\bigg[\frac{(n-2)!\ }{n}\bigg]\)， [  ] 表示取小数部分,

{5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 0, 0,
47, 0, 0, 0, 0, 0, 53, 0, 0, 0, 0, 0,  59, 0,  61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71,  0, 73, 0, 0, 0, 0, 0,  79, 0, 0, 0, 83, 0, 0, 0, 0, 0,
89, 0, 0, 0, 0, 0, 0, 0, 97, 0, 0, 0, 101, 0, 103, 0, 0, 0, 107, 0, 109, 0, 0, 0, 113, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 0, 0,
0, 131, 0, 0, 0, 0, 0, 137, 0, 139, 0, 0, 0, 0, 0, 0, 0, 0, 0, 149, 0, 151, 0, 0, 0, 0, 0, 157, 0, 0, 0, 0, 0, 163, 0, 0, 0, 167, 0, 0,
0, 0, 0, 173, 0, 0, 0, 0, 0, 179, 0, 181, 0, 0, 0, 0, 0, 0, 0, 0, 0, 191, 0, 193, 0, 0, 0, 197, 0, 199, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
211, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  223, 0, 0, 0, 227, 0,  229, 0, 0, 0, 233, 0, 0, 0, 0, 0,  239, 0,  241, 0, 0, 0, 0, 0, 0, 0, 0, 0,
251, 0, 0, 0, 0, 0, 257, 0, 0, 0, 0, 0, 263, 0, 0, 0, 0, 0, 269, 0, 271, 0, 0, 0, 0, 0, 277, 0, 0, 0, 281, 0, 283, 0, 0, 0, 0, 0, 0, 0,

参考 A000040：通项公式与这里不同。

mathe

根据Lucas定理，如果2k+1为素数，那么\({3k+2\choose 2k+1}\equiv \lfloor\frac{3k+2}{2k+1}\rfloor=1(\mod 2k+1)\).
但是反过来不好说，我偏向于不成立，但是概率比较低，比较难以寻找

ejsoon

如果我們有逐一排除法，這個最簡明的素數判定方法，再加上量子計算機，我們就應該可以找到所有夠用的素數⋯

王守恩

TSC999 发表于 2021-8-21 18:09
这个公式应该是对的。

对计算量作裁减。

n=10, 11, 12, 13, 14, 15, 16,1 7, .......

\(\D\left\lceil\left[\frac{\lceil n/2\rceil!\ }{n}\right]\right\rceil\)=1，则：n 为素数。

0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1,
0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0,...}

王守恩

ejsoon 发表于 2021-8-23 11:54
如果我們有逐一排除法，這個最簡明的素數判定方法，再加上量子計算機，我們就應該可以找到所有夠用的素數&# ...

接 6 楼。把 0 删除，就是《素数表》。好心的网友，这些 0 怎么删除？

n=10, 11, 12, 13, 14, 15, 16, .....    \(\D n\left\lceil\left[\frac{\lceil n/2\rceil!\ }{n}\right]\right\rceil\)

0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 0, 0, 47, 0, 0, 0, 0,
0, 53, 0, 0, 0, 0, 0, 59, 0, 61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71, 0, 73, 0, 0, 0, 0, 0, 79, 0, 0, 0, 83, 0, 0, 0, 0, 0, 89, 0, 0, 0, 0, 0,
0, 0, 97, 0, 0, 0, 101, 0, 103, 0, 0, 0, 107, 0, 109, 0, 0, 0,113, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,127, 0, 0, 0, 131, 0, 0, 0, 0,
0, 137, 0, 139, 0, 0, 0, 0, 0, 0, 0, 0, 0, 149, 0, 151, 0, 0, 0, 0, 0, 157, 0, 0, 0, 0, 0, 163, 0, 0, 0, 167, 0, 0, 0, 0, 0, 173, 0, 0,
0, 0, 0, 179, 0, 181, 0, 0, 0, 0, 0, 0, 0, 0, 0, 191, 0, 193, 0, 0, 0, 197, 0, 199, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 211, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 223, 0, 0, 0, 227, 0,  229, 0, 0, 0,  233, 0, 0, 0, 0, 0, 239, 0,  241, 0, 0, 0, 0, 0, 0, 0, 0, 0,  251, 0, 0, 0, 0, 0,
257, 0, 0, 0, 0, 0, 263, 0, 0, 0, 0, 0, 269, 0, 271, 0, 0, 0, 0, 0, 277, 0, 0, 0, 281, 0, 283, 0, 0, 0, 0, 0, 0, 0, 0, 0, 293, 0, 0, 0,