Quão rápido podemos encontrar todas as combinações de quatro quadrados que somam N?

12

Uma pergunta foi feita no Stack Overflow ( aqui ):

Dado um número inteiro N , imprimir todas as combinações possíveis de valores de número inteiro de A,B,C e D que resolvem a equação A2+B2+C2+D2=N .

Essa questão está obviamente relacionada à conjectura de Bachet na teoria dos números (às vezes chamada de Teorema dos Quatro Quadrados de Lagrange por causa de sua prova). Existem alguns artigos que discutem como encontrar uma solução única, mas não consegui encontrar nada que fale sobre a rapidez com que podemos encontrar todas as soluções para um específico N(ou seja, todas as combinações , nem todas as permutações ).

Eu estive pensando sobre isso um pouco e parece-me que pode ser resolvido em tempo e espaço, onde N é a soma desejada. No entanto, na falta de informações prévias sobre o assunto, não tenho certeza se essa é uma reivindicação significativa da minha parte ou apenas um resultado trivial, óbvio ou já conhecido.O(N)N

Portanto, a questão é: com que rapidez podemos encontrar todas as somas de quatro quadrados para um dado ?N


OK, aqui está o algoritmo (quase) O (N) em que eu estava pensando. Primeiras duas funções de suporte, uma função de raiz quadrada inteira mais próxima:

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

E uma função para retornar todos os pares TwoSquare somando de 0 a 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;
    }

Finalmente, o próprio algoritmo:

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

Como eu disse antes, deve ser bem próximo de O (N), no entanto, como Yuval Filmus aponta, como o número de soluções quadradas de N pode ser de ordem (N ln ln N), esse algoritmo não pode ser menos que isso.

RBarryYoung
fonte
Sim, por favor poste. Ainda estou desenvolvendo os detalhes do algoritmo linear, mas tenho certeza de que é válido.
usar o seguinte código
5
Ω(NloglogN)O(N)
1
i=0N/2|hiListNi||loListi|
Sim, está correto, no entanto, sua fórmula está um pouco errada, porque o primeiro i varia de 0 a aprox. N PI / 8 e, em segundo, apenas uma fração dos valores de i satisfazem hiList (Ni) + loList (i) = N, portanto, nem todos são adicionados. De qualquer forma, não há como corrigir isso e eu sou bonita verifique se isso oferece a complexidade mínima possível de O (N log (log (N))).
usar o seguinte código
Mas podemos ter um algoritmo que é executado em O (max (N, "número de soluções")), ocupando O (n) espaço.
precisa saber é o seguinte

Respostas:

15

O(N)A,BNM=A2+B2N(A,B)TNMM,NMT

Ω(NloglogN)N8σ(N)σ(N)(eγϵ)NloglogN

N

Yuval Filmus
fonte
Hmm, a coisa do encontro no meio parece muito semelhante ao que eu estou trabalhando (quase pronto), que é um algoritmo Merge-Match ascendente / descendente sobre os pares TwoSquare. Isso soa igual?
usar o seguinte código
1
Provavelmente é o mesmo, encontrar-se no meio é uma heurística tão comum que deve ter muitos nomes diferentes.
Yuval Filmus
σ(N)
σ(N)ο(N)
1
A soma dos divisores funciona de fato.
Yuval Filmus
5

o(N2)A,B,C,DNO(N2)

O(log2n)O(log2nloglogn)


[1] MO Rabin, JO Shallit, Algoritmos Randomizados em Teoria dos Números , Comunicação sobre Matemática Pura e Aplicada 39 (1986), n. S1, pp. S239 – S256 .

Juho
fonte
Para um algoritmo trivial, você só precisa de loops para A, B e C e, em seguida, calcula D e verifica se é um número inteiro. Se você precisar de A ≤ B ≤ C ≤ D, deverá obter O (N ^ 1,5) com uma constante bastante pequena.
precisa saber é o seguinte
Cerca de 0,04 N ^ 1,5 triplica (A, B, C), e verificar se N - A ^ 2 - B ^ 2 - C ^ 2 é um quadrado pode ser feito muito rapidamente.
precisa saber é o seguinte
-2

O número de soluções é exatamente 8d, Onde d passa por todos os divisores de nque não são múltiplos de 4. Este é um teorema de Jacobi.

hóspede
fonte
1
E como isso responde à pergunta? A tarefa é dar todos esses quádruplos!
Raphael
1
This is already mentioned in my answer.
Yuval Filmus