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

KeyTo9_Fans

这个猜想大概率不成立，我猜测可能需要修改$O(\log\log(n))$位或$O(\log\log\log(x))$位才行

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

l4m2

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. }

复制代码

数论爱好者

修改一下表述：任意一个大于或等于两位的奇数，能否只改变其中的一个数字，不改变其位数，总能找到1个素数

数论爱好者

这个表述太弱，以333为例，变个位3有1，5，7，9共4个组合，变十位3有9种组合，变百位3

数论爱好者

变百位3，有9种组合，位数越多，组合的种类越多，这么多组合中总能找到1个素数，不要找到反例来打击我

l4m2

数论爱好者 发表于 2022-10-28 12:15
修改一下表述：任意一个大于或等于两位的奇数，能否只改变其中的一个数字，不改变其位数，总能找到1个素数

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

数论爱好者

确实厉害,212159改一位真的找不到一个素数.
你说:1e9之内都能改2位.如果只改动末尾的位数,从n与2n之间至少有一个素数,那么看这个2能够缩小到什么值,极值是什么?
n与n+n^0.5之间至少有一个素数
n与n+(ln(n))^2之间至少有一个素数,到这一步,是不是不能再往下了?
任意位置的改动,至少是2位的,一位不行,就如你推翻我找到的那一个.那是不是在10^45以后,至少要改动3位才成立,改动2位是不是能找到反例,一个素数也找不到.

数论爱好者

我的歪理论猜测:改动一位就能够找到的素数,由于一位数是: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位,这个值向上取整,已经是两位数.

数论爱好者

有些拿5结尾的找到反例,有些以合数找到反例.在限制严一点,就像2^n-1,n必须为素数.那么你这个命题,任意x值必须为素数才行,这样就不能轻易找到反例.即使找到,可能是很大的数.
你找找看,任意素数,改动其中任何一位,保持其位数不变,无法产生任何一个新的素数.这个原始素数有多大?

l4m2

数论爱好者 发表于 2022-10-28 19:00
确实厉害,212159改一位真的找不到一个素数.
你说:1e9之内都能改2位.如果只改动末尾的位数,从n与2n之间至少 ...

参考： https://oeis.org/A118118
如果允许在更前面进行修改，那么212159可以改成6212159。这种假设下还存在反例吗？