找回密码
 欢迎注册
查看: 27535|回复: 33

[讨论] 阶乘和素数个数

[复制链接]
发表于 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数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-17 07:46:03 | 显示全部楼层
这么难得的数字是怎么给想到的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-11-17 08:23:18 | 显示全部楼层
呵呵,见A066457
我估计如果解决问题1),应该有可能再得到一个PFP数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-17 10:29:49 | 显示全部楼层
10^18, 太难了吧,不知什么时候可以算出来。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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)$
可惜啊
似乎大概被我丢弃了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-11-17 15:03:18 | 显示全部楼层
对PFP数来说,在$10^18$内,仅有2829个素数是候选的PFP数,它们的序号在下面的prime_index.rar 中。最大的候选PFP数可能是第30091839012864000个素数。(如果第30091839012864000个素数小于$10^18$)

prime_index.rar

12.37 KB, 下载次数: 2, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-17 15:28:17 | 显示全部楼层
你还是想办法把
$O(n^{2/3})$
的$pi(n)$算法
先做好了吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-11-17 18:58:45 | 显示全部楼层
呵呵,这个题还是可以算到10^14的。
不知道哪位装了mathematical,mathematical里有个函数PrimePi(n)是计算n内的素数个数的,据说可以算到8*10^13。因此,计算到10^14还是没有问题的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 03:13 , Processed in 0.050995 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表