计算不包含零的倒数整数之和的程序边界确定。

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

-19 怎么会是正整数? - President James K. Polk
这是一项作业任务吗? - Mitch Dempsey
@GregS:它是收敛的,因为它是倒数的总和。 - Edmund
2
该总和确实收敛到23.10245。 - Bobby S
@GregS 我知道这个问题有点老了,但如果你找到那个问题的链接,能给我传一下吗?谢谢。 - Anonymous Pi
显示剩余5条评论
6个回答

8
这并不难,只要正确处理就可以了。
例如,假设您想找到以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, 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级数

+1:当面对这种问题时,拥有坚实的数学背景是非常棒的。感谢您提供的解决方案。 - tangens
任何试图将系列累加到浮点值“total”的方法最终都会尝试将一个小于“MACHINE_EPSILON * total”的值添加到“total”中,然后“total”将停止增长。要解决这个问题,需要使用像您所描述的分析方法才能得到有意义的解决方案。 - Philip Starhill
我试过你的程序,但它输出(1,1)。 - Emil
@Emil,我怀疑你正在使用旧版本的Python。任何低于3.0版本的Python都会将int/int计算为截断除法,而不是给出浮点结果。我稍微修改了程序,以便在3.0之前的版本中可以得到更好的结果,但我无法测试旧版本。 - Accipitridae

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输出。每十次、每百次或每10000次迭代是否足够?

第二次编辑: 经过一些睡眠,我怀疑我的答案可能有点短视(如果你愿意,可以把它归咎于深夜)。我只是希望,哦,一百万次current的迭代会让你得到解决方案,并且就此打住,而不是使用log(current)等来计算修正情况。

仔细想了想,我发现这个问题有两个问题。一个是你的目标数字23.10345对我来说有点太圆了。毕竟,你正在添加成千上万个像“1/17”、“1/11111”等具有无限小数表示的项目,它们很可能不会准确地加起来得到23.10345。如果某个数值数学专家这么说,那就好吧——但我想看看他们是如何得出这个结论的算法。

另一个问题与第一个问题有关,涉及到您的有理数的内存中的二进制表示的限制。您可以使用BigDecimals,但我有所怀疑。

因此,基本上,我建议您重新编写数值算法,而不是采用暴力解决方案。抱歉。

编辑第三个: 出于好奇,我用C++编写了这个程序来测试我的理论。现在已经运行了6分钟,大约是14.5(大约5.5亿次迭代)。我们将看到。

当前版本为

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百万次迭代,总共已达到16.2583,运行时间约为13小时。情况不太乐观,Bobby S. - 我建议采用更数学化的方法。


但是这个例子会达到101。在这种情况下,您还需要测试零。 - aaronasterling
谢谢,这似乎是有效的,直到我到达某个点时,我的数字开始减少。也许发生了某种溢出? - Bobby S
1
忽略值中带有小数位“0”的限制,1/n的总和在整数溢出之前不会达到23.10245。最少需要将“current”设置为长整型。然而,您可能需要完全使用另一个算法来计算此内容,因为您的“current”越大(特别是超过Integer.MAX_INT),它就会越慢地向收敛值取得进展。 - robert_x44
我从昨天开始的运行中已经到达了16.2244938002。我的外部循环已经执行了743,790,000次,而“current”为182,451,295,311。我想说C++更快。但我仍然想不出更好的方法来完成这个任务。 - aaronasterling
@AaronMcSmooth:好吧,消除每次迭代中的log10和pow计算确实有所帮助。但是现在情况仍然很糟糕,已经牢牢地陷入了无穷小的后山,再也没有希望到达神话般的23点多一些的领域。解决方案必须是更好的数值算法,而不是更好的暴力方法。 - Christian Severin

1
对于所有大于某个阈值 N 的 current 值,1.0/(double)current 的值会足够小,导致加上 1.0/(double)current 不会使 total 增加。因此,终止条件应该像这样:
 while(total != total + (1.0/(double)current))

不要测试已知的限制a priori,而是使用以下方法。当current达到特殊值N时,循环将停止。


谢谢你的建议,但这仍然不能解决我的边界问题。 我编写的程序无法在短时间内解决这个问题。 - Bobby S
@Bobby S 抱歉,我误解了“bounding”的含义,认为它是指“达到上限”,而不是“限制运行时间”。 - Philip Starhill

1
如何将当前数字存储为一个字节数组,其中每个数组元素都是0-9的数字?这样,您可以快速检测到零(使用 == 比较字节而不是 String.contains )。
缺点是您需要自己实现递增,而不能使用 ++ 。您还需要想出一种标记“不存在”数字的方法,以便不将它们检测为零。将 -1 存储为不存在的数字似乎是一个合理的解决方案。

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的最大范围是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;
    }

0
对于一个带符号的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...中来运行。
在我的笔记本电脑上,我可以在8.73226秒内生成2 ^ 31-1的谐波数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接