问题描述

2009年2月medie2005提出问题:
对素数n, 计算其十进制表示的各位数字的乘积s, 若s不小于10,则对s重复上面的步骤,直至结果为一位数.
我们记p(n)为经过的步骤数.
比如,31->3, 则p(31)=1. 47->28->16->6, 则p(47)=3.
现在求使p(n)依次为1,2,...,12的最小素数n.

具体进展

前10个结果

无心人快速给出了前10个结果:
P(11) = 1
P(29) = 2
P(47) = 3
P(277) = 4
P(769) = 5
P(8867) = 6
P(186889) = 7
P(2678789) = 8
P(26899889) = 9
P(3777888899) = 10 #云梦指出这个数不是素数

算法分析

medie2005建议穷举只含素因子2,3,5,7的数,对某个$n=2^a3^b5^c7^d$,计算n的十进制表示的数字的乘积s,然后n到s就有一条边.
通过这样的方法,我们可以得到一个图.
由于只有头部的数是素数,其余的数都是只含2,3,5,7素因子(尾部也可为0).
因此,如果得到的图中,有一条长为k的路径,那么,我们得到头部,然后再由头部得到其前驱,从中选取最小的素数,就得到一个局部的最优解.
若我们对图中所有长度为k的路径,都得到一个局部最优解,从中选优,我们就得到了一个近似最优解.
假定这个近似最优解有T位,我们接下来就是要证明这个近似解是最优或者找到最优解.
我们可以穷举$10^T$内只含素因子2,3,5,7的数,然后再用上面的方法就可以了.
这个穷举问题在gxqcn提出的另外一个贴子里面被详细讨论。
其主要思想就是:
除首项“1”外，在序列顺序增长的过程中，追加项（即新项）总可由现有序列中之前的某项，或乘2或乘3或乘5或乘7（可同时兼具多种途径）构造获得。
我们要做好的是：记录好现有待乘项（*2、*3、*5、*7）的位置，并由此快速获得追加项的值。

11阶结果

mathe估算出$10^{60}$以内这样数的数目约等于$\frac1{4!}\frac{\log^4(10^{60})}{\log(2)\log(3)\log(5)\log(7)}\approx 6364870.77$
并且得出，因子都是2,3,5,7的最小10阶数为$4996238671872=2^{19}3^4 7^6$,
其次为$937638166841712=2^4 3^{20} 7^5$.
通过第一个数字，可以构造出一个11阶的素数277777788888989。
假设还有更小的素数，那么它最多15位，所以所有位数字的乘积不超过$9^{15}\lt 937638166841712$ 也就是证明了只能使用第一个数字来构造这个素数。 而第一个数字构造出的所有数中，这个应该已经是第二小的了（这个可能需要一些比较好的证明方法:)

是否存在12阶结果

medie2005和mathe继续寻找12阶的素数，但是他们穷举到$10^{200}$以内范围还是没有找到结果。
于是mathe开始估算12阶素数存在的可能性到底有多大:
一个任意的n位数，其中所有位都不出现0和5的概率可以认为是$(\frac45)^n$.
所以一个数字连续变换k次，每次变换后各位上都不出现0,5的概率大概为$(\frac45)^{n_1+n_2+...+n_k}$.
其中$n_i$为第i次变换之前的位数。我们就算这些位数平均来说为$\frac n2$.
那么连续变换k次都不出现0和5的概率大概再$(\frac45)^{\frac{nk}2}$.
现在如果选择k=10,那么出现0,5后在两次变换就可能停止了，所以一个n位数12阶以上的概率大概为:
$(\frac45)^{5n}\approx \exp(-n)$.
同样，我们可以估计出不超过n位的因子只有2,3,7的数字数目大概为$\frac1{3!}\frac{n^3}{\log(2)\log(3)\log(7)}\approx 1.37n^3$.
所以我们可以估计出12阶以上的数字出现数目的期望大概在
$\int_{n0}^{\infty}\exp(-n)d1.37n^3=4.11\int_{n0}^{\infty}x^2\exp(-x)dx=(2+2n0+n0^2)\exp(-n0)$.
而对于这个积分，只要n0稍微大一些，显然是个非常非常小的数。
比如:
n0=10时大概为0.0055. n0=20时大概为$9.1\times 10^{-7}$.
n0=100时大概为$3.8\times 10^{-40}$.
所以现在继续向上找能找到一个满足条件的数的概率几乎可以忽略不计,小于$3.8\times 10^{-40}$。

gxqcn统计了（应该是不超过22位？）形如$2^p 3^q 7^r$和$3^q 5^s 7^r$系列整数的持续数步数:
得出所有步数不小于3的数数目非常有限，分别只有587和12组。
最后我们发现OEIS中A003001和A046500已经得出了和我们类似的结论。