洋葱素数

gxqcn

原帖由 mathe 于 2008-4-3 17:03 发表
...

1.         for(it=orig_list->begin();it!=orig_list->end();++it){
   
2.             integer& u=*it;
   
3.             for(j=1;j<=9;j++){
   
4.                 integer cur(j*v+u);
   
5.                 if(CHugeInt(cur).IsPrime()){
   
6.                     new_list->push_back(cur);
   
7.                     printf("%s\n",cur.GetStrA(FS_NORMAL));
   
8.                     count++;
   
9.                 }
   
10.             }
    
11.         }

复制代码

...

中 CHugeInt(cur).IsPrime() 可直接简化为 cur.IsPrime()，

上面引用的那段代码进一步可优化为：

1.         for(it=orig_list->begin();it!=orig_list->end();++it){
   
2.             integer cur(*it);
   
3.             for(j=1;j<=9;j++){
   
4.                 cur += v;
   
5.                 if(cur.IsPrime()){
   
6.                     new_list->push_back(cur);
   
7.                     printf("%s\n",cur.GetStrA(FS_NORMAL));
   
8.                     count++;
   
9.                 }
   
10.             }
    
11.         }

复制代码

不过，由于 mathe 的算法已非常高效，感觉屏幕甚至来不及输出就结束了，所以这里代码级的优化没有太大必要

这类与计数法则相关的题目，即与我们通常所用的十进制相关的题目，
如果涉及到大数运算，HugeCalc 具有得天独厚的优势（双进制内核，内部可高效转换）。

想当初看到 mathe 用 GMP 随手写出大段大段的代码，令人羡慕，
而如今又见 mathe 能将另一个算法库同样运用得如此娴熟，不得不让人佩服啊！

gxqcn

忽然想到：如果“洋葱素数”允许在剥离过程中产生的数首位为“0”的话，结果会多很多！

这个主要是针对“外洋葱素数”数而言，“内洋葱素数”不存在该问题。

如果允许上述条件，则“外洋葱素数”就是无限的了，无论是有限剥离还是无限剥离

无心人

还真没想到
允许空心么？
考虑下
那咱把没空心的叫完美洋葱
不过空心不要太大的
太多空心就不好吃了
允许位数<N/8的空心叫好的空心洋葱素数
空心超过这个限制的叫坏的洋葱素数
如何？
呵呵
觉得挺好玩的

gxqcn

楼主这个比喻比较形象和贴切，
按空心数之比例划分也比较合理。

无心人

不知道能找到相关英文资料么？
昨天找wiki发现国外对这些有趣的东西的研究比国内深且广泛

winxos

3年前就听说过各位大侠的名字了，佩服各位在这些问题上的兴趣！
我对这类问题也很感兴趣，不过水平还比较低。
以前我也想过类似的素数问题，
给定一个尾部，在前面加一个数，如果是素数，则把这个新的素数当尾部，重复这个过程，开开始的这个尾部最长的序列能达到多长，我简单的编了下程，试了一些尾部，长的只有十几位，不知道什么尾部能达到最长的序列。

air

内洋葱素数算掉了一部分（首位数字只能为2、3、5、7，其余数字只能为1、3、7、9），总数应该是83个。
1位：2 3 5 7
2位：23 29 31 37 53 59 71 73 79
3位：233 239 293 311 313 317 373 379 593 599 719 733 739 797
4位：2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
5位：23333 23339 23399 23993 29399 31193 31379 37337 37339 37397 59393 59399 71933 73331 73939
6位：233993 239933 293999 373379 373393 593933 593993 719333 739391 739393 739397 739399
7位：2339933 2399333 2939999 3733799 5939333 7393913 7393931 7393933
8位：23399339 29399999 37337999 59393339 73939133

hujunhua

正整数数列a1, a2, ..., an, ...的递推构造规则为：a(k+1)=ak后缀一个不是9的数字
证明：这个数列中必定有无穷多合数

今天在百度知道中偶见这么个提问，就想起了本坛洋葱素数主题帖。

用反证法，假定这个数列中只有有限个合数，那么以最后那个合数为芯就可以构造一个无限层的内洋葱数。 如果能证明任意有芯内洋葱数总是有限层的，那么就可以完成这个反证。

看楼上各位的讨论，似乎这还是个未解问题。那么从可选数字1，3，7，9中完全排除数字9就可以证明了吗？

manthanein

https://en.wikipedia.org/wiki/Truncatable_prime

葡萄糖

manthanein 发表于 2017-1-30 17:59
https://en.wikipedia.org/wiki/Truncatable_prime

维基百科
https://zh.wikipedia.org/wiki/%E ... D%E8%B3%AA%E6%95%B8
可截短质数是在特定进位制下，位数中不包括0的特定质数。
可左截短质数是指若从最高位数起，由左侧依序删除数字，其结果都是质数的数[1]。例如9137，因为由左侧依序删除数字，得到的9137, 137, 37及7均为质数，因此是可左截短质数，在此文中会以十进制为准。
可右截短质数是指若从最低位数起，由右侧依序删除数字，其结果都是质数的数。例如7393，因为由右侧依序删除数字，得到的7393, 739, 73及7均为质数，因此是可右截短质数。
十进制的可左截短质数共有4260个[1]：
2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 113, 137, 167, 173, 197, 223, 283, 313, 317, 337, 347, 353, 367, 373, 383, 397, 443, 467, 523, 547, 613, 617, 643, 647, 653, 673, 683, 743, 773, 797, 823, 853, 883, 937, 947, 953, 967, 983, 997, 1223, 1283, 1367 ... （OEIS中的数列A024785）
最大的是24位数的357686312646216567629137.

Mathematica官方推出一种铅笔，上面写了一个很大的素数：357686312646216567629137。
这个素数有一个特点，就是从左到右去掉前面若干个数字，剩下的数字仍旧是素数。

百度经验中的视频更新于：2018-12-30 17:17
https://jingyan.baidu.com/article/d5a880ebfb88c113f147ccab.html
优酷中的视频上传于：2018-07-28
https://v.youku.com/v_show/id_XMzc0OTg1MzA4OA

太精巧了！