限制该程序以确定不包含零的整数倒数之和

发布于 2024-09-25 16:59:17 字数 907 浏览 5 评论 0原文

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

Let A denote the set of positive integers whose decimal representation does not contain the digit 0. The sum of the reciprocals of the elements in A is known to be 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, ...

Then take the reciprocal of each number, and sum the total.

How can this be verified numerically?

Write a computer program to verify this number.

Here is what I have written so far, I need help bounding this problem as this currently takes too long to complete:

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

如梦 2024-10-02 16:59:17

如果方法得当,这并不难。

例如,假设您要查找以 123 开头(即最左边的数字)并以 k 个非零数字结尾的所有整数的倒数总和。显然有 9k 这样的整数,并且每个整数的倒数都在 1/(124*10k) .. 1/(123*10< sup>k)。因此,所有这些整数的倒数之和以 (9/10)k/124 和 (9/10)k/123 为界。

要找到从 123 开始的所有倒数总和的界限,必须将每个 k>=0 的上述界限相加。这是一个几何级数,因此可以推导出从 123 开始的整数的倒数之和以 10*(9/10)k/124 和 10*(9/10)< 为界sup>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 系列

This is not that hard when approached properly.

Assume for example that you want to find the sum of reciprocals of all integers starting (i.e. the left-most digits) with 123 and ending with k non-zero digits. Obviously there are 9k such integers and the reciprocal of each of these integers is in the range 1/(124*10k) .. 1/(123*10k). Hence the sum of reciprocals of all these integers is bounded by (9/10)k/124 and (9/10)k/123.

To find bounds for sum of all reciprocals starting with 123 one has to add up the bounds above for every k>=0. This is a geometric serie, hence it can be derived that the sum of reciprocals of integers starting with 123 is bounded by 10*(9/10)k/124 and 10*(9/10)k/123.

The same method can of course be applied for any combination of left-most digits.
The more digits we examine on the left, the more accurate the result becomes.
Here is an implementation of this approach in 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

Calling approx(0, 8) for example gives the lower and upper bound:
23.103447707... and 23.103448107....
which is close to the claim 23.10345 given by the OP.

There are methods that converge faster to the sum in question, but they require more math.
A much better approximation of the sum can be found here. A generalization of the problem are the Kempner series.

榕城若虚 2024-10-02 16:59:17

对于大于某个阈值 N 的所有 current 值,1.0/(double)current 将足够小,使得 total > 不会因添加 1.0/(double)current 而增加。因此,终止标准应该是类似的,

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

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

For all values of current greater than some threshold N, 1.0/(double)current will be sufficiently small that total does not increase as a result of adding 1.0/(double)current. Thus, the termination criterion should be something like

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

instead of testing against the limit that is known a priori. Your loop will stop when current reaches this special value of N.

记忆里有你的影子 2024-10-02 16:59:17

我怀疑转换为字符串然后检查字符“0”是花费太长时间的步骤。如果您想避免全零,可能有助于增加当前

(已编辑 - 感谢 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 ) 等计算校正案例再

想一想,我发现整个问题有两个问题。一是你的目标数字 23.10345 很适合我的口味。毕竟,您要添加数千个具有无限十进制表示形式的项目,例如“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(或者也可以这样称呼),每次迭代都会保存一些 log10pow 计算。每一点点都有帮助——但仍然需要永远......

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

I suspect that casting to string and then checking for the character '0' is the step that takes too long. If you want to avoid all zeroes, might help to increase current thus:

(Edited -- thanks to Aaron McSmooth)

current++;  
for( int i = 10000000; i >= 10; i = i / 10 )  
{
    if ( current % i ) == 0
    {
         current = current + ( i / 10 );
    }
}

This is untested, but the concept should be clear: whenever you hit a multiple of a power of ten (e.g. 300 or 20000), you add the next lower power of 10 (in our examples 10 + 1 and 1000 + 100 + 10 + 1, respectively) until there are no more zeroes in your number.

Change your while loop accordingly and see if this doesn't help performance to the point were your problem becomes manageable.

Oh, and you might want to restrict the System.out output a bit as well. Would every tenth, one hundreth or 10000th iteration be enough?

Edit the second:
After some sleep, I suspect my answer might be a little short-sighted (blame the late hour, if you will). I simply hoped that, oh, one million iterations of current would get you to the solution and left it at that, instead of calculating the correction cases using log( current ) etc.

