Jak szybko możemy znaleźć wszystkie kombinacje czterech kwadratów, które sumują się do N?

Pytanie zostało zadane w Stack Overflow ( tutaj ):

Biorąc pod uwagę całkowitą wydrukować wszystkie możliwe kombinacje wartości całkowitych z i dzięki którym rozwiązuje się równanie .$N$$A,B,C$$D$$A^2+B^2+C^2+D^2 = N$

To pytanie jest oczywiście związane z hipotezą Bacheta w teorii liczb (czasami nazywaną twierdzeniem Four Square Lagrange'a z powodu jego dowodu). Istnieje kilka artykułów, które dyskutują o tym, jak znaleźć pojedyncze rozwiązanie, ale nie byłem w stanie znaleźć niczego, co mówi o tym, jak szybko możemy znaleźć wszystkie rozwiązania dla konkretnego (to znaczy wszystkie kombinacje , nie wszystkie permutacje ).$N$

Długo o tym myślałem i wydaje mi się, że można to rozwiązać w czasie i przestrzeni , gdzie jest pożądaną sumą. Jednak bez wcześniejszych informacji na ten temat nie jestem pewien, czy jest to znaczące roszczenie z mojej strony, czy tylko trywialny, oczywisty lub już znany wynik.$O(N)$$N$

Pytanie zatem brzmi: jak szybko możemy znaleźć wszystkie Kwadraty Czterech Kwadratów dla danego ?$N$

OK, oto algorytm (prawie) O (N), o którym myślałem. Dwie pierwsze funkcje pomocnicze, funkcja najbliższego pierwiastka z liczby całkowitej:

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

I funkcja zwracająca wszystkie pary TwoSquare sumujące od 0 do 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;
    }

Wreszcie sam algorytm:

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

Jak powiedziałem wcześniej, powinno być dość blisko O (N), jak jednak zauważa Yuval Filmus, ponieważ liczba rozwiązań Four Square dla N może być uporządkowana (Nnnn N), to algorytm nie może być mniej niż to.

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

$\Omega(N\log\log N)$$N$$8\sigma(N)$$\sigma(N) \geq (e^\gamma - \epsilon) N\log\log N$

$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, Randomized Algorytmy w teorii liczb , Communications on Pure and Applied Mathematics 39 (1986), no. S1, ss. S239 – S256 .

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