任意整数能否修改O(1)位变成质数

l4m2 · 发表于 2022-10-27 12:54:30

您需要登录才可以下载或查看，没有账号？欢迎注册

×

如果只允许修改最低若干位，那么由质数分布可知，需要修改log n=log log x位。但若允许修改任意位置，则常数个修改可能足够。

1. 是否足够？
2. 能否找到修改2位（或以内）不足以变成质数的例子？

northwolves · 发表于 2022-10-27 13:14:07

以下数字修改1位不足以变成质数:
200
320
510
530
620
840
890

gxqcn · 发表于 2022-10-27 13:27:43

首先，需要明确：修改后的数，位数不能大于之前的位数吧？
也即：修改的数字，必须在原数的最低位与最高位之间。
比如，不允许出现：将 “321”修改成“400321”这种情形。

nyy · 发表于 2022-10-27 13:40:12

再你说一个数是素数之前，你总得判定吧？
判定都是一个很难的事！

northwolves · 发表于 2022-10-27 13:40:26

gxqcn 发表于 2022-10-27 13:27
首先，需要明确：修改后的数，位数不能大于之前的位数吧？
也即：修改的数字，必须在原数的最低位与最高位 ...

应该是从一个n位数到另一个n位数，只是改变一两个数位上的数

gxqcn · 发表于 2022-10-27 14:30:40

如果不局限于10进制的话，建议先在二进制下试着找反例

aimisiyou · 发表于 2022-10-27 14:45:48

7位？

l4m2 · 发表于 2022-10-27 15:02:49

gxqcn 发表于 2022-10-27 14:30
如果不局限于10进制的话，建议先在二进制下试着找反例

在2^24内搜索结果
修改4位及以上 0
修改3位 545773
修改2位 7310737
修改1位 7842833
修改0位 1077871

l4m2 · 发表于 2022-10-27 15:03:44

nodejs代码

A=[...Array(16777216)].map((_,i)=>i);A[0]=A[1]=1/0;for(i=2;i<16777216;++i)if(A[i]<1e9)for(j=i+i;j<16777216;j+=i)A[j]=Infinity;0
F=0;for(p=1;p<16777216;p+=p)for(i=p;i<p+p;++i)for(j=p;j>>=1;)if(A[i]>A[i^j]+1e9)++F,A[i]=A[i^j]+1e9;F // until F=0

复制代码

l4m2 · 发表于 2022-10-28 02:33:26

范围2^31，修改位数/fail数量
0 2042386083
1 1045197146
2 76552887
3 2 (就是0和1不能改位数）

账号		自动登录	找回密码
密码			欢迎注册

[猜想] 任意整数能否修改O(1)位变成质数