haskell - haskell 的出租车号码

Question

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

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

但是我得到的输出不是我所期望的。对于数字一到三，代码产生正确的输出，但 taxicab 4 产生 39312 而不是 20683 。另一个奇怪的事情是，39312 原本是第六小的出租车号码，而不是第四!

那么为什么会发生这种情况呢？我的代码哪里有缺陷？

Answer 1

我认为您错误地认为您的列表包含按升序排列的出租车号码。这是您列表的实际内容:

[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出租车值(value)。