Taxicab numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 05:25, 16 March 2014

definition

A taxicab number (the definition that is being used here) is a positive integer that can be expressed as the sum of two positive cubes in more than one way.

The first taxicab number is 1729, which is:

1³ + 12³ and

9³ + 10³.

Taxicab numbers are also known as:

taxi numbers
taxicab numbers
taxi cab numbers
taxi-cab numbers
Hardy-Ramanujan numbers

task requirements

The task requirements are:

compute the lowest 25 taxicab numbers.
exactly 25 taxicab numbers are to be shown (in numeric order).
show the taxicab numbers as well as its constituent cubes.
show all numbers in a very readable (aligned) format.
show the 2,000^th taxicab number + a half dozen more (extra credit)).

See also

Sequence A001235 taxicab numbers on The On-Line Encyclopedia of Integer Sequences.
Entry Hardy-Ramanujan Number on The Eric Weisstein's World of Mathematics (TM).
Entry taxicab number on The Eric Weisstein's World of Mathematics (TM).
Wiki entry Hardy-Ramanujan number.

C

Using a priority queue to emit sum of two cubs in order. It's reasonably fast and doesn't use excessive amount of memory (the heap is only at 245 length upon the 2006th taxi). <lang c>#include <stdio.h>

include <stdlib.h>

