绑定此程序以确定不包含零的倒数整数之和
设A表示正整数的集合，其十进制表示不包含数字0.A中元素的倒数之和已知为23.10345。
防爆。 1,2,3,4,5,6,7,8,9,11-19,21-29,31-39,41-49,51-59,61-69,71-79,81-89， 91-99,111-119，……
然后取每个数的倒数，并总计。
如何通过数字validation？
编写一个计算机程序来validation这个号码。
这是我到目前为止所写的内容，我需要帮助解决这个问题，因为这需要很长时间才能完成：
Java中的代码
import java.util.*; public class recip { public static void main(String[] args) { int current = 0; double total = 0; while(total < 23.10245) { if(Integer.toString(current).contains("0")) { current++; } else { total = total + (1/(double)current); current++; } System.out.println("Total: " + total); } } } 当正确接近时，这并不难。
例如，假设您要查找以123开始并以k非零数字结尾的所有整数的倒数之和（即最左边的数字）。 显然，存在9k个这样的整数，并且这些整数中的每一个的倒数在1 /（124 * 10k ）… 1 /（123 * 10k ）的范围内。 因此，所有这些整数的倒数之和受（9/10） k / 124和（9/10） k / 123的限制。
为了找到以123开始的所有倒数之和的界限，必须将每个k> = 0的上限加起来。 这是几何系列，因此可以推导出以123开始的整数倒数之和由10 *（9/10） k / 124和10 *（9/10） k / 123限定。
当然，相同的方法可以应用于最左边数字的任何组合。 我们在左侧检查的数字越多，结果就越准确。 这是python中这种方法的实现：
def approx(t,k): """Returns a lower bound and an upper bound on the sum of reciprocals of positive integers starting with t not containing 0 in its decimal representation. k is the recursion depth of the search, ie we append k more digits to t, before approximating the sum. A larger k gives more accurate results, but takes longer.""" if k == 0: return 10.0/(t+1), 10.0/t else: if t > 0: low, up = 1.0/t, 1.0/t else: low, up = 0, 0 for i in range(10*t+1, 10*t+10): l,u = approx(i, k-1) low += l up += u return low, up
例如，调用约（0,8）给出下限和上限：23.103447707 ……和23.103448107 ….这与OP给出的索赔23.10345很接近。
有些方法可以更快地收敛到所讨论的总和，但它们需要更多的数学运算。 可以在这里找到更好的近似值。 问题的一般化是肯普纳系列 。
对于大于某个阈值N所有current值， 1.0/(double)current将足够小，使得total不会因添加1.0/(double)current而增加。 因此，终止标准应该是这样的
while(total != total + (1.0/(double)current))
而不是针对先验已知的限制进行测试。 当current达到N特殊值时，您的循环将停止。
我怀疑转换为字符串然后检查字符’0’是一个耗时太长的步骤。 如果你想避免全零，可能有助于增加current ：
（编辑 – 感谢Aaron McSmooth）
current++; for( int i = 10000000; i >= 10; i = i / 10 ) { if ( current % i ) == 0 { current = current + ( i / 10 ); } }
这是未经测试的，但概念应该是明确的：每当你达到10的幂（例如300或20000）的倍数时，你添加下一个10的较低功率（在我们的例子中10 + 1和1000 + 100 + 10 + 1，分别）直到你的号码中没有更多的零。
相应地更改你的while循环，看看这是否有助于提高性能，你的问题是否易于管理。
哦，你可能也想限制System.out输出。 每十分之一，一个千分之一或第10000次迭代是否足够？
编辑第二个：经过一段时间的睡眠后，我怀疑我的回答可能有点短视（如果你愿意的话，可以归咎于迟到的时候）。 我只是希望，哦，百万次迭代的current会让你得到解决方案并将其留在那里，而不是使用log( current )等来计算校正情况。
再想一想，我发现整个问题存在两个问题。 一个是你的目标数量23.10345是一个leeeeettle圆我的口味。 毕竟，你正在添加数千个项目，如“1/17”，“1/11111”等等，带有无限的十进制表示，并且它们极不可能完全相加到23.10345。 如果一些数学数学专家这么说，那很好 – 但我希望看到他们得出这个结论的算法。
另一个问题与第一个问题有关，并且涉及有理数的有限内存二进制表示。 你可能会使用BigDecimals ，但我有疑虑。
所以，基本上，我建议你重新编程数值算法，而不是去蛮力解决方案。 抱歉。
编辑第三个：出于好奇，我用C ++编写了这个来测试我的理论。 它现在运行6分钟，大约是14.5（大约550 mio。迭代）。 我们拭目以待。
目前的版本是
double total = 0; long long current = 0, currPowerCeiling = 10, iteration = 0; while( total < 23.01245 ) { current++; iteration++; if( current >= currPowerCeiling ) currPowerCeiling *= 10; for( long long power = currPowerCeiling; power >= 10; power = power / 10 ) { if( ( current % power ) == 0 ) { current = current + ( power / 10 ); } } total += ( 1.0 / current ); if( ! ( iteration % 1000000 ) ) std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl; } std::cout << current << "\t" << total << std::endl;
currPowerCeiling计算currPowerCeiling （或者可能会调用它）可以在每次迭代时保存一些log10和pow计算。 每一点点都有帮助 - 但它仍然需要永远......
编辑第四个：状态是大约66,000 mio迭代，总计最多16.2583，运行时间大约是13个小时。 看起来不太好，Bobby S. - 我建议采用更多的数学方法。
如何将当前数字存储为每个数组元素为0-9的字节数组？ 这样，您可以非常快速地检测零（使用==而不是String.contains比较字节）。
缺点是你需要自己实现增量而不是使用++ 。 您还需要设计一种方法来标记“不存在的”数字，这样您就不会将它们检测为零。 为不存在的数字存储-1听起来像是一个合理的解决方案。
对于带符号的32位整数，该程序永远不会停止。 它实际上会朝-2097156 。 由于有符号32位整数的最大谐波数（从1到N的积分倒数之和）是~14.66 ，因此即使当前电流从2^31 - 1到-2^31时，该循环也永远不会终止。 由于最大负32位整数的倒数为〜-4.6666e-10，因此每次电流返回0 ，总和将为负。 假设可以用double表示的最大数字使得number + + 1/2^31 == number是2^52 -2097156 2^31 ，则得到大约-2097156作为收敛值。
话虽如此，假设您没有直接计算任意整数的谐波数的方法，您可以采取一些措施来加速内循环。 首先，最昂贵的操作是System.out.println ; 必须与控制台交互，在这种情况下，程序最终必须将缓冲区刷新到控制台（如果有的话）。 有些情况下可能实际上不会发生，但由于您使用它进行调试，因此与此问题无关。
但是，您还要花很多时间来确定数字是否为零。 您可以翻转该测试以生成整数范围，以便在该范围内保证不具有零数字的整数。 这是非常简单的逐步增加（在C ++中，但足以转换为Java）：
class c_advance_to_next_non_zero_decimal { public: c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0) { std::fill_n(digits, digit_count, 0); return; } int advance_to_next_non_zero_decimal() { assert((next % 10) == 0); int offset= 1; digits[0]+= 1; for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10) { if (digits[digit_index]==0) { digits[digit_index]= 1; offset+= digit_value; } } next+= offset; return next; } int advance_to_next_zero_decimal() { assert((next % 10)!=0); assert(digits[0]==(next % 10)); int offset= 10 - digits[0]; digits[0]+= offset; assert(digits[0]==10); // propagate carries forward for (int digit_index= 0; digits[digit_index]==10 && digit_index
上面的代码是迭代每个数字范围，使得范围只包含没有零的数字。 它的工作原理是确定如何从N000 ...到N111 ...以及从N111 ...到（N + 1）000 ...，携带（N + 1）到1（0）000 ...如果必要。
在我的笔记本电脑上，我可以在8.73226秒内生成2 ^ 31 - 1的谐波数。
public class SumOfReciprocalWithoutZero { public static void main(String[] args) { int maxSize=Integer.MAX_VALUE/10; long time=-System.currentTimeMillis(); BitSet b=new BitSet(maxSize); setNumbersWithZeros(10,maxSize,b); double sum=0.0; for(int i=1;i=100) setInbetween(j, b); } } static void setInbetween(int strt,BitSet b) { int bitToSet; bitToSet=strt; for(int i=1;i<=10;i++) { int nxtInt=-1; while((nxtInt=b.nextSetBit(nxtInt+1))!=strt) { b.set(bitToSet+nxtInt); } nxtInt=-1; int lim=strt/10; while((nxtInt=b.nextClearBit(nxtInt+1))
这是一个使用BitSet的实现。我计算了范围内所有整数的倒数之和(1-Integer.MAX_VALUE/10) 。总和达到13.722766931560747 .这是我用BitSet计算的最大值，因为BitSet的最大范围是Integer.MAX_VALUE.I需要将其除以10并限制范围以避免溢出。但速度有显着提高。我只是发布此代码，以便它可能会给你一些改进代码的新想法。（使用VM参数增加内存-Xmx[Size>350]m ）
输出：
Total: 13.722766931560747 TimeTaken : 60382 ms
更新：
Java移植先前删除的答案：
public static void main(String[] args) { long current =11; double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9; long i=0; while(true) { current=next_current(current); if(i%10000!=0) System.out.println(i+" "+current+" "+tot); for(int j=0;j<9;j++) { tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) + 1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8)); current += 10; } i++; } } static long next_current(long n){ long m=(long)Math.pow(10,(int)Math.log10(n)); boolean found_zero=false; while(m>=1) { if(found_zero) n+=m; else if((n/m)%10==0) { n=n-(n%m)+m; found_zero=true; } m=m/10; } return n; }