¿Qué tan rápido podemos encontrar todas las combinaciones de cuatro cuadrados que sumen N?

12

Se hizo una pregunta en Stack Overflow ( aquí ):

Dado un número entero , imprimir todas las combinaciones posibles de valores enteros de A , B , C y D que resolver la ecuación A 2 + B 2 + C 2 + D 2 = N .NA,B,CDA2+B2+C2+D2=N

Por supuesto, esta pregunta está relacionada con la Conjetura de Bachet en la teoría de números (a veces llamada Teorema de los cuatro cuadrados de Lagrange debido a su prueba). Hay algunos documentos que discuten cómo encontrar una solución única, pero no he podido encontrar nada que hable sobre qué tan rápido podemos encontrar todas las soluciones para un particular (es decir, todas las combinaciones , no todas las permutaciones ).N

Lo he estado pensando bastante y me parece que se puede resolver en tiempo y espacio, donde N es la suma deseada. Sin embargo, al carecer de información previa sobre el tema, no estoy seguro de si es un reclamo significativo de mi parte o simplemente un resultado trivial, obvio o ya conocido.O(N)N

Entonces, la pregunta es, ¿qué tan rápido podemos encontrar todas las sumas de cuatro cuadrados para un dado ?N


OK, aquí está el algoritmo (casi) O (N) en el que estaba pensando. Primeras dos funciones de soporte, una función de raíz cuadrada entera más cercana:

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

Y una función para devolver todos los pares TwoSquare que suman 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, el algoritmo mismo:

    // 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 dije antes, debería estar bastante cerca de O (N), sin embargo, como señala Yuval Filmus, ya que el número de soluciones de cuatro cuadrados a N puede ser de orden (N ln ln N), entonces este algoritmo no podría ser menos que eso.

RBarryYoung
fuente
Sí, por favor publícalo. Todavía estoy desarrollando los detalles del algoritmo lineal, pero estoy bastante seguro de que es válido.
RBarryYoung
55
Ω(NloglogN)O(N)
1
i=0N/2|hiListNi||loListi|
Sí, eso es correcto, sin embargo, su fórmula está un poco apagada porque primero i varía de 0 a apprx. N PI / 8, y en segundo lugar solo una fracción de los valores de i satisfizo hiList (Ni) + loList (i) = N, por lo que no se agregan todos. En cualquier caso, no hay forma de arreglar esto y estoy bastante asegúrese de que esto proporcione la mínima complejidad posible de O (N log (log (N))).
RBarryYoung
Pero podemos tener un algoritmo que se ejecute en O (max (N, "número de soluciones")), tomando espacio O (n).
gnasher729

Respuestas:

15

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

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

N

Yuval Filmus
fuente
Hmm, la cosa de encuentro en el medio suena muy similar a lo que estoy trabajando (casi hecho), que es un algoritmo de combinación de combinación ascendente / descendente sobre los pares TwoSquare. ¿Suena igual?
RBarryYoung
1
Probablemente sea lo mismo, encontrarse en el medio es una heurística tan común que debe tener muchos nombres diferentes.
Yuval Filmus
σ(N)
σ(N)ο(N)
1
La suma de divisores funciona de hecho.
Yuval Filmus
5

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

O(log2n)O(log2nloglogn)


[1] MO Rabin, JO Shallit, Algoritmos aleatorios en teoría de números , Comunicaciones sobre matemática pura y aplicada 39 (1986), no. S1, págs. S239 – S256 .

Juho
fuente
Para un algoritmo trivial, solo necesita bucles para A, B y C y luego calcula D y verifica que sea un número entero. Si necesita A ≤ B ≤ C ≤ D, debería obtener O (N ^ 1.5) con una constante bastante pequeña.
gnasher729
Aproximadamente 0.04 N ^ 1.5 triples (A, B, C), y verificar que N - A ^ 2 - B ^ 2 - C ^ 2 es un cuadrado se puede hacer muy rápidamente.
gnasher729
-2

8ddn

invitado
fuente
1
¿Y cómo responde esto a la pregunta? ¡La tarea es dar todos estos cuádruples!
Raphael
1
Esto ya se menciona en mi respuesta.
Yuval Filmus