1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving algorithm using heap

  1. Sep 26, 2015 #1
    1. The problem statement, all variables and given/known data
    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: a7 + b7 = c7 + d 7

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

    3. The attempt at a solution
    Some basic math will tell us that there are n4 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.
     
  2. jcsd
  3. Sep 26, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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(n3 log n), needs some improvement.
     
  4. Sep 26, 2015 #3
    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(n2). I think this accounts for the n2 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.
     
  5. Sep 27, 2015 #4

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Sep 27, 2015
  6. Sep 27, 2015 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That would be easy, but I don't think it is true, and you would have to prove it.
    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 n2 entries. That would allow an O(n2 log n) algorithm easily, but it is not allowed. Sorting this would still need at least O(n2) as you have n2 entries, but I guess that factor 8 is actually the logarithm, so you have O(n2 log n) sorting steps. Fine. But the array is too large.
     
  7. Sep 27, 2015 #6

    rcgldr

    User Avatar
    Homework Helper

    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?
     
    Last edited: Sep 27, 2015
  8. Sep 27, 2015 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

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

    Anyway, that sub-discussion is pointless because we cannot use a data structure with n2 entries.
     
  9. Sep 27, 2015 #8

    rcgldr

    User Avatar
    Homework Helper

    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

    It could be used to confirm the results of a heap based algorithm.
     
    Last edited: Sep 27, 2015
  10. Sep 27, 2015 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    If you scale that up to arbitrary length, you still get the factor of log n for the number of passes.
    Yes, but it does not help solving the original problem.
     
  11. Sep 27, 2015 #10

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Sep 27, 2015
  12. Sep 27, 2015 #11
    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
     
  13. Sep 27, 2015 #12

    rcgldr

    User Avatar
    Homework Helper

    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?
     
  14. Sep 27, 2015 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  15. Sep 27, 2015 #14

    rcgldr

    User Avatar
    Homework Helper

    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-existance of solutions for cases like 7.2.2, so all that can be stated is that there are no known solutions.
     
  16. Sep 28, 2015 #15

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    At least there is no known way to prove it.
    Sure, but you still want an efficient algorithm for that. As efficient as possible.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted