medie2005 发表于 2008-12-15 20:00:31

素组成数

对自然数n，如果其10进制数字组成中，所有数字都是素数，那么，我们称n为一个素组成数。
比如，57， 数字组成为7，5，都是素数，因此，57是素组成数。

注意到n=5是素组成数，而且n^2=25也是素组成数。
满足n、n^2都是素组成数还有： 235, 72335。

问题：
求出下一个使n、n^2都是素组成数的n，或者证明它不存在。

无心人 发表于 2008-12-15 20:11:12

显然
末位数字必须是5
其他位数字必须是2，3，5，7

无心人 发表于 2008-12-15 20:15:28

开始数字不能为3，
因为9.... <(3a)^2 < 1....
均不能满足要求

无心人 发表于 2008-12-15 20:19:28

开始数字是2不能接数字5

开始数字是5不能接数字3，5

开始数字是7不能接数字7

无心人 发表于 2008-12-15 20:22:55

所以可以定义一个两位数字的开始数字加一位数字的结束数字

假设需要求n位数字(n > 3)
则总的可能尝试是
8 * 4^(n-2)

无心人 发表于 2008-12-15 20:24:20

开始数字是
22 23 27 52 57 71 72 73
结束数字只能是5

medie2005 发表于 2008-12-15 20:57:08

已经搜完10^30内的n，没有发现满足条件的数。

无心人 发表于 2008-12-15 21:23:35

粗略的计算了一下
三位的尾数必须是
235 335 535 735
四位的尾数必须是
2235 2335 3235 3335 5235 5335 7235 7335
五位的必须是
22335 23335 32335 33335 52335 53335 72335 73335

无心人 发表于 2008-12-15 21:26:04

估计每增加两位，可选择的尾数增加一倍
即6，7位的有16种可能
8，9 32种
10，11 64种
...
32,33位是2^17种可能

无心人 发表于 2008-12-15 21:27:39

就是说
如果选择算法恰当
很容易得到64位内的全部可能结果
页: [1] 2
查看完整版本: 素组成数