On second thought, I see two problems with this whole problem. One is that your target number of 23.10345 is a leeeeettle to round for my tastes. After all, you are adding thousands of items like "1/17", "1/11111" and so on, with infinite decimal representations, and it is highly unlikely that they add up to exactly 23.10345. If some specialist for numerical mathematics says so, fine -- but then I'd like to see the algorithm by which they arrived at this conclusion.

The other problem is related to the first and concerns the limited in-memory binary representation of your rational numbers. You might get by using BigDecimals, but I have my doubts.

So, basically, I suggest you reprogram the numerical algorithm instead of going for the brute force solution. Sorry.

Edit the third:
Out of curiosity, I wrote this in C++ to test my theories. It's run for 6 minutes now and is at about 14.5 (roughly 550 mio. iterations). We'll see.

Current version is

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;

Calculating currPowerCeiling (or however one might call this) by hand saves some log10 and pow calculations each iteration. Every little bit helps -- but it still takes forever...

Edit the fourth:
Status is around 66,000 mio iterations, total is up to 16.2583, runtime is at around 13 hours. Not looking good, Bobby S. -- I suggest a more mathematical approach.

最舍不得你 2024-10-02 16:59:17

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

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

How about storing the current number as a byte array where each array element is a digit 0-9? That way, you can detect zeroes very quickly (comparing bytes using == instead of String.contains).

The downside would be that you'll need to implement the incrementing yourself instead of using ++. You'll also need to devise a way to mark "nonexistent" digits so that you don't detect them as zeroes. Storing -1 for nonexistent digits sounds like a reasonable solution.

寻找一个思念的角度 2024-10-02 16:59:17

对于有符号的 32 位整数,该程序将永远不会停止。它实际上会收敛到-2097156。由于有符号 32 位整数的最大谐波数(从 1 到 N 的整数倒数之和)为 ~14.66,因此即使电流从 2 绕回,该循环也永远不会终止^31 - 1-2^31。由于最大负 32 位整数的倒数为 ~-4.6566e-10,因此每次 current 返回到 0 时,总和将为负数。假设 double 可以表示的最大数字,使得 number + + 1/2^31 == number2^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 的谐波数。

For a signed 32-bit integer, this program will never stop. It will actually converge towards -2097156. Since the maximum harmonic number (the sum of integral reciprocals from 1 to N) of a signed 32-bit integer is ~14.66, this loop will never terminate, even when current wraps around from 2^31 - 1 to -2^31. Since the reciprocal of the largest negative 32-bit integer is ~-4.6566e-10, every time current returns to 0, the sum will be negative. Given that the largest number representable by a double such that number + + 1/2^31 == number is 2^52/2^31, you get roughly -2097156 as the converging value.

Having said that, and assuming you don't have a direct way of calculating the harmonic number of an arbitrary integer, there are a few things you can do to speed up your inner loop. First, the most expensive operation is going to be System.out.println; that has to interact with the console in which case your program will eventually have to flush the buffer to the console (if any). There are cases where that may not actually happen, but since you are using that for debugging they are not relevant to this question.

However, you also spend a lot of time determining whether a number has a zero. You can flip that test around to generate ranges of integers such that within that range you are guaranteed not to have an integer with a zero digit. That is really simple to do incrementally (in C++, but trivial enough to convert to 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];
};

What the code above does is to iterate over every range of numbers such that the range only contains numbers without zeroes. It works by determining how to go from N000... to N111... and from N111... to (N+1)000..., carrying (N+1) into 1(0)000... if necessary.

On my laptop, I can generate the harmonic number of 2^31 - 1 in 8.73226 seconds.

心欲静而疯不止 2024-10-02 16:59:17
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;
    }
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;

     }
 }


}

This is an implementation using BitSet.I calculated the sum of reciprocal's for all integer's in range (1-Integer.MAX_VALUE/10).The sum comes upto 13.722766931560747.This is the maximum I could calculate using BitSet since the maximum range for BitSet is Integer.MAX_VALUE.I need to divide it by 10 and limit the range to avoid overflow.But there is significant improvement in speed.I'm just posting this code in-case it might give you some new idea to improve your code.(Increase your memory using the VM argument -Xmx[Size>350]m)

Output:

Total: 13.722766931560747
TimeTaken : 60382 ms

UPDATE:

Java Porting of a previous , deleted answer :

     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;
    }
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文