CODEWITHSUNDEEP
haskell
Crazy Psychild
Crazy Psychild

Reputation: 592

Taxicab Numbers in Haskell

Taxicab number is defined as a positive integer that can be expressed as a sum of two cubes in at least two different ways.

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

I wrote this code to produce a taxicab number which on running would give the nth smallest taxicab number:

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

But the output I get is not what I expected.For the numbers one to three the code produces correct output but taxicab 4 produces 39312 instead of 20683.Another strange thing is that 39312 is originally the 6th smallest taxicab number-not fourth!

So why is this happening? Where is the flaw in my code?

Upvotes: 2

Views: 417

Answers (1)

chi
chi

Reputation: 116174

I think you mistakenly believe that your list contains the taxicab numbers in an increasing order. This is the actual content of your list:

[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]

Recall that a list comprehension such as [(a,b) | a<-[1..100],b<-[1..100]] will generate its pairs as follows:

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

Note that when a gets to its next value, b is restarted from 1. In your code, suppose you just found a taxicab number of the form a^3+b^3, and then no larger b gives you a taxicab. In such case the next value of a is tried. We might find a taxicab of the form (a+1)^3+b'^3 but there is no guarantee that this number will be larger, since b' is any number in [a+2..100], and can be smaller than b. This can also happen with larger values of a: when a increases, there's no guarantee its related taxicabs are larger than what we found before.

Also note that, for the same reason, an hypotetical taxicab of the form 101^3+b^3 could be smaller than the taxicabs you have on your list, but it does not occur there.

Finally, note that you function is quite inefficient, since every time you call taxicab n you recompute all the first n taxicab values.

Upvotes: 5

Related Questions