魔方吧·中文魔方俱乐部

标题: 与任何一个九位数都互质的最小整数（原题：1-9组成的九位数不含有的最小的因数） [打印本页]

作者: lulijie 时间: 2009-3-15 18:42:14 标题: 与任何一个九位数都互质的最小整数（原题：1-9组成的九位数不含有的最小的因数）

引子：
N为一个正整数，假如对于任何一个 N以内的整数m，都至少存在一个九位数可以整除m。
（这个九位数由1-9九个数字各用一次组成的，2<=m<=N）
那么N的最大值是多少？
-------------------------------------------------------------------------------------------------------------
上述题目金眼睛火眼金睛，答案手到擒来。
下面换一个难点的：
N为一个正整数，假如对于任何一个 N以内的整数m，都至少存在一个十位数可以整除m。
（这个十位数由0-9十个数字各用一次组成的，2<=m<=N）
那么N的最大值是多少？
假如100的倍数不算，又是多少？
--------------------------------------------------------------------------------------------------------------
高潮篇：
求与任何一个（由1-9九个数字各用一次组成的）九位数都互质的最小整数（大于1）。

[ 本帖最后由 lulijie 于 2009-3-15 21:49 编辑 ]

作者: kexin_xiao 时间: 2009-3-15 19:28:51

坐沙发学习!LZ喜欢数学问题啊

作者: 金眼睛 时间: 2009-3-15 19:56:57

很显然啊，N=10。任意按题意构成的数都不能整除10。

作者: 美景 时间: 2009-3-15 20:02:48

楼上真是金眼睛！

作者: Cielo 时间: 2009-3-15 21:13:40

原帖由 金眼睛 于 2009-3-15 19:56 发表
很显然啊，N=10。任意按题意构成的数都不能整除10。

哈哈我一开始还以为也得编程才行……

金眼睛果然厉害！

作者: lulijie 时间: 2009-3-15 21:22:07

果然厉害，一眼就看出了。没有上当。
但如果10，20，30等10的倍数不算，那又是多少呢？这就费脑了。

作者: 金眼睛 时间: 2009-3-15 23:24:55 标题: 回复 6# 的帖子

人脑不累电脑累，呵呵！1~9除去10的倍数N=5555，其他的改天算。

作者: 骰迷 时间: 2009-3-16 19:11:35

這種九位數共362880個，答案太變態了，樓主弄壞幾部電腦就算出答案啦

作者: 金眼睛 时间: 2009-3-17 21:58:32

这道题不编程体会不到乐趣，呵呵！

白天没时间，所以思考了很多，反而是好事，如果暴力破解，估计要半天吧！

1：采用9！或10！做总次数比多重for循环效率高。
2：依次验证每个数是否能整除然后break，不如分解出9位数或10位数的所有因数来得快。
3：边分解边对长时间没有出现的数值进行验证，呵呵！等着分解完也是很耗时的。
4：第三问的解很可能是满足第一问的质数，否则它的因数之前应该验证过整除某个9位数，即不满足互质条件。
这个结论虽没精确证明，但可以对找到的第一问解加以验证即可。
其实最好是对因数分解中长时间不出现的质数依次验证，找到满足第一问的第一个质数即可，这样最快。

可以看到，上述想法不用将可能情况都求出来，一个五十多行的程序，改改跑跑，两个小时就可以搞定了，呵呵！

第二问答案：37037=7*11*13*37，怪不得跟这么多数格格不入。
第三问答案：44449，曾想过能是个什么数呢，居然是它！

作者: lulijie 时间: 2009-3-17 23:12:29

哈哈，不错，第一问和第三问跟我算的一样，交流以下程序设计经验很不错。我谈谈我的心得：
我用的是最简单易懂的VB6.0程序设计，我的想法是：
1：先设计一个子函数next9()，从1-9组成的任何一个九位数通过子函数next9（），可获得下一个1-9的九位数。
这样可以从初始九位数123456789，通过子函数next9()，遍举所有的1-9组成的九位数。
2：然后用一个for next  循环检验整数m是否满足条件。
   第一题：m从整数2开始逐渐增加，对于每个m检查是否存在一个九位数整除它。九位数从最小开始检验，遇到有一个九位数能整除，就跳到下一个m。直到发现所有的九位数都不能整除为止。记下m即可。其实对于每个m，大部分都不需要检验很多的九位数，因为遇到一个九位数能整除，余下的九位数就不用检验，跳到下一个m。
            但在计算第二题10位数时，经常等了很久都没反应（因为我在每检验一定长度的m时，就会生成一个文件，记录下计算到哪个数字了。）经过调试和思考，发现每当m=10的倍数时，就要等很久，原来，按照我的遍举十位数的方法，要整除m（m是10的倍数）一定要遍举到0在个位时，0从最前位经过我的Next10函数，位置变到个位，花费大量的时间。后来就让遇到10的倍数就跳过，速度快多了。因为0在个位，前九位数就是1-9组成的九位数，按照第一题的结果，在计算m=5555*10=55550之前根本不用理会10的倍数。但由于时间原因，我还暂时只计算到14000之内，没有发现满足要求的结果。还有一个影响速度的原因是vb6.0中的整数最大只能是2147483647，所以对于大于它的十位数，只能通过一个转换来计算，影响了速度。用VB2005来变程就没这个问题了。
