找回密码
 欢迎注册
楼主: l4m2

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

[复制链接]
发表于 2022-10-28 07:58:37 | 显示全部楼层
这个猜想大概率不成立,我猜测可能需要修改$O(\log\log(n))$位或$O(\log\log\log(x))$位才行

上面仅仅只是我的个人猜测,真实情况应该以你们的实测结果为准

点评

二进制2^35下没有发现需要4次的,但是log_2 log_2 35 = 2.3587... 也很小看不出什么东西  发表于 2022-10-28 09:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-28 09:05:21 | 显示全部楼层
l4m2 发表于 2022-10-28 02:33
范围2^31,修改位数/fail数量
0 2042386083            
1 1045197146            

范围16G
0 16416930073            
1 8455517335            
2 628521854              
3 2

范围32G
0 32879532089            
1 16966537585            
2 1266874680            
3 2

代码
  1. #include <stdio.h>
  2. #include <bitset>
  3. const int M = 35;
  4. const long N = 1ll << M;
  5. std::bitset<N> &buf1 = *new std::bitset<N>, &buf2 = *new std::bitset<N>;
  6. int main() {
  7.        
  8.         buf2[0] = 1;
  9.         buf2[1] = 1;
  10.         for (long i=2; i<N; ++i) {
  11.                 if (!buf2[i]) {
  12.                         for (long j=i+i; j<N; j+=i)
  13.                                 buf2[j] = 1;
  14.                 }
  15.                 if(__builtin_popcount(i)<3) fprintf (stderr, "%d   \r", i);
  16.         }
  17.         int times = 0;
  18.         while (1) {
  19.                 long cnt = buf2.count();
  20.                 fprintf (stderr, "%d %ld            \n", times++, cnt);
  21.                 if (cnt<=2) break;
  22.                 buf1 = buf2;
  23.                 for (long p=2; p<N; p<<=1) {
  24.                         for (long b=1; b<p; b<<=1) {
  25.                                 fprintf (stderr, "%d/%d   \r", p, b);
  26.                                 for (long i=p; i<p*2; ++i) {
  27.                                         buf2[i] = (bool)buf2[i] & (bool)buf1[i^b];
  28.                                 }
  29.                         }
  30.                 }
  31.         }
  32. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 12:15:33 来自手机 | 显示全部楼层
修改一下表述:任意一个大于或等于两位的奇数,能否只改变其中的一个数字,不改变其位数,总能找到1个素数

点评

加个条件,最后一位不是5  发表于 2022-10-28 14:30
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 12:23:45 来自手机 | 显示全部楼层
这个表述太弱,以333为例,变个位3有1,5,7,9共4个组合,变十位3有9种组合,变百位3
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 12:27:20 来自手机 | 显示全部楼层
变百位3,有9种组合,位数越多,组合的种类越多,这么多组合中总能找到1个素数,不要找到反例来打击我

点评

打击你一下:205  发表于 2022-10-28 12:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-28 14:44:24 | 显示全部楼层
数论爱好者 发表于 2022-10-28 12:15
修改一下表述:任意一个大于或等于两位的奇数,能否只改变其中的一个数字,不改变其位数,总能找到1个素数

最小的不以5结尾的反例是212159

点评

1e9之内都能改2位  发表于 2022-10-28 15:34
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 19:00:10 | 显示全部楼层
确实厉害,212159改一位真的找不到一个素数.
你说:1e9之内都能改2位.如果只改动末尾的位数,从n与2n之间至少有一个素数,那么看这个2能够缩小到什么值,极值是什么?
n与n+n^0.5之间至少有一个素数
n与n+(ln(n))^2之间至少有一个素数,到这一步,是不是不能再往下了?
任意位置的改动,至少是2位的,一位不行,就如你推翻我找到的那一个.那是不是在10^45以后,至少要改动3位才成立,改动2位是不是能找到反例,一个素数也找不到.

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 19:54:09 | 显示全部楼层
本帖最后由 数论爱好者 于 2022-10-28 19:58 编辑

我的歪理论猜测:改动一位就能够找到的素数,由于一位数是:1至9,那么理论上小于e^9≈8103,只需改动1位就能够找到1个素数.
最小的两位数是10,e^10≈22026,大于22026后就要至少改动2位了,实际找到的数要比22026大一些.
最小的三位数是100,e^100≈2.6881171418161354484126255515800135873611118773741922415191608620*10^43,这个数以后至少要改动3位数了,改动2位有可能找到反例,当然这个数可能远大于e^100,比如可能会在e^317以后才会找到改动2位不能找到任何素数.
任意x值,可能成立的值是:log(ln(x)),若是log(log(x))或log(log(logx))则太小,因为反例中,log(log(212159))≈0.72645509572349位,这个值向上取整才是1位数,
log(ln(212159)≈1.0886位,这个值向上取整,已经是两位数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-28 20:12:25 | 显示全部楼层
有些拿5结尾的找到反例,有些以合数找到反例.在限制严一点,就像2^n-1,n必须为素数.那么你这个命题,任意x值必须为素数才行,这样就不能轻易找到反例.即使找到,可能是很大的数.
你找找看,任意素数,改动其中任何一位,保持其位数不变,无法产生任何一个新的素数.这个原始素数有多大?

点评

我把素数当成修改0位了  发表于 2022-10-28 20:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-28 20:58:28 | 显示全部楼层
数论爱好者 发表于 2022-10-28 19:00
确实厉害,212159改一位真的找不到一个素数.
你说:1e9之内都能改2位.如果只改动末尾的位数,从n与2n之间至少 ...

参考: https://oeis.org/A118118
如果允许在更前面进行修改,那么212159可以改成6212159。这种假设下还存在反例吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 03:50 , Processed in 0.044545 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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