haskell - Haskell中的出租车编号

出租车编号定义为正整数，可以至少两种不同的方式表示为两个立方体的总和。

1729=1^3+12^3=9^3+10^3

我编写了这段代码以生成一个出租车编号，该编号在运行时将给出第n个最小的出租车编号：

taxicab :: Int -> Int
taxicab n = [(cube a + cube b)
            | a <- [1..100],
              b <- [(a+1)..100],
              c <- [(a+1)..100],
              d <- [(c+1)..100],
              (cube a + cube b) == (cube c + cube d)]!!(n-1)

cube x = x * x * x

但是我得到的输出不是我所期望的。对于数字1到3，代码产生正确的输出，但是taxicab 4产生39312而不是20683。另一个奇怪的是，39312本来是第六个最小的出租车数字不是第四！

那么为什么会这样呢？我的代码的缺陷在哪里？

最佳答案

我认为您错误地认为您的列表中包含的出租车编号是递增的。这是列表的实际内容：

[1729,4104,13832,39312,704977,46683,216027,32832,110656,314496,
 216125,439101,110808,373464,593047,149389,262656,885248,40033,
 195841,20683,513000,805688,65728,134379,886464,515375,64232,171288,
 443889,320264,165464,920673,842751,525824,955016,994688,327763,
 558441,513856,984067,402597,1016496,1009736,684019]

回想一下诸如[(a,b) | a<-[1..100],b<-[1..100]]之类的列表推导将生成其对，如下所示：

[(1,1),...,(1,100),(2,1),...,(2,100),...,...,(100,100)]

请注意，当a达到下一个值时，b从1重新启动。在您的代码中，假设您刚刚找到了格式为a^3+b^3的出租车编号，然后没有更大的b给出了出租车。在这种情况下，尝试下一个a值。我们可能会找到格式为(a+1)^3+b'^3的出租车，但不能保证该数字会更大，因为b'是[a+2..100]中的任何数字，并且可以小于b。当a的值较大时，也会发生这种情况：当a增大时，不能保证其相关的出租车比我们以前发现的更大。

还要注意，由于相同的原因，形式为101^3+b^3的假想出租车可能比您列表中的出租车要小，但在这里不会出现。

最后，请注意，您的函数效率很低，因为每次调用taxicab n时，都会重新计算所有第一个n出租车值。