素组成数

mathe

呵呵，从期望值上来看，解应该仅仅有限几个。 从2#知道所有位数都必须是2,3,5,7. n位数总共$10^n$个，其中满足所有位数都是2,3,5,7的为$4^n$个，概率为$(2/5)^n$. 同样，这个数的平方约2n为，所以平方也满足条件的概率为$(2/5)^{2n}$ 所以$10^n$个数中满足条件的数的期望为$10^n*(2/5)^{3n}=0.64^n$ 对所有的n求和得到期望数目也就2.8左右。 当然这个估计还很不准，还可以再优化一下，但是大概上可以知道只有有限个数目的可能性很大。而对于位数很大的数，找到解的可能性微乎其微

medie2005

呵呵，mathe分析的很好。 我说一下我的搜索算法。 如果d位数n是一个解，那么必然有： 1）：n数字组成都为素数 2）：$F(n)=n^{2} mod 10^{d}$的数字组成都是素数。 设$n=h*10^{d-1}+s$，那么，F(n)右边d-1位是$F(s)=s^{2}mod10^{d-1} $。 也就是说，F(s)数字组成都为素数是F(n)数字组成都为素数的必要条件。 因此，我们可以从底向上构造满足： 1）：n数字组成都为素数 2）：$F(n)=n^{2} mod 10^{d}$的数字组成都是素数。 的n，通过这样的构造，筛掉部分数据，然后，再对剩下的数验证是否有n^2的数字组成都为素数。

mathe

其实同样还可以从最高位开始向低位构造，得出合法结果最高若干位需要满足的条件。 比如我们可以得到最低30位的所有可能组合和最高29位的所有可能组合。那么穷举$10^50$以内的所有结果就非常容易了（中间有不少于9位数据必须完全匹配的数据不会很多了）

无心人

最低的30位的好得到 最高的？ 怎么计算？ 会很多的 比如以2开始的平方 大部分都以5开始

mathe

从概率上来说类似，只是最低k位可以决定平方的最低k位，但是最高位只能决定k-1位。 比如平方以2.2开头的数的最高位只能为1.***,而22.***开头的最高位只能4