java - BigIntegers 桁の分割

Question

大きな整数の桁を分割しようとしています。もう少し具体的にさせてください。フィボナッチ数列を使用して大きな整数を生成しています。このアルゴリズムを使用して、最初の 9 桁と最後の 9 桁がパンデジタルである BigInteger が見つかるまでループする必要があります。唯一の問題は、ループする必要がある量が 300K であることです (BigInteger が非常に巨大になるため)。

BigInteger を文字列に変換してから、「substring(begin, end)」を使用してみました。しかし、これは非常に遅く、100K のインデックスを作成するだけで 28 分近くかかりました。

これには数学的な解決策がありますが、それが何であるかは完全にはわかりません。誰かが私を正しい方向に導くことができれば、非常にありがたいです。注: 直接答えを求めているわけではありません。正しい答えを見つけるための一歩です。

あなたが疑問に思っている場合に備えて、ここに私のコードがあります：

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}

更新され、最初の 9 桁を生成する方法がわかりました (遅すぎないようです)。しかし、最後の 9 桁の生成に問題があります。

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            if (prev1.toString().length() > 19)
            {
                String leading9Digits = leading9Digits(prev1);
                if (isPanDigital(BigInteger.valueOf(Integer.valueOf(leading9Digits))))
                {
                    System.out.println("Solved at index: " + i);
                    break;
                }
            }
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    public static String leading9Digits(BigInteger x) {
        int log10 = (x.bitLength() - 1) * 3 / 10;
        x = x.divide(BigInteger.TEN.pow(Math.max(log10 + 1 - 9, 0)));
        return x.toString().substring(0, 9);
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}