数学研发论坛

 找回密码
 欢迎注册
查看: 479|回复: 14

[悬赏] 素数判别猜想

[复制链接]
发表于 2021-8-21 10:19:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 王守恩 于 2021-8-21 18:24 编辑

各位网友,您能举出反例来?谢谢!

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, ...}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 18:09:48 | 显示全部楼层
这个公式应该是对的。

  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 个。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 18:51:38 | 显示全部楼层
本帖最后由 TSC999 于 2021-8-21 20:17 编辑

主帖中的两个判断,第二个可以去掉,第一个可以简化为:如果中括号内的那个数为整数,即它的小数部分等于零,则 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\) 一定是一个质数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-22 09:44:18 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-22 09:57 编辑
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:47
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-22 12:23:11 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-22 12:32 编辑
王守恩 发表于 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\)  



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-23 10:23:19 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-23 16:56 编辑
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:通项公式与这里不同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-23 10:34:54 | 显示全部楼层
根据Lucas定理,如果2k+1为素数,那么\({3k+2\choose 2k+1}\equiv \lfloor\frac{3k+2}{2k+1}\rfloor=1(\mod 2k+1)\).
但是反过来不好说,我偏向于不成立,但是概率比较低,比较难以寻找
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-23 11:54:20 | 显示全部楼层

弱弱的問一個問題

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

点评

算法是有复杂度的,比如威尔逊定理无法在实际中用来判断素性,就是计算复杂度太高了  发表于 2021-8-23 13:44

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
王守恩 + 3 + 3 + 3 + 3 + 3 愚也是这样想的。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-23 17:13:34 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-23 18:37 编辑
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,...}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-24 04:22:55 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-24 04:25 编辑
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,

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-9-26 13:38 , Processed in 0.074391 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表