471,342 Members | 1,851 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,342 software developers and data experts.

Taxicab Numbers

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 :-)
Dec 27 '07 #1
3 3591
On Dec 27, 9:48*pm, rgalgon <rgal...@gmail.comwrote:
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
Dec 28 '07 #2
>>>>"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
Dec 28 '07 #3
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.
Dec 28 '07 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

12 posts views Thread by Jim Michaels | last post: by
7 posts views Thread by Gerard Flanagan | last post: by
10 posts views Thread by LuTHieR | last post: by
7 posts views Thread by newstips6706 | last post: by
24 posts views Thread by pereges | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.