9
\$\begingroup\$

Taxicab Numbers or OEIS A011541 are the least numbers that are able to be represented as n different sums of two positive cubed integers, for successive n.

You'll need to print out the nth taxicab number. This should work for any n in theory.

However, as only 6 taxicab numbers have been discovered so far, there won't be an n above 6. The numbers are 2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344.

You're not allowed to hard code these variables, because your program must work for any arbitrary n in theory.

\$\endgroup\$
  • \$\begingroup\$ Does this require we support numbers of arbitrary length? If we can only handle values up to 2^32-1 but the program would work for larger values if only they were allowed, is that OK? \$\endgroup\$ – Engineer Toast Jul 12 '17 at 20:37
  • \$\begingroup\$ Sure, that's fine with me. As long as the algorithm itself would work for any number, you're good. \$\endgroup\$ – Morgan Thrapp Jul 12 '17 at 20:58
5
\$\begingroup\$

Haskell, 60 bytes

f n=[k|k<-[0..],n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k]]!!0

Pretty straightforward. Counts how many ways a number k can be written as a sum of two cubes. Filters for k's such that this number is at least n, and takes the first one.

An equal-length method with until:

f n=until(\k->n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k])(+1)0
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your program produces the smallest number that's a sum of two cubes in n different ways. The problem asks to find the n'th number which is a sum of two cubes in two different ways. \$\endgroup\$ – Itai Bar-Natan Feb 24 '16 at 3:05
  • 1
    \$\begingroup\$ @ItaiBar-Natan It looks to me like the spec is asking for the least number that's a sum of two cubes in n different ways. \$\endgroup\$ – xnor Feb 24 '16 at 7:56
  • \$\begingroup\$ Oops, I just reread the problem and I think you're right. I guess I misread it incorrectly. \$\endgroup\$ – Itai Bar-Natan Feb 24 '16 at 13:14
6
\$\begingroup\$

Taxi, 4758 bytes

What better language to calculate taxicab numbers than one that simulates taxicabs?
This is a joke. There are so many better languages. What happened to the last two days of my life?

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Cyclone:s 1 l 1 l 2 l.[a]Pickup a passenger going to Firemouth Grill.Pickup a passenger going to The Underground.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to The Underground:e 1 l.Switch to plan "b" if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 3 l 2 l.Switch to plan "a".[b]Go to Firemouth Grill:s 1 r.[c]Pickup a passenger going to Cyclone.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 r 2 l.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e" if no one is waiting.Switch to plan "c".[e]Go to Trunkers:w 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 r.[f]Go to Trunkers:s 1 l.Switch to plan "g" if no one is waiting.Pickup a passenger going to Sunny Skies Park.Go to Cyclone:w 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Go to Sunny Skies Park:n 1 r.Switch to plan "f".[g]Go to Cyclone:w 2 r.Switch to plan "h" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to Trunkers:w 1 l 1 r.Switch to plan "g".[h]Go to Sunny Skies Park:n 1 r.Switch to plan "i" if no one is waiting.Pickup a passenger going to Cyclone.Go to Firemouth Grill:s 1 l 1 l 1 r.Pickup a passenger going to Addition Alley.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Trunkers.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Addition Alley:w 2 r 2 r 1 r.Pickup a passenger going to Narrow Path Park.Go to Narrow Path Park:n 1 r 1 l 1 r.Go to Cyclone:w 1 l 1 r 2 l.Switch to plan "h".[i]Go to Trunkers:s 1 l.Pickup a passenger going to Knots Landing.Go to Knots Landing:e 1 r 2 l 5 r.Go to Trunkers:w 1 l 3 r 1 l.Switch to plan "j" if no one is waiting.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e".[j]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Addition Alley.[k]Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Equal's Corner.Go to Zoom Zoom:n.Go to Rob's Rest:w 2 l 2 r 1 r.Go to Narrow Path Park:s 1 l 1 l 1 r 1 r 2 l 5 l.Switch to plan "o" if no one is waiting.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l 1 r 2 l 1 l.Switch to plan "l" if no one is waiting.Pickup a passenger going to Knots Landing.1 is waiting at Starchild Numerology.Switch to plan "m".[l]0 is waiting at Starchild Numerology.[m]Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:w 1 r 3 r 1 r 1 r.Pickup a passenger going to Addition Alley.Go to Knots Landing:n 1 r 2 r 1 l.Go to Starchild Numerology:w 1 l 3 r 1 l 1 l 2 l.Switch to plan "k".[o]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 1 r 2 l 1 l 3 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Go to Addition Alley:n 4 r 1 r 1 r.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 l 1 l 1 l 2 r 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Equal's Corner:n 1 r 1 r.Switch to plan "p" if no one is waiting.Go to Starchild Numerology:n 1 r.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 l 1 r 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.Switch to plan "z".[p]1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:s 1 l 1 l 2 r 1 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Rob's Rest:n 1 r 2 r 1 r.Go to Cyclone:s 1 l 1 l 2 l.Switch to plan "a".[z]

