Asp Forum - Taxicab Numbers - comp.lang.python

rgalgon

12/27/2007 9:49:00 PM

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.wo...
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::
*Main> taxicab 10
[]
*Main> taxicab 12
[(1729,(1,12),(9,10))]
*Main> taxicab 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 :-)

4 Answers

Terry Jones

12/28/2007 12:47:00 AM

>>>>> "rgalgon" == rgalgon <rgalgon@gmail.com> writes:

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

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

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

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

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

rgalgon> So, 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

Paul Hankin

12/28/2007 12:53:00 AM

On Dec 27, 9:48 pm, rgalgon <rgal...@gmail.com> wrote:
> 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.wo...
> 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::
> *Main> taxicab 10
> []
> *Main> taxicab 12
> [(1729,(1,12),(9,10))]
> *Main> taxicab 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

Steven D'Aprano

12/28/2007 2:32:00 AM

On Thu, 27 Dec 2007 13:48:36 -0800, rgalgon wrote:

> 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/TaxicabN...).
>
> "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::
> *Main> taxicab 10
> []
> *Main> taxicab 12
> [(1729,(1,12),(9,10))]
> *Main> taxicab 20
> [(1729,(1,12),(9,10)),(4104,(2,16),(9,15))]

I think you have COMPLETELY misunderstood what the taxicab numbers are,
and in particular note the meaning of the argument n. I suggest you re-
read the Mathworld page:

http://mathworld.wolfram.com/TaxicabN...

and pay special attention to the examples given.

You seem to be treating n as the number to be split into the sum of
cubes, but that's not what n is supposed to be. n is the number of
distinct sums.

Your example of taxicab 12 is wrong. According to Mathworld, only the
first five taxicab numbers are known, and the 6th is suspected but not
proven. The 12th taxicab number should be the number which can be written
as twelve distinct sums of two cubes, that is something like:

Note: there is a slightly different definition of taxicab number, which
does not take an "n" argument. In that case, if you list the taxicab
numbers in order from smallest to largest, the 12th is 110808, not 1729.

--
Steven

Steven D'Aprano

12/28/2007 3:16:00 AM

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.

comp.lang.python

Taxicab Numbers

rgalgon

Terry Jones

Paul Hankin

Steven D'Aprano

Steven D'Aprano

x Login to ForumsZone