当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）：

1. 
   
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。

1. 
   
2. package string;
   
3. 
   
4. public class Is9
   
5. {
   
6.        
   
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.         }
    
36. 
    
37. }
    

复制代码

liangbch

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

1. 
   
2. #include "stdafx.h"
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <math.h>
   
6. #include <time.h>
   
7. 
   
8. char bitArr[1000];
   
9. 
   
10. int include9(int i)
    
11. {
    
12.         char buff[12];
    
13.         _itoa(i,buff,10);
    
14.         return ( strchr(buff,'9')!=NULL);
    
15. }
    
16. 
    
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. }
    
26. 
    
27. 
    
28. int sumAll(int n)
    
29. {
    
30.         time_t sec;
    
31.         double s9,s0;
    
32.        
    
33.         int begin=int( pow(10.0,n-1));
    
34.         int end=int( pow(10.0,n))-1;
    
35.         s0=s9=0.00;
    
36.        
    
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;
    
52. 
    
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);
    
76.        
    
77.         return 0;
    
78. }
    
79. 
    
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，能否在你的电脑上测试一下我的这个程序？