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出租车值.