包围盒此程序，以确定未包含零

Question

倒数整数的和让甲表示该组正整数，其十进制表示不包含数字0的元素的倒数之和在A的已知是23.10345。

Ex。 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，...

然后取每个数的倒数，并总和。

这怎么可以数字验证？

编写一个计算机程序来验证这个数字。

这是我到目前为止写的，我需要帮助边界这个问题，因为目前这需要很长时间才能完成：

代码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); 
     } 
    } 
} 

Answer 1

这不是th在正确接近时很难。

例如，假设您想要查找以123开头并以k个非零数字结尾的所有整数开始的倒数（即最左边的数字）的和。显然有这样的整数，并且这些整数中的每一个的倒数在1 /（124 * 1^k）1 /（123 * 10 ^k）的范围内。因此，所有这些整数的倒数和以（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, i.e. 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。

有些方法可以更快地收敛到所讨论的总和，但它们需要更多的数学。 总和的更好的近似值可以找到here。这个问题的一般化是Kempner series。

Answer 2

对于所有值current大于某个阈值N,1.0/(double)current将足够小，以致total不会因增加1.0/(double)current而增加。因此，终止准则应该是这样的

while(total != total + (1.0/(double)current)) 

，而不是测试针对的是被称为先验极限。当current达到此特殊值N时，您的循环将停止。

Answer 3

我怀疑铸造字符串然后检查字符'0​​'是需要太长时间的步骤。如果你想避免全零，可能有助于提高current这样的：

（编辑 - 感谢阿龙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的输出。每十分之一，十分之一还是第一万次迭代就足够了？

编辑第二： 睡觉后，我怀疑我的回答可能是有点短视（怪晚的时候，如果你愿意）。我只是希望，current的一百万次迭代可以让你找到解决方案并将其留在那里，而不是使用log(current)等计算校正案例。

第二个想法，我看到了这个问题的两个问题。一个是你的目标数字23.10345是一个leeeeettle四舍五入我的口味。毕竟，您要添加成千上万的项目，例如“1/17”，“1/11111”等，并且具有无限的小数表示形式，并且它们加起来非常不可能精确到23.10345。如果一些数学数学专家这样说，那么很好 - 但我希望看到他们得出这个结论的算法。

另一个问题与第一个有关，并且涉及有限数量的内存二进制表示。你可能会通过使用BigDecimals，但我有我的疑惑。因此，基本上，我建议你重新编程数值算法，而不是去寻求蛮力解决方案。抱歉。

编辑第三个： 出于好奇，我用C++写了这个测试我的理论。它现在运行了6分钟，大约14.5（大约550万次迭代）。我们拭目以待。

当前版本是

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（或一个不过可能于召本）用手节省一些log10和pow计算每次迭代。每一点帮助 - 但它仍然需要永远...

编辑第四： 状态大约是66000 MIO迭代，共达16.2583，运行时间约为13小时。看起来不错，Bobby S. - 我建议更多的数学方法。

Answer 4

如何将当前数字存储为字节数组，其中每个数组元素是数字0-9？这样，您可以非常快速地检测零（使用==而不是String.contains来比较字节）。

不利的一面是，您需要实现自己增量而不是使用++。您还需要设计一种标记“不存在”数字的方法，以便您不会将它们检测为零。对于不存在的数字，存储-1听起来像是一个合理的解决方案。

Answer 5

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<maxSize;i++) 
    { 
     if(!b.get(i)) 
     { 
      sum+=1.0d/(double)i; 
     } 
    } 
    time+=System.currentTimeMillis(); 
    System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms"); 


} 

static void setNumbersWithZeros(int srt,int end,BitSet b) 
{ 
     for(int j=srt;j<end;j*=10) 
     { 
      for(int i=1;i<=10;i++) 
     { 
      int num=j*i; 
      b.set(num); 
     } 
      if(j>=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))<lim) 
    { 
     b.set(bitToSet+nxtInt); 
    } 

    bitToSet=strt*i; 

    } 
} 


} 

这是使用BitSet.I的实施范围(1-Integer.MAX_VALUE/10)计算倒数的总和为全部整数的.The总和来高达13.722766931560747。这是我可以计算出使用的BitSet以来最大范围的BitSet是整数最大.MAX_VALUE.I需要将它除以10，并限制范围以避免溢出。但速度显着提高。我只是发布此代码以防万一它可能会给您一些新的想法来改进您的代码。（增加使用VM参数-Xmx[Size>350]m你的记忆）

输出：

Total: 13.722766931560747 
TimeTaken : 60382 ms 

UPDATE：

的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; 
    } 

Answer 6

对于一个有符号的32位整数，这个程序永远不会停止。它实际上会收敛到-2097156。由于有符号的32位整数的最大谐波数（从1到N的整数倒数之和）为~14.66，因此即使当前电流从2^31 - 1回到-2^31时，该回路也不会终止。由于最大的负32位整数的倒数为〜-4.6566e-10，因此每次电流返回到0时，总和将为负。考虑到double所代表的最大数字，即number + + 1/2^31 == number为2^52/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<digit_count; ++digit_index) 
     { 
      digits[digit_index]= 0; 
      digits[digit_index + 1]+= 1; 

      max_set_digit_index= max(digit_index + 1, max_set_digit_index); 
     } 

     next+= offset; 
     return next; 
    } 

private: 
    int next; 

    static const size_t digit_count= 10; // log10(2**31) 

    int max_set_digit_index; 

    int digits[digit_count]; 
}; 

什么上面的代码所做的是数字的每一个范围内迭代使得范围仅包含数字没有零。它通过确定如何从N000 ...到N111 ...以及从N111 ...到（N + 1）000 ...，将（N + 1）运载到1（0）000 ... if必要。

在我的笔记本电脑上，我可以在8.73226秒内生成2^31 - 1的谐波数。