Solving the a7 + b7 = c7 + d7 Equation Using Heap Algorithm

[NATURE.M]

Homework Statement

We have four integers a,b,c,d each of which are >= 1 and <= n, and are asked to write an algorithm to find all possible solutions to the following equation: a⁷ + b⁷ = c⁷ + d ⁷

The algorithm should use a heap of at most n elements, and should have worst case runtime of O(n² log n).

The Attempt at a Solution

Some basic math will tell us that there are n⁴ possible combinations of a,b,c,d for some input n. So if we go through each possible combination it would be very costly. This is where the heap is suppose to come into play. But I'm having particular difficulty determining how we would actually use it for this question.

 

[mfb]

It is certainly useful to have some way to quickly look up "is x the seventh power of some integer?". I see an implementation with O(n³ log n), needs some improvement.

 

[NATURE.M]

It is certainly useful to have some way to quickly look up "is x the seventh power of some integer?". I see an implementation with O(n³ log n), needs some improvement.

Right now I'm thinking the only possible solutions are when a=c, b=d or when a=d, b=c. So this is what I have, but it doesn't use a heap. I'm still not entirely sure what I would want to store in the heap.

for (i : 1,...,n)
...for(j : 1,...,n)
...insert into array (i, j, i, j)
...if (i != j)
...insert into array (i, j, j, i)

