12
\$\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 \$n\$th 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\$ and \$24153319581254312065344\$.

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

\$\endgroup\$
2
  • \$\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\$ 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\$ Jul 12 '17 at 20:58
12
\$\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 ]
\$\endgroup\$
3
  • \$\begingroup\$ I love how insane of a language Taxi is. \$\endgroup\$ 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\$ Jul 18 '17 at 20:50
  • 1
    \$\begingroup\$ I'd complain about cheap upvotes given to submissions in funny languages, but this really deserves an upvote anyways. \$\endgroup\$ Jul 18 '17 at 22:14
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
\$\endgroup\$
3
  • \$\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\$ 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\$ Feb 24 '16 at 13:14
2
\$\begingroup\$

Jelly, 11 bytes

Œċ*3§ċ⁸=ð1#

Try it online!

This is ridiculously slow, timing out for \$n > 1\$

How it works

Œċ*3§ċ⁸=ð1# - Main link. Takes n on the left
        ð   - Group the previous links into a dyad f(k, n):
Œċ          -   All pairs from [1, 2, ..., k]
  *3        -   Cube each
    §       -   Sum of each
     ċ⁸     -   Count occurrences of k
       =    -   Does that equal n?
         1# - Find the first k, starting with n, which returns true under f(k, n)
              Starting with k = n is fine, as k > n for all n
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 15 bytes

∞εL3mãOÙN>¢}Ik>

Try it online!

The program timeouts for \$n>1\$ , but the algorithm works.

\$\endgroup\$
1
\$\begingroup\$

ARM Thumb-2, 52 48 bytes for theoretical algorithm, 50 bytes for overflow safe version until n == 3

This one is hilariously inefficient, and only works for n == 3 if we assume infinite integers.

Raw machine code:

b570 2101 0004 000a fb02 f502 4355 0013
fb03 f603 fb06 5603 428e d101 3c01 d005
3b01 d8f5 3a01 d1ef 3101 e7eb 0008 bd70

Assembly:

        .text
        .arch armv6t2
        .thumb
        .globl taxi
        .thumb_func
taxi:
        @ Nickname some registers for clarity
        n .req r0
        candidate .req r1
        i .req r2
        j .req r3
        matches_left .req r4
        i_cubed .req r5
        j_cubed_sum .req r6

        push    {r4-r6, lr}
        @ Start with a candidate of 1 (even though it's impossible)
        movs    candidate, #1
.Lcandidate_loop:
        @ reset match counter
        movs    matches_left, n
        @ start checking cubes
        @ Behold! The world's most inefficient loop!
        @ Takes 1.8 seconds for n = 2 on actual hardware. And remember, this is O(n^3). XD
        @ It also is very vulnerable to integer overflow and returns the incorrect
        @ result for n == 3. However, with sufficiently large integers, it would
        @ theoretically work fine.
        @ for (i = candidate; i != 0; --i)
        movs    i, candidate
.Li_loop:
        @ i_cubed = i * i * i
        mul     i_cubed, i, i                        @ wide insn
        muls    i_cubed, i
        @ for (j = i; --j;)
        movs    j, i
.Lj_loop:
        @ j_cubed_sum = j * j * j + i_cubed
        mul     j_cubed_sum, j, j                    @ wide insn
        mla     j_cubed_sum, j_cubed_sum, j, i_cubed @ wide insn
        @ Compare to the candidate
        cmp     j_cubed_sum, candidate
        bne     .Lno_match
.Lmatch:
        @ If it is the same, decrement matches_left
        subs    matches_left, #1
        @ Exit if we found all of the matches
        bne     .Lexit
.Lno_match:
        @ Decrement j and loop while non-zero.
        subs    j, #1
        bhi     .Lj_loop
.Lnext_i:
        @ Decrement i, and loop if it is not zero
        subs    i, #1
        bne     .Li_loop
.Lnext_candidate:
        @ Next candidate.
        adds    candidate, #1
        b       .Lcandidate_loop
.Lexit:
        movs    r0, candidate
        pop     {r4-r6, pc}

Explanation

C function signature:

uint32_t taxi(uint32_t n);

Has a wonderful O(n^3) complexity combined with billions of redundant iterations thanks to it looping backwards, but it works for n == 1 and n == 2 in reasonable time on hardware. It doesn't properly calculate n == 3 because of integer overflow.

It is a very naïve triple nested loop that is incredibly inefficient.

Goes through every candidate, then tests every i for i <= candidate, then tests every j for j <= i, each going backwards. It calculates cubes live, and is horrendously redundant and inefficient....but it is small and that is what counts.

Equivalent C:

uint32_t taxi(uint32_t n)
{
    for (uint32_t candidate = 1; ; candidate++) {
        uint32_t matches_left = n;
        for (uint32_t i = candidate; i != 0; --i) {
            uint32_t i_cubed = i * i * i;
            for (uint32_t j = i; j != 0; --j) {
                uint32_t j_cubed_sum = j * j * j + i_cubed;
                if (j_cubed_sum == candidate) {
                    --matches_left;
                    if (matches_left == 0) {
                        return candidate;
                    }
               }
          }
    }
}

Overflow-safe version

Here is a much faster one (but still slow) at 50 bytes which does not overflow before n == 3:

b570 2101 0004 2201 fb02 f502 4355 0013
fb03 f603 fb06 5603 428e d101 3c01 d006
3b01 d8f5 3201 428d d3ee 3101 e7ea 0008
bd70                                   
        .text
        .arch armv6t2
        .thumb
        .globl taxi_safe
        .thumb_func
taxi_safe:
        @ Nickname some registers for clarity
        n .req r0
        candidate .req r1
        i .req r2
        j .req r3
        matches_left .req r4
        i_cubed .req r5
        j_cubed_sum .req r6

        push    {r4-r6, lr}
        @ Start with a candidate of 1 (even though it's impossible)
        movs    candidate, #1
.Lcandidate_loop:
        @ reset match counter
        movs    matches_left, n
        @ start checking cubes
        @ This version loops forwards from 1 and short circuits logically.
        @ It can correctly calculate n == 3.
        @ for (i = 1; i * i * i < candidate; i++) but the check is after the loop
        movs    i, #1
.Li_loop:
        @ i_cubed = i * i * i
        mul     i_cubed, i, i                        @ wide insn
        muls    i_cubed, i
        @ for (j = i; --j;)
        movs    j, i
.Lj_loop:
        @ j_cubed_sum = j * j * j + i_cubed
        mul     j_cubed_sum, j, j                    @ wide insn
        mla     j_cubed_sum, j_cubed_sum, j, i_cubed @ wide insn
        @ Compare to the candidate
        cmp     j_cubed_sum, candidate
        bne     .Lno_match
.Lmatch:
        @ If it is the same, decrement matches_left
        subs    matches_left, #1
        @ Exit if we found all of the matches
        bne     .Lexit
.Lno_match:
        @ Decrement j and loop while non-zero.
        subs    j, #1
        bhi     .Lj_loop
.Lnext_i:
        @ Increment i, and loop if i_cubed is less than candidate.
        adds    i, #1
        cmp     i_cubed, candidate
        blo     .Li_loop
.Lnext_candidate:
        @ Next candidate.
        adds    candidate, #1
        b       .Lcandidate_loop
.Lexit:
        movs    r0, candidate
        pop     {r4-r6, pc}

This one is significantly faster, and does not overflow before n == 3.

Instead of looping i backwards from candidate, we loop forwards from 1, and also short circuit when i * i * i >= candidate, although we do run the inner loop with this condition first so it is still very redundant.

\$\endgroup\$

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.