medie2005 发表于 2008-11-16 22:42:27

阶乘和素数个数

用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 发表于 2008-11-17 07:46:03

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

medie2005 发表于 2008-11-17 08:23:18

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

liangbch 发表于 2008-11-17 10:29:49

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

medie2005 发表于 2008-11-17 10:41:17

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

无心人 发表于 2008-11-17 11:46:40

:)

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

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

无心人 发表于 2008-11-17 11:51:49

:)

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

medie2005 发表于 2008-11-17 15:03:18

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

无心人 发表于 2008-11-17 15:28:17

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

medie2005 发表于 2008-11-17 18:58:45

呵呵，这个题还是可以算到10^14的。
不知道哪位装了mathematical,mathematical里有个函数PrimePi(n)是计算n内的素数个数的，据说可以算到8*10^13。因此，计算到10^14还是没有问题的。
页: [1] 2 3 4
查看完整版本: 阶乘和素数个数