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::
*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

 

[Terry Jones]

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.wolfram.com/ 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]

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::
*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))

 

[Steven D'Aprano]

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::
*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/TaxicabNumber.html


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 D'Aprano]

I hate having to correct myself...

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.