当n=？时，含9的项之和开始大于不含9的项之和

qianyb

68# wayne 本来就应该这样的,有好的方法当然要用好的

chyanog

68# wayne 我没有作弊啊，实质其实一样的，只不过你用了Prepend附加到列表后再组成各数位不含9的数（“Prepend[#, ii] & /@ tmp”，这里不就用到了匿名函数嘛），我的只不过用了另一种途径而已， 殊途同归。 奇怪的是用NSum效率反而会下降。

wayne

71# qianyb

Buffalo

含9的项之和收敛，因此很可能你要找的那个n不存在，盲目地找是没用的。

Buffalo

弄错了，是不含9的项之和收敛，因此所求的n必定存在。

Buffalo

左边分母以i（i=1..8）开头的各有$10^(n-1)-9^(n-1)$项，每项都不小于$10^{1-n}/(i+1)$，以9开头的有$10^(n-1)$项，每项都不小于$10^{-n}$，因此左边大于$(1-0.9^{n-1})(1/2+1/3+...+1/9)+0.1$。类似地，右边分母以i（i=1..8）开头的各有$9^(n-1)$项，每项都不大于$10^{1-n}/i$，因此右边小于$0.9^{n-1}(1+1/2+1/3+...+1/8)$，要求左边大于右边的一个充分条件是$(1-0.9^{n-1})(1/2+1/3+...+1/9)+0.1>0.9^{n-1}(1+1/2+1/3+...+1/8)$，也就是$n\ge 10$就够了。 同样地可以知道左边小于$(1-0.9^{n-1})(1+1/2+1/3+...+1/8)+1/9$，右边大于$0.9^{n-1}(1/2+1/3+...+1/9)$，因此当$n\leq 5$时左边小于右边。综上，所求的n只可能是6，7，8，9，10。 以上只以分母的第一位为比较标准，如果精细一点，以前两位为比较标准，则可以得到所求的n只能是8。

chyanog

用Mathematica又弄了一种方法，还是构造的，比前面的Mathematica版的代码要快些（计算6位以内耗时<2s）：

2. f[n_] := Module[{t,
3. arr = Array[1.0/FromDigits[{##}] &, Join[{8}, Array[9 &, n - 1]],
4. Join[{1}, Array[0 &, n - 1]]]},
5. {t = Total[arr, Infinity](*Tr@Flatten@seq*),
6. HarmonicNumber[10^n - 1.0] - HarmonicNumber[10^(n - 1) - 1.0] - t}
7. ]

复制代码

chyanog

最近学习了Java的字符串类，联系上了这个问题，于是又有了写出来到冲动，同时也用C#写了（大家知道，好多Java code可以稍加修改成为C#的，反之亦然）。发现Java的运行效率竟比C#快不少（网上普遍认为C#一般要比Java稍快，我私下也做过多次比较，他们都有快的时候，谁效率更高似乎没有定论），也许是我不懂C#编译优化选项的缘故。 C++的字符串函数没用过，也许比Java快吧。 另外，在我机子上的测试，相同的Java代码在Linux（我用的Ubuntu，Ubuntu10.10发布后装的）上面比Win上运行效率更高。下面的代码在Windows上面运行14s，而在Linux平台9s。

2. package string;
4. public class Is9
5. {
7. public static void main(String[] args)
8. {
9. long start = System.currentTimeMillis();
10. for (int n = 1;; n++)
11. {
12. long t1 = System.currentTimeMillis();
13. double s9 = 0.0, s0 = 0.0;
14. int d = (int) Math.pow(10, n - 1);
15. for (int i = d; i < 10 * d; i++)
16. {
17. if (Integer.toString(i).contains("9"))
18. //还可以用Integer.toString(i).indexOf("9")!=-1,效率稍低
19. s9 += 1.0 / i;
20. else
21. {
22. s0 += 1.0 / i;
23. }
24. }
25. System.out.printf("\n当n=%d时：", n);
26. System.out.print("s9=" + s9 + "\ts0=" + s0 + "\t");
27. System.out.println("Elapsed time:"+ (System.currentTimeMillis() - t1) + "ms");
28. if (s9 > s0)
29. {
30. System.out.println("当n=" + n + "时：s9>s0");
31. break;
32. }
33. }
34. System.out.println("\nTotal time:"+ (System.currentTimeMillis() - start) + "ms");
35. }
37. }

复制代码

liangbch

刚刚完成一个一个程序，测试表明，和gxq的速度大抵相当。 这个程序的特点是： 预先算出0-999是否含有数字9，将结果保存在1个1000个字节的数组。 算法很容易理解。 下面是源代码：

2. #include "stdafx.h"
3. #include <string.h>
4. #include <stdlib.h>
5. #include <math.h>
6. #include <time.h>
8. char bitArr[1000];
10. int include9(int i)
11. {
12. char buff[12];
13. _itoa(i,buff,10);
14. return ( strchr(buff,'9')!=NULL);
15. }
17. int initBitArray()
18. {
19. int i;
20. memset(bitArr,0,sizeof(bitArr));
21. for (i=0;i<1000;i++)
22. if ( include9(i) )
23. bitArr[i]=1;
24. return 0;
25. }
28. int sumAll(int n)
29. {
30. time_t sec;
31. double s9,s0;
33. int begin=int( pow(10.0,n-1));
34. int end=int( pow(10.0,n))-1;
35. s0=s9=0.00;
37. if (n<=3)
38. {
39. for (int j=begin;j<=end;j++)
40. {
41. if ( bitArr[j] )
42. s9 += 1.00 /j;
43. else
44. s0 += 1.00 /j;
45. }
46. }
47. else
48. {
49. int base;
50. begin/=1000;
51. end/=1000;
53. for (int i=begin; i<=end;i++)
54. {
55. base =i*1000;
56. if ( include9(i) )
57. {
58. for (int j=0;j<1000;j++)
59. s9 += 1.00 /(double)(base+j);
60. }
61. else
62. {
63. for (int j=0;j<1000;j++)
64. {
65. if ( bitArr[j] )
66. s9 += 1.00 /(double)(base+j);
67. else
68. s0 += 1.00 /(double)(base+j);
69. }
70. }
71. }
72. }
73. time(&sec);
74. printf( "n = %d\t%.24s\n", n, ctime(&sec) );
75. printf( "s0 = %.15f\ns9 = %.15f\ns0/s9 = %.15f\n\n\n", s0, s9, s0/s9);
77. return 0;
78. }
80. int _tmain(int argc, _TCHAR* argv[])
81. {
82. initBitArray();
83. for (int n=1;n<=9;n++)
84. {
85. sumAll(n);
86. }
87. return 0;
88. }

复制代码

liangbch

在我的电脑上，gxq 56楼的程序和我这个程序性能相当，只需7秒就得到结果。gxq，能否在你的电脑上测试一下我的这个程序？