java - ゼロを含まない逆数整数の合計を決定するためにこのプログラムを制限する

Question

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

Answer 1

適切にアプローチすれば、これはそれほど難しいことではありません。

たとえば、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に近いものです。

問題の合計に速く収束する方法がありますが、より多くの計算が必要です。合計のはるかに良い近似はここで見つけることができます。問題の一般化はケンプナー級数です。

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。

（編集-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ああ、出力も少し制限したいかもしれません。10分の1、100分の1、または10000回の反復で十分でしょうか？

2番目の編集： 少し眠った後、私の答えは少し近視眼的かもしれないと思います（もしそうなら、遅い時間のせいにしてください）。などcurrentを使用して修正ケースを計算するのではなく、100万回の反復で解決策が得られ、そのままにしておくことを望んでいました。log( current )

考え直してみると、この問題全体に2つの問題があります。1つは、23.10345の目標数が、私の好みに合わせて丸めるのが難しいということです。結局のところ、「1/17」や「1/11111」などの数千のアイテムを無限の小数表現で追加しているので、合計が正確に23.10345になる可能性はほとんどありません。数値数学の専門家がそう言うなら、それでいいのですが、それなら、彼らがこの結論に到達したアルゴリズムを見たいと思います。

もう1つの問題は、最初の問題に関連しており、有理数の限られたメモリ内バイナリ表現に関係しています。BigDecimalsを使用することで得られるかもしれませんが、私には疑問があります。

したがって、基本的には、力ずくの解決策を採用するのではなく、数値アルゴリズムを再プログラムすることをお勧めします。ごめん。

3番目の編集： 好奇心から、理論をテストするためにこれを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

4番目の編集： ステータスは約66,000 mioの反復、合計は最大16.2583、実行時間は約13時間です。見栄えが悪い、ボビー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を使用した実装です。範囲内のすべての整数の逆数の合計を計算しました(1-Integer.MAX_VALUE/10)。合計は最大になります13.722766931560747。これは、BitSetの最大範囲がInteger.MAX_VALUEであるため、BitSetを使用して計算できる最大値です。 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;
    }

Answer 6

符号付き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ます。これはコンソールと対話する必要があります。その場合、プログラムは最終的にバッファをコンソールにフラッシュする必要があります（存在する場合）。それが実際には起こらない場合もありますが、デバッグに使用しているため、この質問には関係ありません。

ただし、数値にゼロがあるかどうかを判断するのにも多くの時間を費やします。そのテストを反転して整数の範囲を生成し、その範囲内で0桁の整数がないことが保証されるようにすることができます。これは、インクリメンタルに実行するのは本当に簡単です（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の調和数を生成できます。