3

可能重复：
查找 Hardy Ramanujan 数

我需要找到最低的自然x数

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

并且(k, l, i, j)必须都不同。

我尝试了以下四个 for 循环，但由于变量无限增加，我无法找到正确的解决方案......

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);
4

4 回答 4

4

你需要重新定义你对这个问题的看法。

真的是这样说：可以用两种不同方式表示为两个立方体之和的最小自然数是多少？

问题陈述称这个数为 x，立方体对是 (i, j) 和 (k, l)。

以这种方式重述，它几乎没有那么糟糕。这是伪代码中的提示：

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)

困难的部分将是测试remainder is a cube浮点错误是否会使这变得复杂。这才是这个问题的真正关键——玩得开心。

于 2012-11-19T20:25:06.830 回答
1

您的循环假设i<j<k<l，这不一定是正确的。（可能是这样j>k。）一旦你得到正确的假设，你可以重新排列你的循环，这样第一个项目是最大的，所以其他的循环是有限的。

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);

一旦你得到这个工作，尝试通过检查立方根i*i*i+j*j*j-k*k*k是否是自然数来消除第四个循环。然后尝试为k.

于 2012-11-19T23:51:06.580 回答
1

使您的代码工作的一种简单方法是限制变量的域，然后一次扩展一点。

正如 mazayus 所提到的，您使每个变量都严格大于以前的变量，因此您永远不会有任何可能正确的变化。

像这样的东西可能有效（伪代码），但效率极低：

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
于 2012-11-19T20:22:56.057 回答
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);

像这样的东西会尝试所有没有重复的数字组合（最高值为 100），其中 i < k < j < l。

于 2012-11-19T20:24:40.233 回答