[求作]划分△ABC的周长与面积

watt5151

  楼主不想自己的帖子偏离既定的“简单、巧妙、兴趣”的方向。

qjchen

用Mathematica做了一下，确实第10题在3000之内只解出了1001和2002两个解

修改了一下，也试出了2003改成2007的时候，这个数是666

那借花献佛一下吧，把watt的题目改成应景一些的，2009快到了，题目就是

求最小的自然数 n
使得 n 位数 1111....111 被 2009 整除
答案:
n=？

hejoseph

第一至第九题除了用程序去解都没什么办法去解的，当然在求解前确定某些情况符合条件会减少程序的计算时间。

第十题实际上是求10对模2003的次数，初等数论上已经有很成熟的方法了。

欧拉函数φ(n)：欧拉函数是一个定义在正整数上的函数，φ(n)的值等于以下这些整数0、1、2、…、n-1与n互素的数的个数。

由定义知，φ(1)=1，φ(2)=1，φ(3)=2，φ(4)=2，……，当p是素数时，φ(p)=p-1。

欧拉函数的计算方法：设n的标准分解式子是p1^k1·p2^k2·…·pm^km，其中p1、p2、…、pm是互不相等的素数，k1、k2、…、km都是正整数，则φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pm)。

例如φ(10)=10×(1-1/2)×(1-1/5)=4。

欧拉定理：设a、m为整数，m>1，(a,m)=1，则a^φ(m)≡1 (mod m)。

整数的次数：a、m为整数，m>1，(a,m)=1，k是使a^k≡1 (mod m)成立的最小正整数，则k叫做a对模m的次数。

次数定理：设a对模m的次数为k，n是满足a^n≡1 (mod m)的正整数，则k|n。

例如
2003是素数，所以问题等价于求10^n≡1 (mod 2003)能被2003整除的最小正整数n，φ(2003)=2002=2×7×11×13，由欧拉定理知10^2002≡1 (mod 2003)，因此所求的正整数就是2002的正因数，只需要尝试有限个就得到所求的n是1001。

虽然这个方法可行，但因数多时仍需要做很多的验证，需要有更有效的改进方法。

假设a、n是大于1的正整数，p是素数，则a对模p的次数没有什么好办法去求，只能用上面的方法。
其它情形有下面两个定理：
假设a、n是大于1的正整数，n的标准分解式是p1^k1·p2^k2·…·pt^kt，其中p1、p2、…、pt是互不相等的素数，k1、k2、…、kt都是正整数，a对模pi^ki的次数为mi，则a对模n的次数为m1、m2、…、mt的最小公倍数。
如果a、n是大于1的正整数，p是素数，k是正整数，a对模p^k的次数是m，则a对模p^(k+1)的次数是m或pm。

例如
2007=3^2×223，问题等价于求10^n≡1 (mod 18063)能被2003整除的最小正整数n。18063=3^4×223。10对模3的次数1；因此10对模9的次数是1或3，经检验得10对模9的次数是1；因此10对模27的次数是1或3，经检验得10对模27的次数是3；因此10对模81的次数是3或9，经检验得10对模81的次数是9。10对模223的次数是222。因此所求的n就是9和222的最小公倍数，即666。

相信利用上面的方法，你已经知道对qjchen提出的2009的情形怎样计算了。

watt5151

watt5151发表于2008-12-27 15:53:00《几何算法》版的特色是作图，非作图题浪费了论坛的资源，下不为例了。楼主还有很多作图题与各位阁下切磋，待第一版的精彩文章‘退居二版’再说。

①象人教论坛那样，不欢迎hejoseph来我的帖子上面摆架子。
②42楼的问题只是小菜一碟。
《几何算法》版的特色是作图，非作图题浪费了论坛的资源，请不要在本帖继续。

chenjun_nj

watt5151不要再发火了，qjchen兄的2009问题用excel算了次。
n=210
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111=2009×55306675515734749184226536142912449532658591892041369393285769592389801449034898512250428626735246944306177755655107571483878104087163320612797964714341020961230020463469940821857198163818372877606327083679

hejoseph

谁摆架子大家都明白了吧？若还对watt5151不满我根本不会近来回帖子。

chenjun_nj

都不要生气了，我们论坛风气挺好的，以前的事就放一边吧！

watt5151

watt5151发表于2008-12-27 10:05:00⑩ 求最小的自然数 n 使得 n 位数 1111....111 被 2003 整除 答案: n=1001 数据: 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 1

请hejoseph先生不要点击watt5151的帖子，以免引出矛盾。
请留意37楼的编辑部分。

qjchen

:)，还是继续劝watt小姐和Hejoseph兄别动动气：）

非常感谢 Hejoseph兄 的数论解法，让人大开眼界，我不是很懂数论，不过居然能解决这种大数问题，看来我得下功夫学习一下了。

也非常感谢chenjun_nj兄的精彩excel解答，不愧是excel方面的高高手，居然用这么简洁的方法就解决了大数问题，以后多向您学习。最喜欢这种用函数就解决问题而不是用宏的方法了。

那我下面说说我的解题过程，我是用Mathematica求解的过程如下：

-----------------------
a = 1
For[i = 1, i < 3000, i++, a = a + 10^i;  If[Mod[a, 2009] == 0, Print[i + 1]]]
-----------------------
按shift+enter，得到一堆210的倍数。

To Watt

------------------------

算爆机的可能性很小啊，用Mathematica，不到1秒钟，得到的结果如下

2011（670）、2017（2016）、2027（1013）、2029（2028）、2039（2038）、2053（342）、2063（2062）、2069（2068）、2081（1040）、2083（1041）、2087（298）、2089（1044）、2099（2098）

这些数字是很有趣的，可以看到许多时候和这个数-1有关系，我来看看是什么规律。

哦，原来Hejoseph兄的理论已经解决了这个规律了，请允许我再仔细看下数论。

hejoseph

qjchen问到我上面问题的原理，解释如下：
问题：111…1（n个）组成一个整数能被p整除（p是比3大素数），求n的最小值。
因为111…1（n个）能被p整除，必然999…9（n个）能被p整除；反之9999…9（n个）能被p整除，那么p必定整除9或111…1（n个）。但3与p互素，所以p必定整除111…1（n个）。所以只要求999…9（n个）能被p整除时n的最小值即可。
又9999…9（n个）=10^n-1，问题就变成求n的最小值使p整除10^n-1，亦即10对模p的次数（请看43楼所写的整除的次数的定义）。
φ(p)=p-1（请看43楼所写的欧拉函数的定义），所以n必定整除p-1（请看43楼所写的次数定理）。