Taxicab Numbers

[rgalgon]

I'm new to Python and have been putting my mind to learning it over my
holiday break. I've been looking over the functional programming
aspects of Python and I'm stuck trying to come up with some concise
code to find Taxicab numbers (http://mathworld.wolfram.com/
TaxicabNumber.html).

"Taxicab(n), is defined as the smallest number that can be expressed
as a sum of two positive cubes in n distinct ways"

In Haskell something like this could easily be done with:
cube x = x * x * x

taxicab n = [(cube a + cube b, (a, b), (c, d))
| a <- [1..n],
b <- [(a+1)..n],
c <- [(a+1)..n],
d <- [(c+1)..n],
(cube a + cube b) == (cube c + cube d)]

Output::
*Maintaxicab 10
[]
*Maintaxicab 12
[(1729,(1,12),(9,10))]
*Maintaxicab 20
[(1729,(1,12),(9,10)),(4104,(2,16),(9,15))]

I'm looking for a succinct way of doing this in Python. I've been
toying around with filter(),map(), and reduce() but haven't gotten
anything half-way decent yet.

So, how would you implement this taxicab(n) function in Python?
Thanks in advance :-)

[Paul Hankin]

On Dec 27, 9:48*pm, rgalgon <[e-mail]:

I'm new to Python and have been putting my mind to learning it over my
holiday break. I've been looking over the functional programming
aspects of Python and I'm stuck trying to come up with some concise
code to find Taxicab numbers (http://mathworld.wolfram.com/
TaxicabNumber.html).

"Taxicab(n), is defined as the smallest number that can be expressed
as a sum of two positive cubes in n distinct ways"

In Haskell something like this could easily be done with:
cube x = x * x * x

taxicab n = [(cube a + cube b, (a, b), (c, d))
* * * * * * | a <- [1..n],
* * * * * * * b <- [(a+1)..n],
* * * * * * * c <- [(a+1)..n],
* * * * * * * d <- [(c+1)..n],
* * * * * * * (cube a + cube b) == (cube c + cube d)]

Output::
*Maintaxicab 10
[]
*Maintaxicab 12
[(1729,(1,12),(9,10))]
*Maintaxicab 20
[(1729,(1,12),(9,10)),(4104,(2,16),(9,15))]

I'm looking for a succinct way of doing this in Python. I've been
toying around with filter(),map(), and reduce() but haven't gotten
anything half-way decent yet.

So, how would you implement this taxicab(n) function in Python?
Thanks in advance :-)

Python's list comprehensions are quite similar to haskell's, so this
code can be translated almost word-for-word.

def cube(x):
return x * x * x

def taxicab(n):
return [(cube(a) + cube(b), (a, b), (c, d))
for a in range(1, n + 1)
for b in range(a + 1, n + 1)
for c in range(a + 1, n + 1)
for d in range(c + 1, n + 1)
if cube(a) + cube(b) == cube(c) + cube(d)]

for n in (10, 12, 20):
print list(taxicab(n))

--
Paul Hankin

[Terry Jones]

>>>>"rgalgon" == rgalgon <rg*****@gmail.comwrites:

rgalgonI'm new to Python and have been putting my mind to learning it
rgalgonover my holiday break. I've been looking over the functional
rgalgonprogramming aspects of Python and I'm stuck trying to come up with
rgalgonsome concise code to find Taxicab numbers
rgalgon(http://mathworld.wolfram.com/ TaxicabNumber.html).

rgalgon"Taxicab(n), is defined as the smallest number that can be
rgalgonexpressed as a sum of two positive cubes in n distinct ways"

rgalgonIn Haskell something like this could easily be done with:
rgalgoncube x = x * x * x

rgalgontaxicab n = [(cube a + cube b, (a, b), (c, d))
rgalgon| a <- [1..n],
rgalgonb <- [(a+1)..n],
rgalgonc <- [(a+1)..n],
rgalgond <- [(c+1)..n],
rgalgon(cube a + cube b) == (cube c + cube d)]

rgalgonI'm looking for a succinct way of doing this in Python. I've been
rgalgontoying around with filter(),map(), and reduce() but haven't gotten
rgalgonanything half-way decent yet.

rgalgonSo, how would you implement this taxicab(n) function in Python?

To give a fairly literal translation of your Haskell, you could just use
this:

def cube(n): return n ** 3

def taxicab(n):
n += 1
return [(cube(a) + cube(b), (a, b), (c, d))
for a in xrange(1, n)
for b in xrange(a + 1, n)
for c in xrange(a + 1, n)
for d in xrange(c + 1, n)
if cube(a) + cube(b) == cube(c) + cube(d)]

If you print the return value of this you get the same results as your
Haskell examples. I added the following to my Python file:

if __name__ == '__main__':
import sys
print taxicab(int(sys.argv[1]))

Then I see

$ time taxicab.py 20
[(1729, (1, 12), (9, 10)), (4104, (2, 16), (9, 15))]

real 0m0.098s
user 0m0.046s
sys 0m0.046s
Terry

[Steven D'Aprano]

I hate having to correct myself...

On Fri, 28 Dec 2007 02:31:50 +0000, Steven D'Aprano wrote:

You seem to be treating n as the number to be split into the sum of
cubes,

Not quite... in your code, n appears to be the largest number to test.
That is, if n is twelve, you test up to 12 cubed.

but that's not what n is supposed to be. n is the number of
distinct sums.

That remains true.

--
Steven.