[讨论] 阶乘和素数个数 相关搜索: 素数, 阶乘

medie2005

用$pi(n)$表示不大于n的素数个数.
比如,$pi(13)$=6.     (不大于13的素数有:2,3,5,7,11,13)

13有一个很有意思的性质:$pi(13)$=6=1!*3!,即:$pi(13)$等于13的数字组成(1,3)的阶乘的乘积.
若自然数n满足:$pi(n)$等于n的数字组成的阶乘的乘积,我们就称n为PF数.(^_^,实在不知道取什么名字了).
有同样性质的数还有1512,1520,1521等等.

更难得的,$pi(226130351)$=2!*2!*6!*1!*3!*0!*3!*5!*1!,并且,226130351是素数.
如果n既是PF数,又是素数,则称n为PFP数.

问题:
1):求出10^18内的所有PF数.
2): 13,226130351是前2个PFP数,请求出接下来的两个PFP数.

gxqcn

这么难得的数字是怎么给想到的？

medie2005

呵呵，见A066457。
我估计如果解决问题1），应该有可能再得到一个PFP数。

liangbch

10^18， 太难了吧，不知什么时候可以算出来。

medie2005

呵呵，注意到，数字组成的阶乘的乘积是与顺序无关的。
因此，$10^18$内的的数的数字组成的阶乘的乘积的形式一共只有：$C_27^9$=4686825个。
呵呵，现在关键是计算$pi(n)$。

无心人

问题是
$pi(n), n <= 10^18$
的数据是不完整的！！

而计算$pi(n)$在n很大时是比较慢的

无心人

想起来了， 某人给我一段Haskell代码
可以算$pi(n)$
可惜啊
似乎大概被我丢弃了

medie2005

对PFP数来说，在$10^18$内，仅有2829个素数是候选的PFP数，它们的序号在下面的prime_index.rar 中。最大的候选PFP数可能是第30091839012864000个素数。（如果第30091839012864000个素数小于$10^18$）

无心人

你还是想办法把
$O(n^{2/3})$
的$pi(n)$算法
先做好了吧

medie2005

呵呵，这个题还是可以算到10^14的。
不知道哪位装了mathematical,mathematical里有个函数PrimePi(n)是计算n内的素数个数的，据说可以算到8*10^13。因此，计算到10^14还是没有问题的。