The two for loops I believe are required regardless and give O(n²). I think this accounts for the n² term in the desired complexity. The insertion into the array takes O(# of elements) in the worst case. However, this is not correct. I'm just not sure how to use a heap here.

 

[rcgldr]

There's enough memory on a typical PC to solve this brute force.

Since 566^7 > 2^64, assuming you're using 64 bit unsigned integers (unsigned long long), then you could create an array of size 566 where array[ i ] = i^7 (I assume [0] is not used, so the array only contains 565 entries for 1^7 to 565^7). So now the problem is reduced to finding all combinations of array[ a ] + array[ b ] = array[ c ] + array[ d ]. An array of structures, size 320,356 (566^2) could contain the sums of all combinations of table[ x ] + table [ y ] and x and y, taking O(n^2). The table could be sorted using a counting / radix sort in 4 or 8 passes (sorting 64 bit values 16 bits or 8 bits at a time), independent of n, but since the value size of 64 bits depends on the maximum value of n, this could be considered O(n^2 log(maximum n)) time complexity.

It's not clear to me what is supposed to be stored in the heap.

 

[mfb]

Right now I'm thinking the only possible solutions are when a=c, b=d or when a=d, b=c.

That would be easy, but I don't think it is true, and you would have to prove it.

There's enough memory on a typical PC to solve this brute force.

There is no reason to limit N to 565. If you use unsigned long long it's your own fault that the algorithm cannot handle larger numbers.

Also, you are not allowed to use a data structure with n² entries. That would allow an O(n² log n) algorithm easily, but it is not allowed. Sorting this would still need at least O(n²) as you have n² entries, but I guess that factor 8 is actually the logarithm, so you have O(n² log n) sorting steps. Fine. But the array is too large.

 

[rcgldr]

Also, you are not allowed to use a data structure with n² entries. That would allow an O(n² log n) algorithm easily, but it is not allowed. Sorting this would still need at least O(n²) as you have n² entries, but I guess that factor 8 is actually the logarithm

Indirectly, the factor 8 is based on sorting 64 bit values 8 bits at a time. The 64 bit values could be sorted in 4 passes 16 bits at a time. The number of passes is based on the value size, independent of n, but since the value size depends on the maximum possible value of n, the number of passes = O(log((maximum n)^2)) = O(log(maximum n)) (the 2 in O(2 log(maximum n)) drops out with O() notation). So the sort would take O(n^2 log(maximum n)), if the integer size was a function of n, as opposed to limiting the maximum value of n. If the integer size is fixed in the algorithm, limiting the maximum value of n, then the time complexity is O(n^2).

Memory usage would be around 10 MB, but on most PC's, 1 GB of memory is usually available.

It wasn't stated what type heap would be used, perhaps a binary heap that is balanced as much as possible?

 

[mfb]

The sorting algorithm has to be able to handle arbitrary lengths.
You have n² values from 1 to n⁷ to sort, you cannot sort them in linear time. Your description sounds like bucket sort, that is still O(m log m) where m=n² is the number of entries as you cannot make n⁷ buckets.

Anyway, that sub-discussion is pointless because we cannot use a data structure with n² entries.

 

[rcgldr]

Your description sounds like bucket sort, that is still O(m log m) where m=n² is the number of entries as you cannot make n⁷ buckets.

It's a multi-pass bucket sort, but counts are generated for the bucket sizes (in this case a 8 x 256 matrix of counts converted into offsets), so only a temporary array of the same size as the original array is needed, in this case, n^2 x sizeof(structure containing 64 bit n^7 sum, and two 16 or 32 bit values for n0 and n1). Wiki articles:

http://en.wikipedia.org/wiki/Counting_sort

http://en.wikipedia.org/wiki/Radix_sort

Anyway, that sub-discussion is pointless because we cannot use a data structure with n² entries.

It could be used to confirm the results of a heap based algorithm.

 

[mfb]

If you scale that up to arbitrary length, you still get the factor of log n for the number of passes.

It could be used to confirm the results of a heap based algorithm.

Yes, but it does not help solving the original problem.

 

[rcgldr]

I think there is an issue with the original question (maybe it should have been 4th power, not 7th power?). This is a Diophantine Equation (integer equation) for 7th powers with 2 terms on each side of the equation, described as 7.2.2 (7th power, 2 terms on one side of the equation, 2 terms on the other side). As noted in this document, there are no known solutions for 7.2.2 but there are solutions for 7.4.4 (4 terms on each side of the equation):

http://mathworld.wolfram.com/DiophantineEquation7thPowers.html

For an example of what was involved to find any 7.4.4 solution:

http://www.ams.org/journals/mcom/1996-65-216/S0025-5718-96-00768-5/S0025-5718-96-00768-5.pdf

There are solutions for 2.2.2, 3.2.2, and 4.2.2, but no known solutions for 5.2.2, 6.2.2, 7.2.2, 8.2,2, 9.2.2, 10.2.2.

 

[NATURE.M]

I think there is an issue with the original question (maybe it should have been 4th power, not 7th power?). This is a Diophantine Equation (integer equation) for 7th powers with 2 terms on each side of the equation, described as 7.2.2 (7th power, 2 terms on one side of the equation, 2 terms on the other side). As noted in this document, there are no known solutions for 7.2.2 but there are solutions for 7.4.4 (4 terms on each side of the equation):

http://mathworld.wolfram.com/DiophantineEquation7thPowers.html

For an example of what was involved to find any 7.4.4 solution:

http://www.ams.org/journals/mcom/1996-65-216/S0025-5718-96-00768-5/S0025-5718-96-00768-5.pdf

There are solutions for 2.2.2, 3.2.2, and 4.2.2, but no known solutions for 5.2.2, 6.2.2, 7.2.2, 8.2,2, 9.2.2, 10.2.2.

Interesting, well this would confirm that there are only trivial solutions that exist to the original equation. But the original problem is as stated, that is 7.2.2

 

[rcgldr]

The first link posted above is part of a series that starts here:

http://mathworld.wolfram.com/topics/DiophantineEquations.html

For forth powers, 4.2.2 solutions exist. The article mentions that "Parametric solutions to the 4.2.2 equation are known ... but no "general" solution is known", and that "general (but incomplete) solutions are given by ..."

http://mathworld.wolfram.com/DiophantineEquation4thPowers.html

So where did the question about seventh powers (7.2.2) originate, and if not a mistake, I'm wondering if the originator was aware of the fact that there are no known solutions to 7.2.2?

 

[mfb]

Well, you can still search for them even if no solutions are known. Actually, that's the point of "no solutions are known": someone searched for them. Probably with an efficient algorithm.

 

[rcgldr]

Well, you can still search for them even if no solutions are known. Actually, that's the point of "no solutions are known": someone searched for them. Probably with an efficient algorithm.

If you look at the details for the 7.4.4 case, it's a somewhat optimized brute force approach, in that case using an AVL tree. I think once at 4.x.x or beyond, to get all solutions, there are no elegant algorithms, and there's no way to prove non-existence of solutions for cases like 7.2.2, so all that can be stated is that there are no known solutions.

 

[mfb]

At least there is no known way to prove it.

so all that can be stated is that there are no known solutions.

Sure, but you still want an efficient algorithm for that. As efficient as possible.