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

无心人 · 发表于 2010-5-19 15:50:41

考虑64位精度结果，9位数字情况
两边数字<10^9个
精度 >= 10^9 / 2^64 = 5.42E-11，符合要求

同样道理，64位浮点情况
精度>= 10^9 / 2^53 = 1.11E-7
也满足要求

wayne · 发表于 2010-5-19 16:40:29

21# chyanog

这只是随手一写，关键是要找到一个好算法来分开含9的和不含9的数。

我这个方法很笨，要占用大量的存储空间，不过，速度还可以提高一倍多：

f[x_] := Module[{n = x, tmp, t}, {tmp = Tuples[Range[0, 8], {n - 1}]; t = Sum[Total[1./Map[FromDigits, Prepend[#, ii] & /@ tmp]], {ii, 1,8}], HarmonicNumber[10^n - 1.] -HarmonicNumber[10^(n - 1) - 1.] - t}]

复制代码

gxqcn · 发表于 2010-5-19 16:51:45

29# 无心人

也就是说，已经得到楼主所需的结论：$n>=8$

qianyb · 发表于 2010-5-19 16:59:29

无心人拥有的计算能力是相当的强啊

chyanog · 发表于 2010-5-19 17:42:47

33# gxqcn
嗯，应该没错，有劳大家了。

chyanog · 发表于 2010-5-19 18:01:16

32# wayne

我试过了，用你的函数：
f /@ Range[8] // Timing
Out[1]:=
{244.391, {{2.71786, 0.111111}, {2.05399, 0.294418}, {1.81787,
0.489222}, {1.63336, 0.669671}, {1.46978, 0.832847}, {1.32278,
0.979807}, {1.1905, 1.11208}, {1.07145, 1.23113}}}
效率确实高了不少，不知道还有没提高的余地，尽管比不上无心人Delphi的速度。你的Mathematica用的一直很帅啊。

gxqcn · 发表于 2010-5-19 19:55:59

我觉得编码应尽量避免检验有没有“9”这个过程，因为这个检验过程不可避免地需要除法（包含求余）指令。
可采用构造法，比如利用：首位数字是1~8，其余位则可为0~8，这样直接可得到不含9的自然数，效率应该会大幅提高。

gxqcn · 发表于 2010-5-20 09:04:33

我写的程序代码，无检测是否含9的过程：

#include <stdio.h>
#include <time.h>
int main(int argc, char* argv[])
{
unsigned long i, j, v0, v9, d[9], m[9];
double s0, s9;
time_t sec;
d[0] = 1;
m[0] = 9;
for ( i=1; i<9; ++i )
{
d[i] = d[i-1] * 10;
m[i] = 9;
}
v9 = v0 = d[ i=0 ];
for ( ; i<9; ++i )
{
s9 = s0 = 0.0;
--m[i];
do
{
s0 += 1.0 / v0;
for ( ++v0, j=0; j<=i && 0==--m[j]; ++j )
{
v0 += d[j];
m[j] = 9;
}
while ( v0 != ++v9 )
{
s9 += 1.0 / v9;
}
} while ( j <= i );
time(&sec);
printf( "n = %u\t%.24s\n", i+1, ctime(&sec) );
printf( "s0 = %.15f\ns9 = %.15f\ns0/s9 = %.15f\ns0+s9 = %.15f\n\n", s0, s9, s0/s9, s0+s9 );
}
return 0;
}

复制代码

注：该程序在 56# 再次得到优化。

gxqcn · 发表于 2010-5-20 09:05:49

运行结果如下：

n = 1 Thu May 20 09:14:20 2010
s0 = 2.717857142857143
s9 = 0.111111111111111
s0/s9 = 24.460714285714285
s0+s9 = 2.828968253968254
n = 2 Thu May 20 09:14:20 2010
s0 = 2.053991622224917
s9 = 0.294417641446448
s0/s9 = 6.976455663912790
s0+s9 = 2.348409263671365
n = 3 Thu May 20 09:14:20 2010
s0 = 1.817871425200977
s9 = 0.489221917709748
s0/s9 = 3.715842155460231
s0+s9 = 2.307093342910725
n = 4 Thu May 20 09:14:20 2010
s0 = 1.633364212583175
s9 = 0.669670962910865
s0/s9 = 2.439054853869453
s0+s9 = 2.303035175494040
n = 5 Thu May 20 09:14:20 2010
s0 = 1.469783389239973
s9 = 0.832846704579078
s0/s9 = 1.764770612837813
s0+s9 = 2.302630093819051
n = 6 Thu May 20 09:14:20 2010
s0 = 1.322783057766752
s9 = 0.979806535235522
s0/s9 = 1.350045146870536
s0+s9 = 2.302589593002275
n = 7 Thu May 20 09:14:21 2010
s0 = 1.190502772693381
s9 = 1.112082770300745
s0/s9 = 1.070516336091988
s0+s9 = 2.302585542994125
n = 8 Thu May 20 09:14:23 2010
s0 = 1.071452317287522
s9 = 1.231132820706344
s0/s9 = 0.870297907152530
s0+s9 = 2.302585137993867
n = 9 Thu May 20 09:14:44 2010
s0 = 0.964307069526290
s9 = 1.338278027967131
s0/s9 = 0.720558097326824
s0+s9 = 2.302585097493420
Press any key to continue

复制代码

总共才24秒即运行结束！非常高效！

wayne · 发表于 2010-5-20 10:25:36

37# gxqcn
我在32楼用的也是这个方法~~

账号		自动登录	找回密码
密码			欢迎注册

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

评分