数学研发论坛

 找回密码
 欢迎注册
查看: 59181|回复: 109

[擂台] csdn number

[复制链接]
发表于 2008-4-17 13:59:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
这个是CSDN上阿诺发的一个题目,觉得挺有意思,转载过来,大家看看:
http://topic.csdn.net/u/20080417 ... d-acc73e3b8cdb.html
设一个合数n的素因子分解式为$S(n)=p_1^{c_1}*p_2^{c_2}*...*p_i^{c_i}$. ( $p_1 <p_2 <... <p_i$ )
将S(n)全部展开,形成如下形式:
$(p_1*...*p_1) * (p_2*...*p_2) * (p_3*...*p_3) * ... * (p_i*...*p_i)$.
再提取上面形式的各个素因子,得到如下形式:
$p_1...p_1p_2...p_2p_3...p_3...p_i...p_i$
($c_1$个$p_1$)($c_2$个$p_2$)($c_3$个$p_3$)($c_i$个$p_i$)

顺次连接上面的素因子,得到了一个10进制数:
$p_1...p_1p_2...p_2p_3...p_3...p_i...p_i$
记为$"Factor"(n)=bar{p_1...p_1p_2...p_2p_3...p_3...p_i...p_i}$.

比如:n=20=2*2*5, S(20)=2*2*5.
于是Factor(20)=225.

如果对某个n,有Factor(n)%n==0成立,我们称n为一个csdn number.(^_^,恶搞一下).
比如:n=28749=3*7*37*37.
于是Factor(28749)=373737.
而373737/28749=13.
于是28749是一个csdn number.

你能求出多大范围内的csdn number?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 14:17:22 | 显示全部楼层
穷举吧
根本没数学规律啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 14:27:05 | 显示全部楼层
第一感觉想到中国余数定理,想想看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 16:08:13 | 显示全部楼层
不对不对,等明天看结果吧

[ 本帖最后由 shshsh_0510 于 2008-4-17 16:20 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 16:28:28 | 显示全部楼层
你要用CRT做出来才叫不对呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-18 21:38:08 | 显示全部楼层
现在觉得这个问题可以用解决卡米切尔数
/thread-257-1-2.html
类似的方法去做
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-19 07:50:20 | 显示全部楼层
上面方法需要用到CRT ,计算到$10^12$以内应该没有问题,估计可以算到$10^14$以内范围还是可能的。

不过另外一方面,我觉得我们可以通过构造法得出一些特殊的解。
我们首先可以寻找一些形式如$a*10^b+1$的合数,其中a很小,而合数的因子数目尽量多。
找到这样的合数以后,我们将这个合数的部分素因子按顺序排序,如果得到结果能够形成一个$a*p$形式的数,其中p为b位素数,我们就可以得到一个解。
特别的对于a=1,我们选择b为适当的合数应该会比较好,比如a=1,b=15就很可能有解.
这几天我没空,谁有空试验一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-19 11:44:13 | 显示全部楼层
还有一点是我尝试着手工构造没有成功,后来发现CSDN上几个人宣称$10^8$以内没有其它解。所以有点怀疑是否只有唯一解。
所以后来想到是否可以估计一下可能解的数目。假设n是一个候选数,那么通过n的所有素因子排列,我们可以得到另外一个大于n的数m,如果我们看成m是否n的倍数完全随机,那么m是n的倍数的概率应该是$1/n$.通过这个想法,我们可以估计$N$以内csdn数目的期望值应该为
$sum_{n<=N, n=p_1^{a_1} p_2^{a_2} ...p_t^{a_t}, t>=3} 1/n$, 其中求和式种n至少有三个素因子,而且n不是2和5的倍数。
可以看出,这个数据在$N$比较小时不会很大(显然远远小于$sum_{n=1}^N 1/n ~= log(N)$)
但是可以证明上面的和在N趋向无穷时也趋向无穷。所以有理由相信csdn数应该是很多的,只是通常会比较大。

评分

参与人数 1威望 +1 鲜花 +1 收起 理由
shshsh_0510 + 1 + 1 有创造性

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-19 16:20:35 | 显示全部楼层


或者说当数字比较大时
需要借助强力的因数分解工具
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-19 17:51:02 | 显示全部楼层
是的,你能否帮忙将$10^105+1$因子分解掉?这个数字应该有机会
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-5-20 08:32 , Processed in 0.094888 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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