3

Possible Duplicate:
Finding Hardy Ramanujan Numbers

I need to find the lowest natural number x where 

x = k^3 + l^3 = i^3 + j^3

and (k, l, i, j) must all be different.

I tried the following four for loops, but I couldn't get it to the right solution because of infinitely increasing variables...

for (int i=0;;i++)
    for (int j=i+1;;j++)
        for (int k=j+1;;k++)
            for (int l=k+1;;i++)
                compare(i,j,k,l);
Community
  • 1
  • 1
user1836858
  • 39
  • 1
  • 1
    What is your `compare()` function? –  Nov 19 '12 at 20:08
  • 1
    Likely `compare()` is `return (i*i*i + j*j*j == k*k*k + l*l*l)`. The issue here is that his final loop will increment forever. And he recognizes this. The question is what is a good way to state this problem in code. – Bill Lynch Nov 19 '12 at 20:08
  • 3
    `for (int l=k+1;;i++)` should probably be `l++` not `i++` – Pubby Nov 19 '12 at 20:08
  • 1
    @moooeeeep: The current code will try `{0,1,2,3}`, then `{0,1,2,4}`, then `{0,1,2,5}`... The current code will not find a match. – Bill Lynch Nov 19 '12 at 20:15
  • 5
    @sharth - come to think of it none of the loops will ever end. There are no terminating conditions. For that to happen the `;;` in those looks need something to terminate them. So like my mother - it will never shut up !!!! – Ed Heal Nov 19 '12 at 20:17
  • 1
    I think I would recommend a different approach - generate an initial list of cubes, then search the list for pairs that happen to sum (or difference) to the same value. Start with a small list (e.g. the first 10 cubes), and if you don't find the solution in a small list, extend the list progressively until you find a solution. – twalberg Nov 19 '12 at 20:19
  • How about a Monte Carlo algorithm. Set the stakes low. Why ran out of choices increase the stakes? – Ed Heal Nov 19 '12 at 20:25
  • The Monte Carlo approach seems a lot like the brute force approach here. – Richard Nov 19 '12 at 20:32
  • 4
    spoiler: http://mathworld.wolfram.com/Hardy-RamanujanNumber.html – Andrew Durward Nov 19 '12 at 20:35

4 Answers4

4

You need to reframe how you're thinking about the problem.

It's really saying this: what's the smallest natural number expressible as the sum of two cubes in two different ways?

The problem statement calls that number x, and the pairs of cubes are (i, j) and (k, l).

Restated in this way, it's not nearly so bad. Here's a hint in pseudocode:

function count_num_cubic_pairs(n):
    cubic_pairs = []
    for i..n:
        first_cube = i * i * i
        remainder = n - first_cube
        if remainder is a cube and (first_cube, remainder) not in cubic_pairs:
            cubic_pairs.add((first_cube, remainder))
    return length(cubic_pairs)

The tough part will be testing whether remainder is a cube - floating point errors will complicate that a lot. That's the real meat of this problem - have fun with it.

spencer nelson
  • 4,365
  • 3
  • 24
  • 22
1

One easy way to make your code work is to limit the domain of your variables, and then expand it a bit at a time.

As mazayus mentioned, you're keeping each variable strictly greater than the previous ones, so you never any variation that could possibly be correct.

Something like this may work (pseudocode) but it's horribly inefficient:

for max in [100, 200, 300, ...]
  for i in [0..max]
    for j in [0..max]
      for k in [0..max]
        for l in [0..max]
          if (i equals k or l, or j equals k or l) continue
          if (i^3 + j^3 equals k^3 + l^3)
            return answer
OmnipotentEntity
  • 16,531
  • 6
  • 62
  • 96
1
int i = 1
int j = 3
int k = 2
int l = 4

do {
  do {
    do {
      do {
        compare(i, j ,k l);
        i++;
      } while (i < k);
      k++;
    } while (k < j);
    j++;
  } while(j < l);
  l++;
} while(l < 100);

Something like this tries every combination of numbers without dups (up to values of 100), with i < k < j < l.

Adam Berkan
  • 115
  • 1
  • 6
1

Your loops assume i<j<k<l, which is not necessarily true. (It might be that j>k.) Once you get the right assumptions, you can reorder you loops so the first item is biggest and so the other loops are limited.

Here's an example with the i>j, i>k>l, 

for (int i=1;;i++)
    for (int j=1;j<i;j++)
        for (int k=1;k<i;k++)
            for (int l=1;l<k;i++)
                compare(i,j,k,l);

Once you get that working, try eliminating the fourth loop by checking if the cube root of i*i*i+j*j*j-k*k*k is a natural number. Then try finding a smarter starting value for k.

xan
  • 7,511
  • 2
  • 32
  • 45