typedef unsigned long long xint; typedef unsigned uint; typedef struct { uint x, y; // x > y always xint value; } sum_t;

xint *cube; uint n_cubes;

sum_t *pq; uint pq_len, pq_cap;

void add_cube(void) { uint x = n_cubes++; cube = realloc(cube, sizeof(xint) * (n_cubes + 1)); cube[n_cubes] = (xint) n_cubes*n_cubes*n_cubes; if (x < 2) return; // x = 0 or 1 is useless

if (++pq_len >= pq_cap) { if (!(pq_cap *= 2)) pq_cap = 2; pq = realloc(pq, sizeof(*pq) * pq_cap); }

sum_t tmp = (sum_t) { x, 1, cube[x] + 1 }; // upheap uint i, j; for (i = pq_len; i >= 1 && pq[j = i>>1].value > tmp.value; i = j) pq[i] = pq[j];

pq[i] = tmp; }

void next_sum(void) { redo: while (!pq_len || pq[1].value >= cube[n_cubes]) add_cube();

sum_t tmp = pq[0] = pq[1]; // pq[0] always stores last seen value if (++tmp.y >= tmp.x) { // done with this x; throw it away tmp = pq[pq_len--]; if (!pq_len) goto redo; // refill empty heap } else tmp.value += cube[tmp.y] - cube[tmp.y-1];

uint i, j; // downheap for (i = 1; (j = i<<1) <= pq_len; pq[i] = pq[j], i = j) { if (j < pq_len && pq[j+1].value < pq[j].value) ++j; if (pq[j].value >= tmp.value) break; } pq[i] = tmp; }

uint next_taxi(sum_t *hist) { do next_sum(); while (pq[0].value != pq[1].value);

uint len = 1; hist[0] = pq[0]; do { hist[len++] = pq[1]; next_sum(); } while (pq[0].value == pq[1].value);

return len; }

int main(void) { uint i, l; sum_t x[10]; for (i = 1; i <= 2006; i++) { l = next_taxi(x); if (25 < i && i < 2000) continue; printf("%4u:%10llu", i, x[0].value); while (l--) printf(" = %4u^3 + %4u^3", x[l].x, x[l].y); putchar('\n'); } return 0; }</lang>

Output:

   1:      1729 =   12^3 +    1^3 =   10^3 +    9^3
   2:      4104 =   15^3 +    9^3 =   16^3 +    2^3
   3:     13832 =   20^3 +   18^3 =   24^3 +    2^3
   4:     20683 =   27^3 +   10^3 =   24^3 +   19^3
   5:     32832 =   30^3 +   18^3 =   32^3 +    4^3
   6:     39312 =   33^3 +   15^3 =   34^3 +    2^3
   7:     40033 =   33^3 +   16^3 =   34^3 +    9^3
   8:     46683 =   30^3 +   27^3 =   36^3 +    3^3
   9:     64232 =   36^3 +   26^3 =   39^3 +   17^3
  10:     65728 =   33^3 +   31^3 =   40^3 +   12^3
  11:    110656 =   40^3 +   36^3 =   48^3 +    4^3
  12:    110808 =   45^3 +   27^3 =   48^3 +    6^3
  13:    134379 =   43^3 +   38^3 =   51^3 +   12^3
  14:    149389 =   50^3 +   29^3 =   53^3 +    8^3
  15:    165464 =   48^3 +   38^3 =   54^3 +   20^3
  16:    171288 =   54^3 +   24^3 =   55^3 +   17^3
  17:    195841 =   57^3 +   22^3 =   58^3 +    9^3
  18:    216027 =   59^3 +   22^3 =   60^3 +    3^3
  19:    216125 =   50^3 +   45^3 =   60^3 +    5^3
  20:    262656 =   60^3 +   36^3 =   64^3 +    8^3
  21:    314496 =   66^3 +   30^3 =   68^3 +    4^3
  22:    320264 =   66^3 +   32^3 =   68^3 +   18^3
  23:    327763 =   58^3 +   51^3 =   67^3 +   30^3
  24:    373464 =   60^3 +   54^3 =   72^3 +    6^3
  25:    402597 =   61^3 +   56^3 =   69^3 +   42^3
2000:1671816384 = 1168^3 +  428^3 =  944^3 +  940^3
2001:1672470592 = 1124^3 +  632^3 = 1187^3 +   29^3
2002:1673170856 = 1034^3 +  828^3 = 1164^3 +  458^3
2003:1675045225 = 1153^3 +  522^3 = 1081^3 +  744^3
2004:1675958167 = 1096^3 +  711^3 = 1159^3 +  492^3
2005:1676926719 = 1188^3 +   63^3 = 1095^3 +  714^3
2006:1677646971 =  990^3 +  891^3 = 1188^3 +   99^3

J

Explanation:

First, generate 100 cubes.

Then, form a 3 column table of unique rows: sum, small cube, large cube

Then, gather rows where the first entry is the same. Keep the ones with at least two such entries.

Note that the cube root of the 25th entry is slightly smaller than 74, so testing against the first 100 cubes is more than sufficient.

Perl 6

This example may be incorrect.

For the 1^st requirement, exactly 25 taxicab numbers are to be shown.
The intent is to make sure that a program can handle finding the (lower) proper taxicab numbers up to a certain number correctly.
For the 2,000^th through the 2,007^th taxicab numbers,
only seven numbers should be shown, not 2,007 with the first 1,999 numbers elided.

Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

This uses a pretty simple search algorithm that doesn't guarantee the order of the returned numbers. Assuming we want N Taxicab numbers, in order to guarantee that we have all of them up to N, we look at the Nth one found and continue to search up to the cube root of the Nth value. That ensures we will find them all up to N without needing to search arbitrarily or use magic numbers. Defaults to returning the first 25 Taxicab numbers. Pass in a value if you want to specify some other amount. <lang perl6>sub MAIN ($upto = 25) {

   my %taxi;
   my $taxis = 0;
   my $terminate = Inf;

   for 1 .. * -> $c1 {
       my $c = $c1 ** 3;
       display(%taxi, $upto) and exit if $c > $terminate;
       for 1 ..^ $c1 -> $c2 {
           my $this = $c2 ** 3 + $c;
           %taxi{$this}.push: [$c2, $c1];
           $taxis++ if %taxi{$this}.elems == 2;
   	$terminate = $this if $taxis == $upto;
       }
   }

}

sub display (%this_stuff, $howmany) {

   my $i = 0; 
   printf "%4d %10d  =>\t%s\n", ++$i, $_.key, 
       ($_.value.map({ sprintf "%4d³ + %-s", $_[0], "$_[1]³" })).join: ",\t"
       for %this_stuff.grep( { $_.value.elems > 1 } ).sort( +*.key )[^$howmany];
   1;

}</lang>

Output:

With a passed parameter 2007

   1       1729  =>	   9³ + 10³,	   1³ + 12³
   2       4104  =>	   9³ + 15³,	   2³ + 16³
   3      13832  =>	  18³ + 20³,	   2³ + 24³
   4      20683  =>	  19³ + 24³,	  10³ + 27³
   5      32832  =>	  18³ + 30³,	   4³ + 32³
   6      39312  =>	  15³ + 33³,	   2³ + 34³
   7      40033  =>	  16³ + 33³,	   9³ + 34³
   8      46683  =>	  27³ + 30³,	   3³ + 36³
   9      64232  =>	  26³ + 36³,	  17³ + 39³
  10      65728  =>	  31³ + 33³,	  12³ + 40³
  11     110656  =>	  36³ + 40³,	   4³ + 48³
  12     110808  =>	  27³ + 45³,	   6³ + 48³
  13     134379  =>	  38³ + 43³,	  12³ + 51³
  14     149389  =>	  29³ + 50³,	   8³ + 53³
  15     165464  =>	  38³ + 48³,	  20³ + 54³
  16     171288  =>	  24³ + 54³,	  17³ + 55³
  17     195841  =>	  22³ + 57³,	   9³ + 58³
  18     216027  =>	  22³ + 59³,	   3³ + 60³
  19     216125  =>	  45³ + 50³,	   5³ + 60³
  20     262656  =>	  36³ + 60³,	   8³ + 64³
  21     314496  =>	  30³ + 66³,	   4³ + 68³
  22     320264  =>	  32³ + 66³,	  18³ + 68³
  23     327763  =>	  51³ + 58³,	  30³ + 67³
  24     373464  =>	  54³ + 60³,	   6³ + 72³
  25     402597  =>	  56³ + 61³,	  42³ + 69³
...(skip 1974 lines)
2000 1671816384  =>	 940³ + 944³,	 428³ + 1168³
2001 1672470592  =>	 632³ + 1124³,	  29³ + 1187³
2002 1673170856  =>	 828³ + 1034³,	 458³ + 1164³
2003 1675045225  =>	 744³ + 1081³,	 522³ + 1153³
2004 1675958167  =>	 711³ + 1096³,	 492³ + 1159³
2005 1676926719  =>	 714³ + 1095³,	  63³ + 1188³
2006 1677646971  =>	 891³ + 990³,	  99³ + 1188³
2007 1680918365  =>	 613³ + 1132³,	  16³ + 1189³

Python

(Magic number 1201 found by trial and error) <lang python>from collections import defaultdict from itertools import product from pprint import pprint as pp

cube2n = {x**3:x for x in range(1, 1201)} sum2cubes = defaultdict(set) for c1, c2 in product(cube2n, cube2n): if c1 >= c2: sum2cubes[c1 + c2].add((cube2n[c1], cube2n[c2]))

taxied = sorted((k, v) for k,v in sum2cubes.items() if len(v) >= 2)

pp(len(taxied)) # 2068

for t in enumerate(taxied[:25], 1):

   pp(t)

print('...') for t in enumerate(taxied[2000-1:2000+6], 2000):

   pp(t)</lang>

Output:

(1, (1729, {(12, 1), (10, 9)}))
(2, (4104, {(16, 2), (15, 9)}))
(3, (13832, {(20, 18), (24, 2)}))
(4, (20683, {(27, 10), (24, 19)}))
(5, (32832, {(30, 18), (32, 4)}))
(6, (39312, {(33, 15), (34, 2)}))
(7, (40033, {(33, 16), (34, 9)}))
(8, (46683, {(30, 27), (36, 3)}))
(9, (64232, {(36, 26), (39, 17)}))
(10, (65728, {(33, 31), (40, 12)}))
(11, (110656, {(48, 4), (40, 36)}))
(12, (110808, {(48, 6), (45, 27)}))
(13, (134379, {(51, 12), (43, 38)}))
(14, (149389, {(50, 29), (53, 8)}))
(15, (165464, {(54, 20), (48, 38)}))
(16, (171288, {(54, 24), (55, 17)}))
(17, (195841, {(57, 22), (58, 9)}))
(18, (216027, {(60, 3), (59, 22)}))
(19, (216125, {(60, 5), (50, 45)}))
(20, (262656, {(64, 8), (60, 36)}))
(21, (314496, {(66, 30), (68, 4)}))
(22, (320264, {(66, 32), (68, 18)}))
(23, (327763, {(58, 51), (67, 30)}))
(24, (373464, {(72, 6), (60, 54)}))
(25, (402597, {(69, 42), (61, 56)}))
...
(2000, (1671816384, {(1168, 428), (944, 940)}))
(2001, (1672470592, {(1187, 29), (1124, 632)}))
(2002, (1673170856, {(1164, 458), (1034, 828)}))
(2003, (1675045225, {(1153, 522), (1081, 744)}))
(2004, (1675958167, {(1159, 492), (1096, 711)}))
(2005, (1676926719, {(1188, 63), (1095, 714)}))
(2006, (1677646971, {(990, 891), (1188, 99)}))

REXX

<lang rexx>/*REXX program displays the first (lowest) taxicab numbers. */ parse arg L1 H1 L2 H2 . /*obtain the optional numbers. */ if L1== | L1==',' then L1=1 /*L1 " " " " " */ if H1== | H1==',' then H1=25 /*H1 " " " " " */ if L2== | L2==',' then L2=2000 /*L2 " " " " " */ if H2== | H2==',' then H2=2007 /*H2 " " " " " */ mx=max(L1, H1, L2, H2) /*find how many taxicab #s needed*/ mx=mx+mx%10 /*cushion, compensate for triples*/ w=length(mx) /*width is used formatting output*/ numeric digits 20 /*prepare to use larger numbers. */

=0; @.=0; $.=; b='■'; p='**3' /*initialize some REXX variables.*/

                                      /* [↓]  generate extra taxicab #s*/
do j=1   until  #>=mx                 /*taxicab nums won't be in order.*/
jjj=j**3                              /*might as well calculate a cube.*/
         do k=1  for j-1; s=jjj+k**3  /*define a whole bunch of cubes. */
         if @.s==0  then do           /*if cube not defined, then do it*/
                         @.s = "────►"right(j,6,b)p"■■■+"right(k,6,b)p
                         iterate      /* ··· and then go and do another*/
                         end          /* [↑] define one cube at a time.*/
         comma=pos(',',@.s)\==0       /*has it has been defined before?*/
         @.s=@.s","right(j,9,b)p"■■■+"right(k,6,b)p   /*build the text.*/
         $.s=right(s,15,b)'■■■'@.s    /*define the rest of taxicab #s. */
         if comma  then iterate       /*S  is a triple (or better).    */
         #=#+1                        /*bump the taxicab number count. */
         #.#=s                        /*define a   #.   taxicab number.*/
         end   /*k*/                  /* [↑]  build cubes one-at-a-time*/
end   /*j*/                           /* [↑]  complete with overage #s.*/

h=mx /*H= ½─way point for pivot sort. */

     do  while  h>1;  h=h%2;   do i=1  for mx-h; j=i; k=h+i    /*sort. */
     do  while  #.k<#.j;       _=#.j;  #.j=#.k;  #.k=_         /*sort. */
         if h>=j  then leave;  j=j-h;  k=k-h;  end;  end       /*sort. */
     end   /*while h>1*/              /* [↑]  sort the taxicab # array.*/

call show L1,H1 /*show 1st range of taxicab #s. */ call show L2,H2 /*show 2nd range of taxicab #s. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SHOW subroutine─────────────────────*/ show: parse arg low,high; if low==0 then return /*show bunch taxicab#s,*/

    do t=low to high;  _=#.t          /*get single taxicab # at a time.*/
    say right(t,w)  translate($._,,b) /*display taxicab # (with blanks)*/
    end   /*t*/                       /* [↑] ■ are translated to blanks*/

return</lang> output using the default input:

 
   1            1729            10**3   +     9**3,       12**3   +     1**3
   2            4104            15**3   +     9**3,       16**3   +     2**3
   3           13832            20**3   +    18**3,       24**3   +     2**3
   4           20683            24**3   +    19**3,       27**3   +    10**3
   5           32832            30**3   +    18**3,       32**3   +     4**3
   6           39312            33**3   +    15**3,       34**3   +     2**3
   7           40033            33**3   +    16**3,       34**3   +     9**3
   8           46683            30**3   +    27**3,       36**3   +     3**3
   9           64232            36**3   +    26**3,       39**3   +    17**3
  10           65728            33**3   +    31**3,       40**3   +    12**3
  11          110656            40**3   +    36**3,       48**3   +     4**3
  12          110808            45**3   +    27**3,       48**3   +     6**3
  13          134379            43**3   +    38**3,       51**3   +    12**3
  14          149389            50**3   +    29**3,       53**3   +     8**3
  15          165464            48**3   +    38**3,       54**3   +    20**3
  16          171288            54**3   +    24**3,       55**3   +    17**3
  17          195841            57**3   +    22**3,       58**3   +     9**3
  18          216027            59**3   +    22**3,       60**3   +     3**3
  19          216125            50**3   +    45**3,       60**3   +     5**3
  20          262656            60**3   +    36**3,       64**3   +     8**3
  21          314496            66**3   +    30**3,       68**3   +     4**3
  22          320264            66**3   +    32**3,       68**3   +    18**3
  23          327763            58**3   +    51**3,       67**3   +    30**3
  24          373464            60**3   +    54**3,       72**3   +     6**3
  25          402597            61**3   +    56**3,       69**3   +    42**3

2000      1671816384           944**3   +   940**3,     1168**3   +   428**3
2001      1672470592          1124**3   +   632**3,     1187**3   +    29**3
2002      1673170856          1034**3   +   828**3,     1164**3   +   458**3
2003      1675045225          1081**3   +   744**3,     1153**3   +   522**3
2004      1675958167          1096**3   +   711**3,     1159**3   +   492**3
2005      1676926719          1095**3   +   714**3,     1188**3   +    63**3
2006      1677646971           990**3   +   891**3,     1188**3   +    99**3
2007      1680918365          1132**3   +   613**3,     1189**3   +    16**3