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 .
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 ).
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.
Pytanie zatem brzmi: jak szybko możemy znaleźć wszystkie Kwadraty Czterech Kwadratów dla danego ?
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.