第三题：检查两个整数是否互质，设计一个函数来判断两个整数是否互质。利用辗转相除法，就可以判断，最后得到0就是含有公因数，得到1，就是互质。再利用Next9函数，检验方法同第一题。
------------------------------------------------------------------------------------------------------
在计算第一题和第三题都花不了多少时间，第二题费时间明显增加，按照金眼睛的答案，我可能还要继续运行1、2个小时或2、3个小时才能算出这个结果。

作者: yq_118 时间: 2009-5-24 22:02:26

搞不懂提些无聊问题就能加精华，对数学发展没一点建设性

作者: lulijie 时间: 2009-5-25 22:47:08

楼上说的很对，对数学发展确实没有作用。
很多题目都是如此，但有些题目可以锻炼人的思维能力、思维的严密性，比如推理题。有些题目则纯粹挑战计算机的算法，怎样计算得快，怎样计算得准。比如计算圆周率，你可以说圆周率算到小数点后1亿位、1百亿位，对数学发展没有任何意义。但是对计算机的算法的发展却有非常大的贡献。
我的这帖其实无非是怎样设计程序，使得得出答案又快又准。
数学的发展很多时候离不开计算机算法的发展。
计算机的算法，很多时候离不开严密的逻辑分析能力，创新的设计能力。换句话说，没有很好的数学能力，往往设计不出优秀的算法。而算法的锻炼，也可以提高自己的数学能力。
我太罗嗦了。也怪我太推崇计算机对数学解题的帮助了，有些着魔。

作者: r_517 时间: 2009-5-25 22:54:19 标题: 无视11楼

当今世界发展根本离不开计算机，计算机核心就是算法。要是连这些最基本的算法题都做不来，更别说把抽象化的题目具体化以后所面临的各种情况了。试问一句：要是没人会算法，你的手机、电脑、计算器、游戏机，都是哪里来的？

接着，这题目没有建设性？你去好好查查，从二战密码机的出现，到现在银行卡、在线付费，哪个不是用密码学大质数分解方法来得以实现的？大数分解问题是没有建设性的？世界三大密码学难题之一是没有建设性的？

另外，就从你自己的话出发，那你倒是觉得什么才是有建设性的题？

[ 本帖最后由 r_517 于 2009-5-25 23:05 编辑 ]

作者: yq_118 时间: 2009-5-26 01:54:04

原帖由 r_517 于 2009-5-25 22:54 发表
当今世界发展根本离不开计算机，计算机核心就是算法。要是连这些最基本的算法题都做不来，更别说把抽象化的题目具体化以后所面临的各种情况了。试问一句：要是没人会算法，你的手机、电脑、计算器、游戏机，都是哪里来的？

接着，这题目没有建设性？你去好好查查，从二战密码机的出现，到现在银行卡、在线付费，哪个不是用密码学大质数分解方法来得以实现的？大数分解问题是没有建设性的？世界三大密码学难题之一是没有建设性的？

另外，就从你自己的话出发，那你倒是觉得什么才是有建设性的题？

先纠正一个错误，再大的质数也不能分解，这个也不是密码学独有的，应该算数论里面的。

你说的这些问题和楼主说的有什么联系，这几个是利用两个大质数之积的分解没有有效的算法（指多项式时间算法）来实现的。

一个算法的关键在于时间复杂度，超过了多项式复杂程度，基本可以PASS。电脑快多少倍，问题稍微复杂一点，电脑就无能为力了。

有建设性的问题，是指能够引出一个数学分支的问题，例如：
从“高次方程求根式解”到“伽罗瓦理论”
从“七桥问题”到“图论”
……

[ 本帖最后由 yq_118 于 2009-5-26 01:58 编辑 ]

作者: yq_118 时间: 2009-5-26 02:02:15

原帖由 lulijie 于 2009-5-25 22:47 发表
楼上说的很对，对数学发展确实没有作用。
很多题目都是如此，但有些题目可以锻炼人的思维能力、思维的严密性，比如推理题。有些题目则纯粹挑战计算机的算法，怎样计算得快，怎样计算得准。比如计算圆周率，你可以说 ...

计算机的算法，很多时候离不开严密的逻辑分析能力，创新的设计能力。换句话说，没有很好的数学能力，往往设计不出优秀的算法。而算法的锻炼，也可以提高自己的数学能力。

我很赞同,算法设计靠的就是数学能力.

作者: pumpitup 时间: 2009-5-26 11:42:37

这个数是可以很容易找到的,但是要最小整数,那可就难了...

作者: njlcazl 时间: 2009-6-5 16:42:15

VB6.0主要是看重界面的，拿这种不符合解题特点的编程软件来解没有效率，这道题用C语言来解应该比较合适吧

作者: lulijie 时间: 2009-6-5 23:54:04

掌握各种编程语言，根据不同的题目特点选用不同的语言当然好，但是一个人的精力是有限的，又不是专门搞计算机专业的，我觉得没必要什么语言都懂。能运用一种语言（不需要精通），能充分利用自己掌握的其中一部分知识，设计出解题所需的算法，可以利用计算机来解题就可以了。语言的不同也许使得解出答案所需的时间不同，但只要解出来了，多花1、2个小时又有什么关系呢。关键是算法的设计。C语言我一直想学，一直想掌握它，也看了一些书，知道点皮毛，但一直没有坚持学下去，这也是一种遗憾。VB的好处主要是通俗易懂，容易学习。再说升级后的VB2005、VB2007等语言据说已经不输于C语言了。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)