csdn number

medie2005 2008-04-17 11:09:32
设一个合数n的素因子分解式为S(n)=p1^c1*p2^c2*...*pi^ci. ( p1<p2<...<pi )
将S(n)全部展开,形成如下形式:
(p1*...*p1) * (p2*...*p2) * (p3*...*p3) * ... * (pi*...*pi).
再提取上面形式的各个素因子,得到如下形式:
p1...p1 p2...p2 p3...p3 ... pi...pi
(c1个p1) (c2个p2) (c3个p3) (ci个pi)

顺次连接上面的素因子,得到了一个10进制数:
p1...p1p2...p2p3...p3...pi...pi
记为Factor(n)=p1...p1p2...p2p3...p3...pi...pi.

比如: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?
...全文
595 44 打赏 收藏 转发到动态 举报
写回复
用AI写文章
44 条回复
切换为时间正序
请发表友善的回复…
发表回复
mathe 2009-01-19
  • 打赏
  • 举报
回复
第二个csdn number是21757820799
http://www.primepuzzles.net/puzzles/puzz_472.htm
UltraBejing 2008-04-30
  • 打赏
  • 举报
回复
接分是王道!
mathe 2008-04-22
  • 打赏
  • 举报
回复
这个比较难,也许不一定有什么方便的方法
medie2005 2008-04-22
  • 打赏
  • 举报
回复
我说的是如何求满足Factor(n)/n=3或7的csdn number,或者证明不存在满足这种约束的csdn number.
mathe 2008-04-22
  • 打赏
  • 举报
回复
你是说3*10^a+1和7*10^a+1?2,3,5也都不可能是它们的因子(2和5显然不能,主要是测试3),所以对它们最小也只能是7.
而要得到3,只能从11*10^a+1开始
medie2005 2008-04-22
  • 打赏
  • 举报
回复
那3和7呢?
mathe 2008-04-22
  • 打赏
  • 举报
回复
1显然不存在,证明Factor(n)>n很容易。
而如果仅仅用10^a+1的因子分解的方法去构造,显然2,3,5都不可能是10^a+1的因子,所以得到的factor(n)/n不会小于7.但是对于其他格式的情况,倒有可能还有更加小的比例
medie2005 2008-04-22
  • 打赏
  • 举报
回复
呵呵,其实我对大的csdn number兴趣不大.
我现在很想知道Factor(n)/n的值最小可以小到什么程度,是否有满足Factor(n)/n=1的csdn number?
mathe 2008-04-22
  • 打赏
  • 举报
回复
嗯,是小的结果好一些,不过大的结果更加难计算,各有优缺点吧。
比如将10^{3*5*7*11}+1如果因子分解了,我估计可能不止一个解,但是因子分解这个数字的难度应该很大:)
此外不知道是否有谁有兴趣穷举一下n<=10^12或n<=10^14以内的情况(当然很可能无解)。
另外一个可以试验的方向是因子分解a*10^b+1,其中a为3,7,9,11,13,17,19,21,23,27,29,...
因子分解以后,将这些因子排序,去掉一部分,如果余下构成的数是a乘上一个素数,那么也可以构造出一个解。只是
因子分解a*10^b+1更加难,而且通常它的因子数目也不会像10^b+1这种形式的数多,所以最后成功率也应该低一些。
medie2005 2008-04-22
  • 打赏
  • 举报
回复
to yaos:
我觉得factor(n)/n大并不能说明结果好,反而是factor(n)/n小才能说明结果好.
像:
n=859 × 1058313049 × 8591058313049
Factor(n)=85910583130498591058313049
=8591058313049 × (10^13+1)
Factor(n)/n=11
Factor(n)/n值这么小的csdn number,是十分难得的.
yaos 2008-04-21
  • 打赏
  • 举报
回复
10^165+1

7
11
11
13
23
211
241
331
2161
4093
5171
8779
9091
599144041
4124507971
20163494891
183411838171
318727841165674579776721
19835636682880495867311241
1112314101311286003379752617807870409611285281

全部组合中
p=
7132321124121614093517187795991440414124507971
2016349489118341183817131872784116567457977672
1198356366828804958673112411112314101311286003
379752617807870409611285281
剔除数字 11 11 331 9091
factor(n)/n = 11*11*331*9091

p=
7111121124121614093517190915991440414124507971
2016349489118341183817131872784116567457977672
1198356366828804958673112411112314101311286003
379752617807870409611285281
剔除数字 13 23 331 8779
factor(n)/n = 13*23*331*8779
大于上面一个

仅两个可能,均通过100次素性测试
yaos 2008-04-21
  • 打赏
  • 举报
回复
无论n的大小还是factor(n)/n均以俺的最大

哈哈

再分析个更大的

稍后分析10^(2*3*5*7)+1
medie2005 2008-04-21
  • 打赏
  • 举报
回复
C=2928135412796134713011348984112149944960368344121848654483879497562821,
C通过了1000次Miller-Rabin测试.

n=29*281*3541*27961*3471301*13489841*121499449*60368344121*848654483879497562821*C.

Factor(n)=C*(10^70+1).

而10^70+1=29*101*281*421*3541*27961*3471301*13489841*121499449*60368344121*848654483879497562821.

于是, Factor(n)/n=101*421=42521.
medie2005 2008-04-21
  • 打赏
  • 举报
回复
n=7 × 11 × 19 × 211 × 241 × 2161 × 29611 × 52579 × 3762091 × 8985695684401 × 711192112412161296115257937620918985695684401
Factor(n)=711192112412161296115257937620918985695684401711192112412161296115257937620918985695684401
=711192112412161296115257937620918985695684401*(10^45+1)

而10^45+1=7 × 11 × 13 × 19 × 211 × 241 × 2161 × 9091 × 29611 × 52579 × 3762091 × 8985695684401.
于是, Factor(n)/n=13*9091=118183.

711192112412161296115257937620918985695684401通过了严格的素数测试,是一个素数.
shshsh_0510 2008-04-21
  • 打赏
  • 举报
回复
o,你先找到了
medie2005 2008-04-21
  • 打赏
  • 举报
回复
上面的10^14应该是10^13.
medie2005 2008-04-21
  • 打赏
  • 举报
回复
n=859 × 1058313049 × 8591058313049
Factor(n)=85910583130498591058313049
=8591058313049 × (10^14+1)
而10^14+1=11 × 859 × 1058313049
于是,Factor(n)/n=11.
medie2005 2008-04-21
  • 打赏
  • 举报
回复
n=13 × 23 × 4093 × 8779 × 599144041 × 183411838171 × 132340938779599144041183411838171
Factor(n)=132340938779599144041183411838171132340938779599144041183411838171
=132340938779599144041183411838171 × (10^33+1)
而10^33+1=7 × 11 × 11 × 13 × 23 × 4093 × 8779 × 599144041 × 183411838171

于是,Factor(n)/n=7 × 11 × 11=847.
132340938779599144041183411838171通过了严格的素数测试,是一个素数.
medie2005 2008-04-21
  • 打赏
  • 举报
回复
哦,搞错了.142857142857142857143不是素数.
medie2005 2008-04-21
  • 打赏
  • 举报
回复
应是:而10^21+1=7*142857142857142857143.
加载更多回复(24)

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