À quelle vitesse pouvons-nous trouver toutes les combinaisons de quatre carrés qui résument à N?

12

Une question a été posée à Stack Overflow ( ici ):

Compte tenu d' un nombre entier , imprimer toutes les combinaisons possibles des valeurs entières de et qui résolvent l'équation .A , B , C D A 2 + B 2 + C 2 + D 2 = NNA,B,CDA2+B2+C2+D2=N

Cette question est bien sûr liée à la conjecture de Bachet en théorie des nombres (parfois appelée théorème des quatre carrés de Lagrange en raison de sa preuve). Il y a des articles qui expliquent comment trouver une solution unique, mais je n'ai pas pu trouver quoi que ce soit qui parle de la vitesse à laquelle nous pouvons trouver toutes les solutions pour un particulier (c'est-à-dire toutes les combinaisons , pas toutes les permutations ).N

J'y ai beaucoup réfléchi et il me semble que cela peut être résolu dans le temps et l'espace O(N) , où N est la somme souhaitée. Cependant, faute d'informations préalables sur le sujet, je ne sais pas s'il s'agit d'une revendication significative de ma part ou simplement d'un résultat trivial, évident ou déjà connu.

Donc, la question est alors, à quelle vitesse pouvons-nous trouver toutes les sommes des quatre carrés pour un N donné N?


OK, voici l'algorithme (presque) O (N) auquel je pensais. Deux premières fonctions de support, une fonction de racine carrée entière la plus proche:

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

Et une fonction pour renvoyer toutes les paires TwoSquare sommant de 0 à 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;
    }

Enfin, l'algorithme lui-même:

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

Comme je l'ai déjà dit, il devrait être assez proche de O (N), cependant, comme le souligne Yuval Filmus, car le nombre de solutions à quatre carrés de N peut être d'ordre (N ln ln N), alors cet algorithme ne pourrait pas être moins que ça.

RBarryYoung
la source
Oui, veuillez l'afficher. Je suis toujours en train de développer les détails de l'algorithme linéaire, mais je suis presque sûr qu'il est valide.
RBarryYoung
5
Pour mémoire, il semble qu'il existe parfois autant de solutions que nous ne pouvons pas vraiment avoir d' algorithme . Ω(NloglogN)O(N)
Yuval Filmus
1
De là, il semble que le catch (et le facteur non linéaire supplémentaire) provienne des deux boucles foreach () dans votre boucle while principale; votre temps total est essentiellement, et le problème est que les tailles de hiList et loList ne sont pas nécessairement limitées par une constante. i=0N/2|hiListNi||loListi|
Steven Stadnicki
Oui, c'est exact, mais votre formule est un peu décalée car d'abord i varie de 0 à environ. N PI / 8, et en second lieu seulement une fraction des valeurs de i satisfont hiList (Ni) + loList (i) = N, donc elles ne sont pas toutes ajoutées. En tout état de cause, il n'y a aucun moyen de résoudre ce problème et je suis assez sûr que cela donne la complexité minimale possible de O (N log (log (N))).
RBarryYoung
Mais nous pouvons avoir un algorithme qui s'exécute en O (max (N, "nombre de solutions")), prenant l'espace O (n).
gnasher729

Réponses:

15

L'algorithme de Juho peut être amélioré en un algorithme en utilisant la rencontre au milieu. Passez en revue toutes les paires ; pour chaque paire telle que , stockez dans un tableau de longueur (chaque position pourrait contenir plusieurs paires, qui pourraient être stockées dans une liste chaînée). Parcourez maintenant les paires telle sorte que les cellules correspondantes dans soient pas vides.A , B O(N) M=A2+B2N(A,B)TNMM,N-MTA,BNM=A2+B2N(A,B)TNMM,NMT

De cette façon, nous obtenons une représentation implicite de tous les quadruples. Si nous voulons tous les énumérer, nous ne pouvons pas faire mieux que , car le théorème des quatre carrés de Jacobi montre que (pour impair ) le nombre de représentations est , et il existe une infinité de nombres entiers tels que (voir le théorème de Grönwall ).Ω(NloglogN)N8σ(N)σ(N)(eγϵ)NloglogN

Afin d'obtenir des algorithmes moins triviaux, on peut essayer de factoriser sur l'anneau de quaternion approprié, car on sait que les représentations sous forme de sommes de deux carrés correspondent (dans un certain sens) à ces factorisations, à travers l'identité quadratique de Lagrange. Il nous faudrait encore trouver toutes les représentations de tout nombre premier pertinent.N

Yuval Filmus
la source
Hmm, la rencontre dans le milieu ressemble beaucoup à ce sur quoi je travaille (presque terminé) qui est un algorithme de fusion-correspondance ascendant / descendant sur les paires TwoSquare. Est-ce que ça sonne pareil?
RBarryYoung
1
C'est probablement la même chose, la rencontre au milieu est une heuristique si courante qu'elle doit avoir de nombreux noms différents.
Yuval Filmus
Umm, je suis sorti du milieu universitaire depuis trente ans, qu'est-ce que la chose signifie? (ou pouvez-vous m'indiquer une référence?) thnx. σ(N)
RBarryYoung
Ou est-ce que vraiment un ? σ(N)ο(N)
RBarryYoung
1
La somme des diviseurs fonctionne en effet.
Yuval Filmus
5

Je pense qu'un algorithme de temps n'est pas trivial et nécessite un aperçu s'il en existe un. L'algorithme évident qui s'exécute en temps quadratique énumère tous les tuples . Cela peut être fait en quatre boucles, de sorte que la complexité temporelle totale devient . Il énumère également clairement toutes les solutions.o(N2)A,B,C,DNO(N2)

En tant qu'algorithmes relatifs, Rabin et Shallit [1] présentent deux algorithmes randomisés pour décomposer des entiers en somme de carrés. Pour deux carrés, ils donnent un algorithme de temps attendu . Pour quatre carrés, ils donnent un algorithme de temps attendu . Notez que les algorithmes ne vous donnent pas toutes les solutions, mais seulement une seule.O ( log 2 n log log n )O(log2n)O(log2nloglogn)


[1] MO Rabin, JO Shallit, Algorithmes randomisés en théorie des nombres , Communications on Pure and Applied Mathematics 39 (1986), no. S1, p. S239 – S256 .

Juho
la source
Pour un algorithme trivial, vous n'avez besoin que de boucles pour A, B et C, puis calculez D et vérifiez qu'il s'agit d'un entier. Si vous avez besoin de A ≤ B ≤ C ≤ D, vous devriez obtenir O (N ^ 1,5) avec une constante plutôt petite.
gnasher729
Environ 0,04 N ^ 1,5 triplets (A, B, C), et vérifier que N - A ^ 2 - B ^ 2 - C ^ 2 est un carré peut être fait très rapidement.
gnasher729
-2

Le nombre de solutions est exactement , où passe par tous les diviseurs de qui ne sont pas des multiples de 4. C'est un théorème de Jacobi.d n8ddn

client
la source
1
Et comment cela répond-il à la question? La tâche est de donner tous ces quadruples!
Raphael
1
Cela est déjà mentionné dans ma réponse.
Yuval Filmus