7

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, ...

然后取每个数字的倒数,并求和。

如何在数字上验证这一点?

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

这是我到目前为止所写的内容,我需要帮助来解决这个问题,因为这目前需要很长时间才能完成:

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);
        }
    }
}
4

6 回答 6

8

如果处理得当,这并不难。

例如,假设您要查找以 123 开头(即最左边的数字)并以 k 个非零数字结尾的所有整数的倒数之和。显然有 9 k个这样的整数,每个整数的倒数都在 1/(124*10 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

例如,调用 approx(0, 8) 给出下限和上限:23.103447707... 和 23.103448107...。这与 OP 给出的权利要求 23.10345 接近。

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

于 2010-10-04T19:04:58.203 回答
1

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

缺点是您需要自己实现递增而不是使用++. 您还需要设计一种方法来标记“不存在”的数字,这样您就不会将它们检测为零。存储-1不存在的数字听起来是一个合理的解决方案。

于 2010-10-04T05:44:50.670 回答
1

对于current大于某个阈值的所有值N1.0/(double)current将足够小,total不会因为相加而增加1.0/(double)current。因此,终止标准应该类似于

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

而不是针对先验已知的限制进行测试。current当达到这个特殊值时,您的循环将停止N

于 2010-10-02T21:41:54.987 回答
1

我怀疑转换为字符串然后检查字符“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稍微限制输出。每十分之一、百分之一或一万次迭代就足够了吗?

编辑第二个: 睡了一会儿,我怀疑我的回答可能有点短视(如果你愿意,请怪罪到晚了)。我只是希望,哦,一百万次迭代current可以让你找到解决方案并将其留在那个地方,而不是使用log( current )etc来计算更正案例。

再想一想,我发现整个问题有两个问题。一个是你的目标数字 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(或者人们可能称之为)可以节省一些log10pow每次迭代的计算。每一点都有帮助 - 但它仍然需要永远......

编辑第四个: 状态约为 66,000 次 mio 迭代,总计高达 16.2583,运行时间约为 13 小时。看起来不太好,Bobby S.——我建议采用更数学的方法。

于 2010-10-02T22:47:10.730 回答
0
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 的实现。我计算了范围内所有整数的倒数之和(1-Integer.MAX_VALUE/10)。总和达到13.722766931560747。这是我可以使用 BitSet 计算的最大值,因为 BitSet 的最大范围是 Integer.MAX_VALUE。我需要将其除以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;
    }
于 2010-10-04T12:16:05.630 回答
0

对于一个有符号的 32 位整数,这个程序永远不会停止。它实际上会向 收敛-2097156。由于有符号 32 位整数的最大谐波数(从 1 到 N 的整数倒数之和)为,因此即使电流从到~14.66回绕,该循环也永远不会终止。由于最大负 32 位整数的倒数是 ~-4.6566e-10,因此每次电流返回到时,总和将为负数。鉴于由/表示的最大数,您大致得到收敛值。2^31 - 1-2^310doublenumber + + 1/2^31 == number2^522^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... 如果必要的。

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

于 2010-10-04T21:11:41.197 回答