Try it online!
Try it online but with comments and line breaks!
Note: TIO can handle an input of 1 but 2 and above cause a timeout issue. I wrote a little snippet to print the value being checked every iteration and it only got up to 137 before it timed out. If someone who knows what they're doing could run it through an interpreter (the homepage links to a C++ version) to verify higher values, I'd appreciate it. It may take a very long time to run.

Ungolfed with comments:

[ FIND THE NTH TAXI CAB NUMBER ]
[ https://en.wikipedia.org/wiki/Taxicab_number ]
[ Inspired by https://codegolf.stackexchange.com/q/73827/38183 ]

[ A taxi cab number T(n) is the smallest number that can be made from the sum  ]
[ of two positive cubes in n different ways. For example, T(1) = 2 because     ]
[ 2 = 1^3 + 1^3. That is the only way to make 2 by summing positive cubes. No  ]
[ solution exists for 1 so 2 is T(1). T(2) = 1729 = 1^3 + 12^3 = 9^3 + 10^3.   ]
[ This program takes n as input and finds T(n). The (bad) psuedocode is:       ]
[                                                                              ]
[    S = STDIN;  // Use Bird's Bench                                           ]
[    T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true.   ]
[    while (true) {                                                            ]
[       // Fill an array (Firemouth Grill) with the numbers 1 through T        ]
[       // This will make it much easier to compute the cubes because a taxi   ]
[       // can only carry three passengers at a time.                          ]
[       for (i = T; i > 0; i--) { A.push(i) }                                  ]
[       // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[       for (i = T; i > 0; i--) { B.push(i ^ 3) }                              ]
[       // Fill an array (Sunny Skies Park) with each possible sum of cubes    ]
[       while (B(0) != null) {                                                 ]
[          // Make copies of the next value to add to each remaining value     ]
[          C.push(B(0));                                                       ]
[          while (B(0) != null) {                                              ]
[             C.push(C(0));                                                    ]
[             D.push(B(0));                                                    ]
[             B.shift();                                                       ]
[          }                                                                   ]
[          // Store each possible sum with this cube                           ]
[          while (C(0) != null) {                                              ]
[             E.push(C(0) + D(0));                                             ]
[             B.push(D(0));                                                    ]
[             C.shift;                                                         ]
[             D.shift;                                                         ]
[          }                                                                   ]
[       }                                                                      ]
[       // Check each possible sum to see if it equals T                       ]
[       N = 0;                                                                 ]
[       while (D(0) != null) {                                                 ]
[          if (D(0) = T) { N++ }                                               ]
[          D.shift();                                                          ]
[       }                                                                      ]
[       // If we found the desired number of sums, ouput and break             ]
[       // Otherwise, go to the next T and keep going                          ]
[       if (N = S) {                                                           ]
[          print(T);                                                           ]
[          break;                                                              ]
[       } else {                                                               ]
[          T++;                                                                ]
[       }                                                                      ]
[    }                                                                         ]
[                                                                              ]



[ S = STDIN;  // Use Bird's Bench                                         ]
[ T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true. ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left 2nd right.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.


[ // Fill an array (Firemouth Grill) with the numbers 1 through T      ]
[ // This will make it much easier to compute the cubes because a taxi ]
[ //  can only carry three passengers at a time.                       ]
[ for (i = T; i > 0; i--) { A.push(i) }                                ]
Go to Cyclone: south 1st left 1st left 2nd left.
[a]
Pickup a passenger going to Firemouth Grill.
Pickup a passenger going to The Underground.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to The Underground: east 1st left.
Switch to plan "b" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 3rd left 2nd left.
Switch to plan "a".


[b]
[ // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[ for (i = T; i > 0; i--) { B.push(i ^ 3); }                             ]
Go to Firemouth Grill: south 1st right.
[c]
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station: south 1st left 2nd right 4th left.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st right 2nd left.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e" if no one is waiting.
Switch to plan "c".


[e]
[ // Fill an array with each possible sum of cubes                ]
[ while (B(0) != null) {                                          ]
[ // Make copies of the next value to add to each remaining value ]
[ C.push(B(0));                                                   ]
[ while (B(0) != null) {                                          ]
[    C.push(C(0));                                                ]
[    D.push(B(0));                                                ]
[    B.shift();                                                   ]
[ }                                                               ]
[ Setup Cyclone with a copy of the first value ]
Go to Trunkers: west 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park: north 1st right.

[f]
[ Move any remaining values to Sunny Skies Park, duplicating Cyclone each time ]
Go to Trunkers: south 1st left.
Switch to plan "g" if no one is waiting.
Pickup a passenger going to Sunny Skies Park.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Go to Sunny Skies Park: north 1st right.
Switch to plan "f".

[g]
[ // Store each possible sum with this cube ]
[ while (C(0) != null) {                    ]
[    E.push(C(0) + D(0));                   ]
[    B.push(D(0));                          ]
[    C.shift;                               ]
[    D.shift;                               ]
[ }                                         ]
[ Move everything at Cyclone to Firemouth Grill ]
Go to Cyclone: west 2nd right.
Switch to plan "h" if no one is waiting.
Pickup a passenger going to Firemouth Grill.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to Trunkers: west 1st left 1st right.
Switch to plan "g".

[h]
[ Copy Sunny Skies Park to Trunkers and add it to Firemouth Grill ]
Go to Sunny Skies Park: north 1st right.
Switch to plan "i" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Firemouth Grill: south 1st left 1st left 1st right.
Pickup a passenger going to Addition Alley.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Trunkers.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Addition Alley: west 2nd right 2nd right 1st right.
Pickup a passenger going to Narrow Path Park.
Go to Narrow Path Park: north 1st right 1st left 1st right.
Go to Cyclone: west 1st left 1st right 2nd left.
Switch to plan "h".

[i]
[ } // End of 'while (B(0) != null)' up near plan "e" ]
Go to Trunkers: south 1st left.
Pickup a passenger going to Knots Landing.
Go to Knots Landing: east 1st right 2nd left 5th right.
Go to Trunkers: west 1st left 3rd right 1st left.
Switch to plan "j" if no one is waiting.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e".


[j]
[ // Check each possible sum to see if it equals T ]
[ N = 0;                                           ]
[ while (D(0) != null) {                           ]
[    if (D(0) = T) { N++; }                        ]
[    D.shift();                                    ]
[ }                                                ]
[ Set N = 0 ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Addition Alley.

[k]
[ Pickup T ]
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Equal's Corner.
Go to Zoom Zoom: north.
Go to Rob's Rest: west 2nd left 2nd right 1st right.
Go to Narrow Path Park: south 1st left 1st left 1st right 1st right 2nd left 5th left.
Switch to plan "o" if no one is waiting.

[ Check the next value against T ]
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left 1st right 2nd left 1st left.
Switch to plan "l" if no one is waiting.

[ It's a match so N = N + 1 ]
Pickup a passenger going to Knots Landing.
1 is waiting at Starchild Numerology.
Switch to plan "m".

[l]
[ It's not a match so N = N + 0 ]
0 is waiting at Starchild Numerology.

[m]
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: west 1st right 3rd right 1st right 1st right.
Pickup a passenger going to Addition Alley.
Go to Knots Landing: north 1st right 2nd right 1st left.
Go to Starchild Numerology: west 1st left 3rd right 1st left 1st left 2nd left.
Switch to plan "k".


[o]
[ // If we found the desired number of sums, ouput and break ]
[ // Otherwise, go to the next T and keep going              ]
[ if (N = S) {                                               ]
[    print(T);                                               ]
[    break;                                                  ]
[ } else {                                                   ]
[    T++;                                                    ]
[ }                                                          ]
[ T is still going to Equal's Corner so just get rid of it ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 1st right 2nd left 1st left 3rd left.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left.

[ N is still going to Addition Alley so redirect it to Equal's Corner ]
Go to Addition Alley: north 4th right 1st right 1st right.
Pickup a passenger going to Equal's Corner.

[ Compare N = S ]
Go to Bird's Bench: north 1st left 1st left 1st left 2nd right 1st left.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Equal's Corner.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Equal's Corner: north 1st right 1st right.
Switch to plan "p" if no one is waiting.

[ It's a match! The value we want is T, waiting at Rob's Rest. ]
[Go to Rob's Rest:n 3 l 1 r.]
Go to Starchild Numerology: north 1st right.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st left 1st right 1st right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Switch to plan "z".

[p]
[ It's not a match. T = T + 1 and start over. ]
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: south 1st left 1st left 2nd right 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north 1st right 2nd right 1st right.
Go to Cyclone: south 1st left 1st left 2nd left.
Switch to plan "a".

[z]
[ Terminate program with 10 less bytes than going back to the Taxi Garage ]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I love how insane of a language Taxi is. \$\endgroup\$ – Morgan Thrapp Jul 18 '17 at 20:36
  • \$\begingroup\$ @MorganThrapp I hadn't run into this before, but it quickly became an issue that you are able to store a maximum of 6 integer arrays and that's only because Trunkers and Rounders Pub play nicely with integers. If you're storing decimals, you only get 4 arrays. Plus, Firemouth Grill picks up numbers in random order so that's out if you need to maintain order. Really, you only get 2 queues and 1 stack. Good luck. \$\endgroup\$ – Engineer Toast Jul 18 '17 at 20:50
  • \$\begingroup\$ I'd complain about cheap upvotes given to submissions in funny languages, but this really deserves an upvote anyways. \$\endgroup\$ – Esolanging Fruit Jul 18 '17 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.