Seberapa cepat kita dapat menemukan semua kombinasi Four-Square yang berjumlah N?

Sebuah pertanyaan diajukan di Stack Overflow (di sini ):

Dengan bilangan bulat , cetak semua kemungkinan kombinasi nilai integer A , B , C dan D yang menyelesaikan persamaan A 2 + B 2 + C 2 + D $N$$A,B,C$$D$ .$A^2+B^2+C^2+D^2 = N$

Pertanyaan ini tentu saja terkait dengan dugaan Bachet dalam teori bilangan (kadang-kadang disebut Lagrange's Four Square Theorem karena buktinya). Ada beberapa makalah yang membahas bagaimana menemukan solusi tunggal, tetapi saya tidak dapat menemukan apa pun yang berbicara tentang seberapa cepat kita dapat menemukan semua solusi untuk suatu solusi tertentu.(yaitu, semuakombinasi, tidak semuapermutasi).$N$

Saya telah memikirkannya sedikit dan menurut saya hal itu dapat diselesaikan dalam ruang dan waktu , di mana N adalah jumlah yang diinginkan. Namun, karena tidak ada informasi sebelumnya tentang masalah ini, saya tidak yakin apakah itu merupakan klaim signifikan pada bagian saya atau hanya hasil yang sepele, jelas atau sudah diketahui.$O(N)$$N$

Jadi, pertanyaannya adalah, seberapa cepat kita dapat menemukan semua Jumlah Empat-Kuadrat untuk diberikan ?$N$

OK, inilah algoritma (hampir) O (N) yang saya pikirkan. Dua fungsi pendukung pertama, fungsi akar kuadrat integer terdekat:

    // the nearest integer whose square is less than or equal to N
    public int SquRt(int N)
    {
        return (int)Math.Sqrt((double)N);
    }

Dan fungsi untuk mengembalikan semua pasangan TwoSquare yang menjumlahkan dari 0 ke N:

    // Returns a list of all sums of two squares less than or equal to N, in order.
    public List<List<int[]>> TwoSquareSumsLessThan(int N)
    {
        //Make the index array
        List<int[]>[] Sum2Sqs = new List<int[]>[N + 1];

        //get the base square root, which is the maximum possible root value
        int baseRt = SquRt(N);

        for (int i = baseRt; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                int sum = (i * i) + (j * j);
                if (sum > N)
                {
                    break;
                }
                else
                {
                    //make the new pair
                    int[] sumPair = { i, j };
                    //get the sumList entry
                    List<int[]> sumLst;
                    if (Sum2Sqs[sum] == null)
                    {   
                        // make it if we need to
                        sumLst = new List<int[]>();
                        Sum2Sqs[sum] = sumLst;
                    }
                    else
                    {
                        sumLst = Sum2Sqs[sum];
                    }
                    // add the pair to the correct list
                    sumLst.Add(sumPair);
                }
            }
        }

        //collapse the index array down to a sequential list
        List<List<int[]>> result = new List<List<int[]>>();
        for (int nn = 0; nn <= N; nn++)
        {
            if (Sum2Sqs[nn] != null) result.Add(Sum2Sqs[nn]);
        }

        return result;
    }

Akhirnya, algoritma itu sendiri:

    // Return a list of all integer quads (a,b,c,d), where:
    //      a^2 + b^2 + c^2 + d^2 = N,
    // and  a >= b >= c >= d,
    // and  a,b,c,d >= 0
    public List<int[]> FindAllFourSquares(int N)
    {
        // get all two-square sums <= N, in descending order
        List<List<int[]>> Sqr2s = TwoSquareSumsLessThan(N);

        // Cross the descending list of two-square sums <= N with
        // the same list in ascending order, using a Merge-Match
        // algorithm to find all combinations of pairs of two-square
        // sums that add up to N
        List<int[]> hiList, loList;
        int[] hp, lp;
        int hiSum, loSum;
        List<int[]> results = new List<int[]>();
        int prevHi = -1;
        int prevLo = -1;

        //  Set the Merge sources to the highest and lowest entries in the list
        int hi = Sqr2s.Count - 1;
        int lo = 0;

        //  Merge until done ..
        while (hi >= lo)
        {
            // check to see if the points have moved
            if (hi != prevHi)
            {
                hiList = Sqr2s[hi];
                hp = hiList[0];     // these lists cannot be empty
                hiSum = hp[0] * hp[0] + hp[1] * hp[1];
                prevHi = hi;
            }
            if (lo != prevLo)
            {
                loList = Sqr2s[lo];
                lp = loList[0];     // these lists cannot be empty
                loSum = lp[0] * lp[0] + lp[1] * lp[1];
                prevLo = lo;
            }

            // do the two entries' sums together add up to N?
            if (hiSum + loSum == N)
            {
                // they add up, so cross the two sum-lists over each other
                foreach (int[] hiPair in hiList)
                {
                    foreach (int[] loPair in loList)
                    {
                        // make a new 4-tuple and fill it
                        int[] quad = new int[4];
                        quad[0] = hiPair[0];
                        quad[1] = hiPair[1];
                        quad[2] = loPair[0];
                        quad[3] = loPair[1];

                        // only keep those cases where the tuple is already sorted
                        //(otherwise it's a duplicate entry)
                        if (quad[1] >= quad[2]) //(only need to check this one case, the others are implicit)
                        {
                            results.Add(quad);
                        }
                        //(there's a special case where all values of the 4-tuple are equal
                        // that should be handled to prevent duplicate entries, but I'm
                        // skipping it for now)
                    }
                }
                // both the HI and LO points must be moved after a Match
                hi--;
                lo++;
            }
            else if (hiSum + loSum < N)
            {
                lo++;   // too low, so must increase the LO point
            }
            else    // must be > N
            {
                hi--;   // too high, so must decrease the HI point
            }
        }
        return results;
    }

Seperti yang saya katakan sebelumnya, itu harus cukup dekat dengan O (N), namun, seperti yang Yuval Filmus tunjukkan, karena jumlah solusi Four Square untuk N dapat menjadi urutan (N ln ln N), maka algoritma ini tidak dapat kurang dari itu.

$O(N)$$A,B \leq \sqrt{N}$$M=A^2+B^2 \leq N$$(A,B)$$T$$N$$M$$M,N-M$$T$ tidak kosong.

$\Omega(N\log\log N)$$N$$8\sigma(N)$$\sigma(N) \geq (e^\gamma - \epsilon) N\log\log N$ teorema Grönwall ).

$N$

$o(N^2)$$A,B,C,D \leq \sqrt[]{N}$$O(N^2)$

$O(\log^2 n)$$O(\log^2 n \log \log n)$

[1] MO Rabin, JO Shallit, Algoritma Acak dalam Teori Bilangan , Komunikasi tentang Matematika Murni dan Terapan 39 (1986), no. S1, hal. S239 – S256 .

$8\sum d$$d$$n$