Taxicab numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added Wren) |
m (→{{header|Wren}}: Minor tidy) |
||
(28 intermediate revisions by 18 users not shown) | |||
Line 1:
{{task|Mathematics}}
[[File:taxi1729.png|
A [[wp:Hardy–Ramanujan number|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.
Line 6:
The first taxicab number is '''1729''', which is:
::: 1<sup>3</sup> + 12<sup>3</sup> and also
::: 9<sup>3</sup> + 10<sup>3</sup>.
Line 27:
;See also:
* [
* [http://mathworld.wolfram.com/Hardy-RamanujanNumber.html Hardy-Ramanujan Number] on MathWorld.
* [http://mathworld.wolfram.com/TaxicabNumber.html taxicab number] on MathWorld.
* [
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V cubes = (1..1199).map(x -> Int64(x) ^ 3)
[Int64 = Int64] crev
L(x3) cubes
crev[x3] = L.index + 1
V sums = sorted(multiloop_filtered(cubes, cubes, (x, y) -> y < x, (x, y) -> x + y))
V idx = 0
L(i) 1 .< sums.len - 1
I sums[i - 1] != sums[i] & sums[i] == sums[i + 1]
idx++
I (idx > 25 & idx < 2000) | idx > 2006
L.continue
V n = sums[i]
[(Int64, Int64)] p
L(x) cubes
I n - x < x
L.break
I n - x C crev
p.append((crev[x], crev[n - x]))
print(‘#4: #10’.format(idx, n), end' ‘ ’)
L(x1, x2) p
print(‘ = #4^3 + #4^3’.format(x1, x2), end' ‘ ’)
print()</syntaxhighlight>
{{out}}
<pre>
1: 1729 = 1^3 + 12^3 = 9^3 + 10^3
2: 4104 = 2^3 + 16^3 = 9^3 + 15^3
3: 13832 = 2^3 + 24^3 = 18^3 + 20^3
4: 20683 = 10^3 + 27^3 = 19^3 + 24^3
5: 32832 = 4^3 + 32^3 = 18^3 + 30^3
6: 39312 = 2^3 + 34^3 = 15^3 + 33^3
7: 40033 = 9^3 + 34^3 = 16^3 + 33^3
8: 46683 = 3^3 + 36^3 = 27^3 + 30^3
9: 64232 = 17^3 + 39^3 = 26^3 + 36^3
10: 65728 = 12^3 + 40^3 = 31^3 + 33^3
11: 110656 = 4^3 + 48^3 = 36^3 + 40^3
12: 110808 = 6^3 + 48^3 = 27^3 + 45^3
13: 134379 = 12^3 + 51^3 = 38^3 + 43^3
14: 149389 = 8^3 + 53^3 = 29^3 + 50^3
15: 165464 = 20^3 + 54^3 = 38^3 + 48^3
16: 171288 = 17^3 + 55^3 = 24^3 + 54^3
17: 195841 = 9^3 + 58^3 = 22^3 + 57^3
18: 216027 = 3^3 + 60^3 = 22^3 + 59^3
19: 216125 = 5^3 + 60^3 = 45^3 + 50^3
20: 262656 = 8^3 + 64^3 = 36^3 + 60^3
21: 314496 = 4^3 + 68^3 = 30^3 + 66^3
22: 320264 = 18^3 + 68^3 = 32^3 + 66^3
23: 327763 = 30^3 + 67^3 = 51^3 + 58^3
24: 373464 = 6^3 + 72^3 = 54^3 + 60^3
25: 402597 = 42^3 + 69^3 = 56^3 + 61^3
2000: 1671816384 = 428^3 + 1168^3 = 940^3 + 944^3
2001: 1672470592 = 29^3 + 1187^3 = 632^3 + 1124^3
2002: 1673170856 = 458^3 + 1164^3 = 828^3 + 1034^3
2003: 1675045225 = 522^3 + 1153^3 = 744^3 + 1081^3
2004: 1675958167 = 492^3 + 1159^3 = 711^3 + 1096^3
2005: 1676926719 = 63^3 + 1188^3 = 714^3 + 1095^3
2006: 1677646971 = 99^3 + 1188^3 = 891^3 + 990^3
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f TAXICAB_NUMBERS.AWK
BEGIN {
stop = 99
for (a=1; a<=stop; a++) {
for (b=1; b<=stop; b++) {
n1 = a^3 + b^3
for (c=1; c<=stop; c++) {
if (a == c) { continue }
for (d=1; d<=stop; d++) {
n2 = c^3 + d^3
if (n1 == n2 && (a != d || b != c)) {
if (n1 in arr) { continue }
arr[n1] = sprintf("%7d = %2d^3 + %2d^3 = %2d^3 + %2d^3",n1,a,b,c,d)
}
}
}
}
}
PROCINFO["sorted_in"] = "@ind_num_asc"
for (i in arr) {
if (++count <= 25) {
printf("%2d: %s\n",count,arr[i])
}
}
printf("\nThere are %d taxicab numbers using bounds of %d\n",length(arr),stop)
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
1: 1729 = 1^3 + 12^3 = 9^3 + 10^3
2: 4104 = 2^3 + 16^3 = 9^3 + 15^3
3: 13832 = 2^3 + 24^3 = 18^3 + 20^3
4: 20683 = 10^3 + 27^3 = 19^3 + 24^3
5: 32832 = 4^3 + 32^3 = 18^3 + 30^3
6: 39312 = 2^3 + 34^3 = 15^3 + 33^3
7: 40033 = 9^3 + 34^3 = 16^3 + 33^3
8: 46683 = 3^3 + 36^3 = 27^3 + 30^3
9: 64232 = 17^3 + 39^3 = 26^3 + 36^3
10: 65728 = 12^3 + 40^3 = 31^3 + 33^3
11: 110656 = 4^3 + 48^3 = 36^3 + 40^3
12: 110808 = 6^3 + 48^3 = 27^3 + 45^3
13: 134379 = 12^3 + 51^3 = 38^3 + 43^3
14: 149389 = 8^3 + 53^3 = 29^3 + 50^3
15: 165464 = 20^3 + 54^3 = 38^3 + 48^3
16: 171288 = 17^3 + 55^3 = 24^3 + 54^3
17: 195841 = 9^3 + 58^3 = 22^3 + 57^3
18: 216027 = 3^3 + 60^3 = 22^3 + 59^3
19: 216125 = 5^3 + 60^3 = 45^3 + 50^3
20: 262656 = 8^3 + 64^3 = 36^3 + 60^3
21: 314496 = 4^3 + 68^3 = 30^3 + 66^3
22: 320264 = 18^3 + 68^3 = 32^3 + 66^3
23: 327763 = 30^3 + 67^3 = 51^3 + 58^3
24: 373464 = 6^3 + 72^3 = 54^3 + 60^3
25: 402597 = 42^3 + 69^3 = 56^3 + 61^3
There are 45 taxicab numbers using bounds of 99
</pre>
=={{header|Befunge}}==
This is quite slow in most interpreters, although a decent compiler should allow it to complete in a matter of seconds. Regardless of the speed, though, the range in a standard Befunge-93 implementation is limited to the first 64 numbers in the series, after which the 8-bit memory cells will overflow. That range could be extended in Befunge-98, but realistically you're not likely to wait that long for the results.
<
>004p:0>1+24p:24g\:24g>>1+:34p::**24g::**+-|p>9,,,14v,
,,,"^3 + ^3= ^3 + ^3".\,,,9"= ".:\_v#g40g43<^v,,,,.g<^
5+,$$$\1+:38*`#@_\::"~"1+:24p34p0\0>14p24g04^>,04g.,,5</
{{out}}
Line 72 ⟶ 197:
=={{header|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).
<
#include <stdlib.h>
Line 155 ⟶ 280:
}
return 0;
}</
{{out}}
<pre>
Line 191 ⟶ 316:
2006:1677646971 = 990^3 + 891^3 = 1188^3 + 99^3
</pre>
=={{header|C++}}==
{{trans|C#}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
template <typename T>
size_t indexOf(const std::vector<T> &v, const T &k) {
auto it = std::find(v.cbegin(), v.cend(), k);
if (it != v.cend()) {
return it - v.cbegin();
}
return -1;
}
int main() {
std::vector<size_t> cubes;
auto dump = [&cubes](const std::string &title, const std::map<int, size_t> &items) {
std::cout << title;
for (auto &item : items) {
std::cout << "\n" << std::setw(4) << item.first << " " << std::setw(10) << item.second;
for (auto x : cubes) {
auto y = item.second - x;
if (y < x) {
break;
}
if (std::count(cubes.begin(), cubes.end(), y)) {
std::cout << " = " << std::setw(4) << indexOf(cubes, y) << "^3 + " << std::setw(3) << indexOf(cubes, x) << "^3";
}
}
}
};
std::vector<size_t> sums;
// create sorted list of cube sums
for (size_t i = 0; i < 1190; i++) {
auto cube = i * i * i;
cubes.push_back(cube);
for (auto j : cubes) {
sums.push_back(cube + j);
}
}
std::sort(sums.begin(), sums.end());
// now seek consecutive sums that match
auto nm1 = sums[0];
auto n = sums[1];
int idx = 0;
std::map<int, size_t> task;
std::map<int, size_t> trips;
auto it = sums.cbegin();
auto end = sums.cend();
it++;
it++;
while (it != end) {
auto np1 = *it;
if (nm1 == np1) {
trips.emplace(idx, n);
}
if (nm1 != n && n == np1) {
if (++idx <= 25 || idx >= 2000 == idx <= 2006) {
task.emplace(idx, n);
}
}
nm1 = n;
n = np1;
it++;
}
dump("First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:", task);
std::stringstream ss;
ss << "\n\nFound " << trips.size() << " triple Taxicabs under 2007:";
dump(ss.str(), trips);
return 0;
}</syntaxhighlight>
{{out}}
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:
1 1729 = 12^3 + 1^3 = 10^3 + 9^3
2 4104 = 16^3 + 2^3 = 15^3 + 9^3
3 13832 = 24^3 + 2^3 = 20^3 + 18^3
4 20683 = 27^3 + 10^3 = 24^3 + 19^3
5 32832 = 32^3 + 4^3 = 30^3 + 18^3
6 39312 = 34^3 + 2^3 = 33^3 + 15^3
7 40033 = 34^3 + 9^3 = 33^3 + 16^3
8 46683 = 36^3 + 3^3 = 30^3 + 27^3
9 64232 = 39^3 + 17^3 = 36^3 + 26^3
10 65728 = 40^3 + 12^3 = 33^3 + 31^3
11 110656 = 48^3 + 4^3 = 40^3 + 36^3
12 110808 = 48^3 + 6^3 = 45^3 + 27^3
13 134379 = 51^3 + 12^3 = 43^3 + 38^3
14 149389 = 53^3 + 8^3 = 50^3 + 29^3
15 165464 = 54^3 + 20^3 = 48^3 + 38^3
16 171288 = 55^3 + 17^3 = 54^3 + 24^3
17 195841 = 58^3 + 9^3 = 57^3 + 22^3
18 216027 = 60^3 + 3^3 = 59^3 + 22^3
19 216125 = 60^3 + 5^3 = 50^3 + 45^3
20 262656 = 64^3 + 8^3 = 60^3 + 36^3
21 314496 = 68^3 + 4^3 = 66^3 + 30^3
22 320264 = 68^3 + 18^3 = 66^3 + 32^3
23 327763 = 67^3 + 30^3 = 58^3 + 51^3
24 373464 = 72^3 + 6^3 = 60^3 + 54^3
25 402597 = 69^3 + 42^3 = 61^3 + 56^3
2000 1671816384 = 1168^3 + 428^3 = 944^3 + 940^3
2001 1672470592 = 1187^3 + 29^3 = 1124^3 + 632^3
2002 1673170856 = 1164^3 + 458^3 = 1034^3 + 828^3
2003 1675045225 = 1153^3 + 522^3 = 1081^3 + 744^3
2004 1675958167 = 1159^3 + 492^3 = 1096^3 + 711^3
2005 1676926719 = 1188^3 + 63^3 = 1095^3 + 714^3
2006 1677646971 = 1188^3 + 99^3 = 990^3 + 891^3
Found 10 triple Taxicabs under 2007:
455 87539319 = 436^3 + 167^3 = 423^3 + 228^3 = 414^3 + 255^3
535 119824488 = 493^3 + 11^3 = 492^3 + 90^3 = 428^3 + 346^3
588 143604279 = 522^3 + 111^3 = 460^3 + 359^3 = 423^3 + 408^3
655 175959000 = 560^3 + 70^3 = 552^3 + 198^3 = 525^3 + 315^3
888 327763000 = 670^3 + 300^3 = 661^3 + 339^3 = 580^3 + 510^3
1299 700314552 = 872^3 + 334^3 = 846^3 + 456^3 = 828^3 + 510^3
1398 804360375 = 930^3 + 15^3 = 927^3 + 198^3 = 920^3 + 295^3
1515 958595904 = 986^3 + 22^3 = 984^3 + 180^3 = 856^3 + 692^3
1660 1148834232 = 1044^3 + 222^3 = 920^3 + 718^3 = 846^3 + 816^3
1837 1407672000 = 1120^3 + 140^3 = 1104^3 + 396^3 = 1050^3 + 630^3</pre>
=={{header|C sharp}}==
<
using System.Collections.Generic;
using System.Linq;
Line 268 ⟶ 527:
}
}
}</
===Alternate Algorithm===
Based on the second Python example where only the sums are stored and sorted. Also shows the first 10 Taxicab Number triples.
<syntaxhighlight lang="csharp">using System; using static System.Console;
using System.Collections.Generic; using System.Linq;
class Program {
static void Main(string[] args) {
List<uint> cubes = new List<uint>(), sums = new List<uint>();
void dump(string title, Dictionary <int, uint> items) {
Write(title); foreach (var item in items) {
Write("\n{0,4} {1,10}", item.Key, item.Value);
foreach (uint x in cubes) { uint y = item.Value - x;
if (y < x) break; if (cubes.Contains(y))
Write(" = {0,4}³ + {1,3}³", cubes.IndexOf(y), cubes.IndexOf(x));
} } }
DateTime st = DateTime.Now;
// create sorted list of cube sums
for (uint i = 0, cube; i < 1190; i++) { cube = i * i * i;
cubes.Add(cube); foreach (uint j in cubes)
sums.Add(cube + j); } sums.Sort();
// now seek consecutive sums that match
uint nm1 = sums[0], n = sums[1]; int idx = 0;
Dictionary <int, uint> task = new Dictionary <int, uint>(),
trips = new Dictionary <int, uint>();
foreach (var np1 in sums.Skip(2)) {
if (nm1 == np1) trips.Add(idx, n); if (nm1 != n && n == np1)
if (++idx <= 25 || idx >= 2000 == idx <= 2006)
task.Add(idx, n); nm1 = n; n = np1; }
// show results
dump("First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:", task);
dump(string.Format("\n\nFound {0} triple Taxicabs under {1}:", trips.Count, 2007), trips);
Write("\n\nElasped: {0}ms", (DateTime.Now - st).TotalMilliseconds); }
}</syntaxhighlight>
{{out}} (from TIO.run)
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:
1 1729 = 12³ + 1³ = 10³ + 9³
2 4104 = 16³ + 2³ = 15³ + 9³
3 13832 = 24³ + 2³ = 20³ + 18³
4 20683 = 27³ + 10³ = 24³ + 19³
5 32832 = 32³ + 4³ = 30³ + 18³
6 39312 = 34³ + 2³ = 33³ + 15³
7 40033 = 34³ + 9³ = 33³ + 16³
8 46683 = 36³ + 3³ = 30³ + 27³
9 64232 = 39³ + 17³ = 36³ + 26³
10 65728 = 40³ + 12³ = 33³ + 31³
11 110656 = 48³ + 4³ = 40³ + 36³
12 110808 = 48³ + 6³ = 45³ + 27³
13 134379 = 51³ + 12³ = 43³ + 38³
14 149389 = 53³ + 8³ = 50³ + 29³
15 165464 = 54³ + 20³ = 48³ + 38³
16 171288 = 55³ + 17³ = 54³ + 24³
17 195841 = 58³ + 9³ = 57³ + 22³
18 216027 = 60³ + 3³ = 59³ + 22³
19 216125 = 60³ + 5³ = 50³ + 45³
20 262656 = 64³ + 8³ = 60³ + 36³
21 314496 = 68³ + 4³ = 66³ + 30³
22 320264 = 68³ + 18³ = 66³ + 32³
23 327763 = 67³ + 30³ = 58³ + 51³
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 = 1188³ + 99³ = 990³ + 891³
Found 10 triple Taxicabs under 2007:
455 87539319 = 436³ + 167³ = 423³ + 228³ = 414³ + 255³
535 119824488 = 493³ + 11³ = 492³ + 90³ = 428³ + 346³
588 143604279 = 522³ + 111³ = 460³ + 359³ = 423³ + 408³
655 175959000 = 560³ + 70³ = 552³ + 198³ = 525³ + 315³
888 327763000 = 670³ + 300³ = 661³ + 339³ = 580³ + 510³
1299 700314552 = 872³ + 334³ = 846³ + 456³ = 828³ + 510³
1398 804360375 = 930³ + 15³ = 927³ + 198³ = 920³ + 295³
1515 958595904 = 986³ + 22³ = 984³ + 180³ = 856³ + 692³
1660 1148834232 = 1044³ + 222³ = 920³ + 718³ = 846³ + 816³
1837 1407672000 = 1120³ + 140³ = 1104³ + 396³ = 1050³ + 630³
Elasped: 78.7948ms</pre>
=={{header|Clojure}}==
<
(:gen-class))
Line 338 ⟶ 683:
(show-result n sample))
}</
{{out}}
Line 379 ⟶ 724:
===High Level Version===
{{trans|Python}}
<
import std.stdio, std.range, std.algorithm, std.typecons, std.string;
Line 397 ⟶ 742:
writeln;
}
}</
{{out}}
<pre> 1: 1729 = 1^3 + 12^3 = 9^3 + 10^3
Line 436 ⟶ 781:
===Heap-Based Version===
{{trans|Java}}
<
struct CubeSum {
Line 500 ⟶ 845:
writeln;
}
}</
{{out}}
<pre> 1: 1729 = 10^3 + 9^3 = 12^3 + 1^3
Line 538 ⟶ 883:
===Low Level Heap-Based Version===
{{trans|C}}
<
alias CubesSumT = uint; // Or ulong.
Line 638 ⟶ 983:
'\n'.putchar;
}
}</
{{out}}
<pre> 1: 1729 = 12^3 + 1^3 = 10^3 + 9^3
Line 676 ⟶ 1,021:
=={{header|DCL}}==
We invoke external utility SORT which I suppose technically speaking is not a formal part of the language but is darn handy at times;
<
$ on control_y then $ goto clean
$ open /write sums_of_cubes sums_of_cubes.txt
Line 730 ⟶ 1,075:
$ clean:
$ close /nolog sorted_sums_of_cubes
$ close /nolog sums_of_cubes</
{{out}}
<pre>$ @taxicab_numbers
Line 765 ⟶ 1,110:
2005: 1676926719 = 1095^3 + 714^3 = 1188^3 + 63^3
2006: 1677646971 = 990^3 + 891^3 = 1188^3 + 99^3</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Taxicab_numbers#Pascal Pascal].
=={{header|EchoLisp}}==
Using the '''heap''' library, and a heap to store the taxicab numbers. For taxi tuples - decomposition in more than two sums - we use the '''group''' function which transforms a list ( 3 5 5 6 8 ...) into ((3) (5 5) (6) ...).
<
(require '(heap compile))
Line 817 ⟶ 1,167:
(for ((i (in-naturals nfrom)) (taxi (sublist taxis nfrom nto)))
(writeln (taxi->string i (first taxi)))))
</syntaxhighlight>
{{out}}
<
(define S (stack 'S)) ;; to push taxis
(define H (make-heap < )) ;; make min heap of all scubes
Line 864 ⟶ 1,214:
1660. 1148834232 = 846^3 + 816^3 = 920^3 + 718^3 = 1044^3 + 222^3
1837. 1407672000 = 1050^3 + 630^3 = 1104^3 + 396^3 = 1120^3 + 140^3
</syntaxhighlight>
=={{header|Elixir}}==
<
def numbers(n \\ 1200) do
(for i <- 1..n, j <- i..n, do: {i,j})
Line 881 ⟶ 1,231:
IO.puts "#{i+1} : #{inspect x}"
end
end)</
{{out}}
Line 917 ⟶ 1,267:
2005 : {1676926719, [{714, 1095}, {63, 1188}]}
2006 : {1677646971, [{891, 990}, {99, 1188}]}
</pre>
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<syntaxhighlight lang="forth">variable taxicablist
variable searched-cubessum
73 constant max-constituent \ uses magic numbers
: cube dup dup * * ;
: cubessum cube swap cube + ;
: ?taxicab ( a b -- c d true | false )
\ does exist an (c, d) such that c^3+d^3 = a^3+b^3 ?
2dup cubessum searched-cubessum !
dup 1- rot 1+ do \ c is possibly in [a+1 b-2]
dup i 1+ do \ d is possibly in [c+1 b-1]
j i cubessum searched-cubessum @ = if drop j i true unloop unloop exit then
loop
loop drop false ;
: swap-taxi ( n -- )
dup 5 cells + swap do
i @ i 5 cells - @ i ! i 5 cells - !
cell +loop ;
: bubble-taxicablist
here 5 cells - taxicablist @ = if exit then \ not for the first one
taxicablist @ here 5 cells - do
i @ i 5 cells - @ > if unloop exit then \ no (more) need to reorder
i swap-taxi
5 cells -loop ;
: store-taxicab ( a b c d -- )
2dup cubessum , swap , , swap , ,
bubble-taxicablist ;
: build-taxicablist
here taxicablist !
max-constituent 3 - 1 do \ a in [ 1 ; max-3 ]
i 3 + max-constituent swap do \ b in [ a+3 ; max ]
j i ?taxicab if j i store-taxicab then
loop
loop ;
: .nextcube cell + dup @ . ." ^3 " ;
: .taxi
dup @ .
." = " .nextcube ." + " .nextcube ." = " .nextcube ." + " .nextcube
drop ;
: taxicab 5 cells * taxicablist @ + ;
: list-taxicabs ( n -- )
0 do
cr I 1+ . ." : "
I taxicab .taxi
loop ;
build-taxicablist
25 list-taxicabs</syntaxhighlight>
{{out}}
<pre>1 : 1729 = 1 ^3 + 12 ^3 = 9 ^3 + 10 ^3
2 : 4104 = 2 ^3 + 16 ^3 = 9 ^3 + 15 ^3
3 : 13832 = 2 ^3 + 24 ^3 = 18 ^3 + 20 ^3
4 : 20683 = 10 ^3 + 27 ^3 = 19 ^3 + 24 ^3
5 : 32832 = 4 ^3 + 32 ^3 = 18 ^3 + 30 ^3
6 : 39312 = 2 ^3 + 34 ^3 = 15 ^3 + 33 ^3
7 : 40033 = 9 ^3 + 34 ^3 = 16 ^3 + 33 ^3
8 : 46683 = 3 ^3 + 36 ^3 = 27 ^3 + 30 ^3
9 : 64232 = 17 ^3 + 39 ^3 = 26 ^3 + 36 ^3
10 : 65728 = 12 ^3 + 40 ^3 = 31 ^3 + 33 ^3
11 : 110656 = 4 ^3 + 48 ^3 = 36 ^3 + 40 ^3
12 : 110808 = 6 ^3 + 48 ^3 = 27 ^3 + 45 ^3
13 : 134379 = 12 ^3 + 51 ^3 = 38 ^3 + 43 ^3
14 : 149389 = 8 ^3 + 53 ^3 = 29 ^3 + 50 ^3
15 : 165464 = 20 ^3 + 54 ^3 = 38 ^3 + 48 ^3
16 : 171288 = 17 ^3 + 55 ^3 = 24 ^3 + 54 ^3
17 : 195841 = 9 ^3 + 58 ^3 = 22 ^3 + 57 ^3
18 : 216027 = 3 ^3 + 60 ^3 = 22 ^3 + 59 ^3
19 : 216125 = 5 ^3 + 60 ^3 = 45 ^3 + 50 ^3
20 : 262656 = 8 ^3 + 64 ^3 = 36 ^3 + 60 ^3
21 : 314496 = 4 ^3 + 68 ^3 = 30 ^3 + 66 ^3
22 : 320264 = 18 ^3 + 68 ^3 = 32 ^3 + 66 ^3
23 : 327763 = 30 ^3 + 67 ^3 = 51 ^3 + 58 ^3
24 : 373464 = 6 ^3 + 72 ^3 = 54 ^3 + 60 ^3
25 : 402597 = 42 ^3 + 69 ^3 = 56 ^3 + 61 ^3 ok</pre>
One can use 1200 as magic number rather than 73 and display 2006 taxicab numbers ('2006 list-taxicabs') but the 10 triple taxicabs will slide the count...
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
! A non-bruteforce approach
PROGRAM POOKA
IMPLICIT NONE
!
! PARAMETER definitions
!
INTEGER , PARAMETER :: NVARS = 25
!
! Local variables
!
REAL :: f1
REAL :: f2
INTEGER :: hits
INTEGER :: s
INTEGER :: TAXICAB
hits = 0
s = 0
f1 = SECOND()
DO WHILE ( hits<NVARS )
s = s + 1
hits = hits + TAXICAB(s)
END DO
f2 = SECOND()
PRINT * , 'elapsed time = ' , f2 - f1 , 'For ' , NVARS , ' Variables'
STOP
END PROGRAM POOKA
FUNCTION TAXICAB(N)
IMPLICIT NONE
!
! Dummy arguments
!
INTEGER :: N
INTEGER :: TAXICAB
INTENT (IN) N
!
! Local variables
!
INTEGER :: holder
INTEGER :: oldx
INTEGER :: oldy
INTEGER :: s
INTEGER :: x
INTEGER :: y
real*8,parameter :: xpon=(1.0D0/3.0D0)
!
x = 0
holder = 0
oldx = 0
oldy = 0
TAXICAB = 0
y = INT(N**xpon)
DO WHILE ( x<=y )
s = x**3 + y**3
IF( s<N )THEN
x = x + 1
ELSE IF( s>N )THEN
y = y - 1
ELSE
IF( holder==s )THEN ! Print the last value and this one that correspond
WRITE(6 , 34)s , '(' , x**3 , y**3 , ')' , '(' , oldx**3 , oldy**3 , ')'
34 FORMAT(1x , i12 , 10x , 1A1 , i12 , 2x , i12 , 1A1 , 10x , 1A1 , i12 , 2x ,&
& i12 , 1A1)
TAXICAB = 1 ! Indicate that we found a Taxi Number
END IF
holder = s ! Set to the number that appears a potential cab number
oldx = x ! Retain the values for the 2 cubes
oldy = y
x = x + 1 ! Keep looking
y = y - 1
END IF
END DO
RETURN
END FUNCTION TAXICAB
</syntaxhighlight>
{{out}}
<pre> Print first 25 numbers
1729 ( 729 1000) ( 1 1728)
4104 ( 729 3375) ( 8 4096)
13832 ( 5832 8000) ( 8 13824)
20683 ( 6859 13824) ( 1000 19683)
32832 ( 5832 27000) ( 64 32768)
39312 ( 3375 35937) ( 8 39304)
40033 ( 4096 35937) ( 729 39304)
46683 ( 19683 27000) ( 27 46656)
64232 ( 17576 46656) ( 4913 59319)
65728 ( 29791 35937) ( 1728 64000)
110656 ( 46656 64000) ( 64 110592)
110808 ( 19683 91125) ( 216 110592)
134379 ( 54872 79507) ( 1728 132651)
149389 ( 24389 125000) ( 512 148877)
165464 ( 54872 110592) ( 8000 157464)
171288 ( 13824 157464) ( 4913 166375)
195841 ( 10648 185193) ( 729 195112)
216027 ( 10648 205379) ( 27 216000)
216125 ( 91125 125000) ( 125 216000)
262656 ( 46656 216000) ( 512 262144)
314496 ( 27000 287496) ( 64 314432)
320264 ( 32768 287496) ( 5832 314432)
327763 ( 132651 195112) ( 27000 300763)
373464 ( 157464 216000) ( 216 373248)
402597 ( 175616 226981) ( 74088 328509)
elapsed time = 4.68750000E-02 For 25 Variables
----- 2000 to 2006 numbers
1671816384 ( 830584000 841232384) ( 78402752 1593413632)
1672470592 ( 252435968 1420034624) ( 24389 1672446203)
1673170856 ( 567663552 1105507304) ( 96071912 1577098944)
1675045225 ( 411830784 1263214441) ( 142236648 1532808577)
1675958167 ( 359425431 1316532736) ( 119095488 1556862679)
1676926719 ( 363994344 1312932375) ( 250047 1676676672)
1677646971 ( 707347971 970299000) ( 970299 1676676672)
</pre>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,019 ⟶ 1,581:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> Print first 25 numbers
Line 1,060 ⟶ 1,622:
=={{header|Go}}==
<
import (
Line 1,172 ⟶ 1,734:
}
}
}</
{{out}}
<pre>
Line 1,219 ⟶ 1,781:
=={{header|Haskell}}==
<
import Data.Function (on)
Line 1,256 ⟶ 1,818:
]
where
term r c l = ["(", show r, "^3=", show c, ")", l]</
{{Out}}
<pre> 1. 1729 = ( 1^3= 1) + ( 12^3= 1728) or ( 9^3= 729) + ( 10^3= 1000)
Line 1,293 ⟶ 1,855:
=={{header|J}}==
<
triples=: /:~ ~. ,/ (+ , /:~@,)"0/~cubes NB. ordered pairs of cubes (each with their sum)
candidates=: ;({."#. <@(0&#`({.@{.(;,)<@}."1)@.(1<#))/. ])triples
Line 1,349 ⟶ 1,911:
├──┼──────┼────────────┼─────────────┤
│25│402597│74088 328509│175616 226981│
└──┴──────┴────────────┴─────────────┘</
Explanation:
Line 1,367 ⟶ 1,929:
Extra credit:
<
┌────┬──────────┬────────────────────┬────────────────────┬┐
│2000│1671816384│78402752 1593413632 │830584000 841232384 ││
Line 1,382 ⟶ 1,944:
├────┼──────────┼────────────────────┼────────────────────┼┤
│2006│1677646971│970299 1676676672 │707347971 970299000 ││
└────┴──────────┴────────────────────┴────────────────────┴┘</
The extra blank box at the end is because when tackling this large of a data set, some sums can be achieved by three different pairs of cubes.
=={{header|Java}}==
<
import java.util.ArrayList;
import java.util.List;
Line 1,461 ⟶ 2,023:
}
}
}</
{{out}}
<pre>
Line 1,499 ⟶ 2,061:
=={{header|JavaScript}}==
<
s3s = {}
for (var n = 1, e = 1200; n < e; n += 1) n3s[n] = n * n * n
Line 1,525 ⟶ 2,087:
}
document.write('<br>')
}</
{{out}}
1: 1729 = 1<sup>3</sup>+12<sup>3</sup> = 9<sup>3</sup>+10<sup>3</sup>
Line 1,573 ⟶ 2,135:
{{works with|jq|1.4}}
<
# Only cubes of 1 to ($in-1) are considered; the listing is therefore truncated
# as it might not capture taxicab numbers greater than $in ^ 3.
Line 1,611 ⟶ 2,173:
| [ ., [taxicabs0] ]
| until( .[1] | length >= $m; (.[0] + $increment) | [., [taxicabs0]] )
| .[1][0:$n] ;</
'''The task'''
<
| (range(0;25), range(1999;2006)) as $i
| "\($i+1): \($t[$i][0]) ~ \($t[$i][1]) and \($t[$i][2])"</
{{out}}
<
1: 1729 ~ [1,12] and [9,10]
2: 4104 ~ [2,16] and [9,15]
Line 1,650 ⟶ 2,212:
2004: 1675958167 ~ [492,1159] and [711,1096]
2005: 1676926719 ~ [63,1188] and [714,1095]
2006: 1677646971 ~ [99,1188] and [891,990]</
=={{header|Julia}}==
{{trans|Python}}
<
function findtaxinumbers(nmax::Integer)
Line 1,707 ⟶ 2,269:
end
findtaxinumbers(1200)</
{{out}}
Line 1,778 ⟶ 2,340:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.PriorityQueue
Line 1,838 ⟶ 2,400:
println()
}
}</
{{out}}
Line 1,876 ⟶ 2,438:
</pre>
=={{header|
<syntaxhighlight lang="lua">sums, taxis, limit = {}, {}, 1200
for i = 1, limit do
for j = 1, i-1 do
sum = i^3 + j^3
sums[sum] = sums[sum] or {}
table.insert(sums[sum], i.."^3 + "..j.."^3")
end
end
for k,v in pairs(sums) do
if #v > 1 then table.insert(taxis, { sum=k, num=#v, terms=table.concat(v," = ") }) end
end
table.sort(taxis, function(a,b) return a.sum<b.sum end)
for i=1,2006 do
if i<=25 or i>=2000 or taxis[i].num==3 then
print(string.format("%4d%s: %10d = %s", i, taxis[i].num==3 and "*" or " ", taxis[i].sum, taxis[i].terms))
end
end
print("* n=3")</syntaxhighlight>
{{out}}
<pre> 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
455*: 87539319 = 414^3 + 255^3 = 423^3 + 228^3 = 436^3 + 167^3
535*: 119824488 = 428^3 + 346^3 = 492^3 + 90^3 = 493^3 + 11^3
588*: 143604279 = 423^3 + 408^3 = 460^3 + 359^3 = 522^3 + 111^3
655*: 175959000 = 525^3 + 315^3 = 552^3 + 198^3 = 560^3 + 70^3
888*: 327763000 = 580^3 + 510^3 = 661^3 + 339^3 = 670^3 + 300^3
1299*: 700314552 = 828^3 + 510^3 = 846^3 + 456^3 = 872^3 + 334^3
1398*: 804360375 = 920^3 + 295^3 = 927^3 + 198^3 = 930^3 + 15^3
1515*: 958595904 = 856^3 + 692^3 = 984^3 + 180^3 = 986^3 + 22^3
1660*: 1148834232 = 846^3 + 816^3 = 920^3 + 718^3 = 1044^3 + 222^3
1837*: 1407672000 = 1050^3 + 630^3 = 1104^3 + 396^3 = 1120^3 + 140^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
* n=3</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">findTaxi[n_] := Sort[Keys[Select[Counts[Flatten[Table[x^3 + y^3, {x, 1, n}, {y, x, n}]]], GreaterThan[1]]]];
Take[findTaxiNumbers[100], 25]
found=findTaxiNumbers[1200][[2000 ;; 2005]]
Map[Reduce[x^3 + y^3 == # && x >= y && x > 0 && y > 0, {x, y}, Integers] &, found]</
{{out}}
<pre>{1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728, 110656, 110808, 134379, 149389, 165464, 171288, 195841, 216027, 216125, 262656, 314496, 320264, 327763, 373464, 402597}
{1671816384, 1672470592, 1673170856, 1675045225, 1675958167, 1676926719}
{(x == 944 && y == 940) || (x == 1168 && y == 428),
(x == 1124 && y == 632) || (x == 1187 && y == 29),
Line 1,892 ⟶ 2,516:
(x == 1096 && y == 711) || (x == 1159 && y == 492),
(x == 1095 && y == 714) || (x == 1188 && y == 63)}</pre>
=={{header|Nim}}==
{{trans|Python}}
This is a translation of the Python version which uses a heap.
Python generators have been translated as Nim iterators. We used inline iterators as code expansion is not a problem in this case and performances are better. We formatted the output as in the D version.
Execution time is excellent: about 45 ms on our laptop (I5).
<syntaxhighlight lang="nim">import heapqueue, strformat
type
CubeSum = tuple[x, y, value: int]
# Comparison function needed for the heap queues.
proc `<`(c1, c2: CubeSum): bool = c1.value < c2.value
template cube(n: int): int = n * n * n
iterator cubesum(): CubeSum =
var queue: HeapQueue[CubeSum]
var n = 1
while true:
while queue.len == 0 or queue[0].value > cube(n):
queue.push (n, 1, cube(n) + 1)
inc n
var s = queue.pop()
yield s
inc s.y
if s.y < s.x: queue.push (s.x, s.y, cube(s.x) + cube(s.y))
iterator taxis(): seq[CubeSum] =
var result: seq[CubeSum] = @[(0, 0, 0)]
for s in cubesum():
if s.value == result[^1].value:
result.add s
else:
if result.len > 1: yield result
result.setLen(0)
result.add s # These two statements are faster than the single result = @[s].
var n = 0
for t in taxis():
inc n
if n > 2006: break
if n <= 25 or n >= 2000:
stdout.write &"{n:4}: {t[0].value:10}"
for s in t:
stdout.write &" = {s.x:4}^3 + {s.y:4}^3"
echo()</syntaxhighlight>
{{out}}
<pre> 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 = 34^3 + 9^3 = 33^3 + 16^3
8: 46683 = 30^3 + 27^3 = 36^3 + 3^3
9: 64232 = 39^3 + 17^3 = 36^3 + 26^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 = 54^3 + 20^3 = 48^3 + 38^3
16: 171288 = 54^3 + 24^3 = 55^3 + 17^3
17: 195841 = 58^3 + 9^3 = 57^3 + 22^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 = 68^3 + 18^3 = 66^3 + 32^3
23: 327763 = 67^3 + 30^3 = 58^3 + 51^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 = 1153^3 + 522^3 = 1081^3 + 744^3
2004: 1675958167 = 1096^3 + 711^3 = 1159^3 + 492^3
2005: 1676926719 = 1095^3 + 714^3 = 1188^3 + 63^3
2006: 1677646971 = 1188^3 + 99^3 = 990^3 + 891^3</pre>
=={{header|PARI/GP}}==
<
cubes(n)=my(t); for(k=sqrtnint((n-1)\2,3)+1, sqrtnint(n,3), if(ispower(n-k^3, 3, &t), print(n" = \t"k"^3\t+ "t"^3")))
select(taxicab, [1..402597])
apply(cubes, %);</
{{out}}
<pre>%1 = [1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728, 110656, 110808, 134379, 149389, 165464, 171288, 195841, 216027, 216125, 262656, 314496, 320264, 327763, 373464, 402597]
Line 1,961 ⟶ 2,673:
Its impressive, that over all one check takes ~3.5 cpu-cycles on i4330 3.5Ghz
<
uses
sysutils;
Line 2,096 ⟶ 2,808:
writeln('count of solutions ',AllSolHigh);
end.
</syntaxhighlight>
<pre> 1 1729 = 12^3 + 1^3 = 10^3 + 9^3
2 4104 = 16^3 + 2^3 = 15^3 + 9^3
Line 2,115 ⟶ 2,827:
Uses segmentation so memory use is constrained as high values are searched for. Also has parameter to look for Ta(3) and Ta(4) numbers (which is when segmentation is really needed). By default shows the first 25 numbers; with one argument shows that many; with two arguments shows results in the range.
<
my $lim = 1e14; # Ought to be dynamic as should segment size
Line 2,168 ⟶ 2,880:
@retlist = sort { $a->[0] <=> $b->[0] } @retlist;
return @retlist;
}</
{{out}}
<pre>
Line 2,209 ⟶ 2,921:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Taxicab_numbers.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cube_sums</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">// create cubes and sorted list of cube sums</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cubes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1189</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">cube</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cube</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cubes</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">cube</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (706,266 in total)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cube_sums</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">nm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 25 Taxicab Numbers, 2000..2006th, and all interim triples:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">np1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">np1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">nm1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">25</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">2000</span> <span style="color: #008080;">and</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2006</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cubes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span><span style="color: #0000FF;"><</span><span style="color: #000000;">x</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ydx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ydx</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(%3d^3=%9d) + (%4d^3=%10d)"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ydx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d %10d = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" or "</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">np1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
First 25 Taxicab Numbers, 2000..2006th, and all interim triples:
25 402597 = ( 42^3= 74088) + ( 69^3= 328509) or ( 56^3= 175616) + ( 61^3= 226981)
455 87539319 = (167^3= 4657463) + ( 436^3= 82881856) or (228^3= 11852352) + ( 423^3= 75686967) or (255^3= 16581375) + ( 414^3= 70957944)
535 119824488 = ( 11^3= 1331) + ( 493^3= 119823157) or ( 90^3= 729000) + ( 492^3= 119095488) or (346^3= 41421736) + ( 428^3= 78402752)
588 143604279 = (111^3= 1367631) + ( 522^3= 142236648) or (359^3= 46268279) + ( 460^3= 97336000) or (408^3= 67917312) + ( 423^3= 75686967)
655 175959000 = ( 70^3= 343000) + ( 560^3= 175616000) or (198^3= 7762392) + ( 552^3= 168196608) or (315^3= 31255875) + ( 525^3= 144703125)
888 327763000 = (300^3= 27000000) + ( 670^3= 300763000) or (339^3= 38958219) + ( 661^3= 288804781) or (510^3=132651000) + ( 580^3= 195112000)
1299 700314552 = (334^3= 37259704) + ( 872^3= 663054848) or (456^3= 94818816) + ( 846^3= 605495736) or (510^3=132651000) + ( 828^3= 567663552)
1398 804360375 = ( 15^3= 3375) + ( 930^3= 804357000) or (198^3= 7762392) + ( 927^3= 796597983) or (295^3= 25672375) + ( 920^3= 778688000)
1515 958595904 = ( 22^3= 10648) + ( 986^3= 958585256) or (180^3= 5832000) + ( 984^3= 952763904) or (692^3=331373888) + ( 856^3= 627222016)
1660 1148834232 = (222^3= 10941048) + (1044^3=1137893184) or (718^3=370146232) + ( 920^3= 778688000) or (816^3=543338496) + ( 846^3= 605495736)
1837 1407672000 = (140^3= 2744000) + (1120^3=1404928000) or (396^3= 62099136) + (1104^3=1345572864) or (630^3=250047000) + (1050^3=1157625000)
2000 1671816384 = (428^3= 78402752) + (1168^3=1593413632) or (940^3=830584000) + ( 944^3= 841232384)
2001 1672470592 = ( 29^3= 24389) + (1187^3=1672446203) or (632^3=252435968) + (1124^3=1420034624)
2002 1673170856 = (458^3= 96071912) + (1164^3=1577098944) or (828^3=567663552) + (1034^3=1105507304)
2003 1675045225 = (522^3=142236648) + (1153^3=1532808577) or (744^3=411830784) + (1081^3=1263214441)
2004 1675958167 = (492^3=119095488) + (1159^3=1556862679) or (711^3=359425431) + (1096^3=1316532736)
2005 1676926719 = ( 63^3= 250047) + (1188^3=1676676672) or (714^3=363994344) + (1095^3=1312932375)
2006 1677646971 = ( 99^3= 970299) + (1188^3=1676676672) or (891^3=707347971) + ( 990^3= 970299000)
</pre>
=={{header|PicoLisp}}==
<
(off 'B)
Line 2,393 ⟶ 3,030:
(println (car L) (caddr L)) )
(for L (head 7 (nth R 2000))
(println (car L) (caddr L)) )</
{{out}}
Line 2,430 ⟶ 3,067:
1677646971 ((891 990) (99 1188))
</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">#MAX=1189
Macro q3(a,b)
a*a*a+b*b*b
EndMacro
Structure Cap
x.i
y.i
s.i
EndStructure
NewList Taxi.Cap()
For i=1 To #MAX
For j=i To #MAX
AddElement(Taxi()) : Taxi()\s=q3(i,j) : Taxi()\x=i : Taxi()\y=j
Next j
Next i
SortStructuredList(Taxi(),#PB_Sort_Ascending,OffsetOf(Cap\s),TypeOf(Cap\s))
If OpenConsole()
ForEach Taxi()
If sum=Taxi()\s
r$+"="+RSet(Str(Taxi()\x),4)+"³ +"+RSet(Str(Taxi()\y),4)+"³ " : Continue
EndIf
If CountString(r$,"=")>=2 : c+1 : EndIf
If CountString(r$,"=")=2
Select c
Case 1 To 25, 2000 To 2006 : PrintN(RSet(Str(c),5)+": "+RSet(Str(sum),10)+r$)
Case Bool(c>2006) : Break
EndSelect
EndIf
r$=""
sum=Taxi()\s : r$="="+RSet(Str(Taxi()\x),4)+"³ +"+RSet(Str(Taxi()\y),4)+"³ "
Next
PrintN("FIN.") : Input()
EndIf</syntaxhighlight>{{out}}
<pre> 1: 1729= 1³ + 12³ = 9³ + 10³
2: 4104= 2³ + 16³ = 9³ + 15³
3: 13832= 2³ + 24³ = 18³ + 20³
4: 20683= 10³ + 27³ = 19³ + 24³
5: 32832= 4³ + 32³ = 18³ + 30³
6: 39312= 2³ + 34³ = 15³ + 33³
7: 40033= 9³ + 34³ = 16³ + 33³
8: 46683= 3³ + 36³ = 27³ + 30³
9: 64232= 17³ + 39³ = 26³ + 36³
10: 65728= 12³ + 40³ = 31³ + 33³
11: 110656= 4³ + 48³ = 36³ + 40³
12: 110808= 6³ + 48³ = 27³ + 45³
13: 134379= 12³ + 51³ = 38³ + 43³
14: 149389= 8³ + 53³ = 29³ + 50³
15: 165464= 20³ + 54³ = 38³ + 48³
16: 171288= 17³ + 55³ = 24³ + 54³
17: 195841= 9³ + 58³ = 22³ + 57³
18: 216027= 3³ + 60³ = 22³ + 59³
19: 216125= 5³ + 60³ = 45³ + 50³
20: 262656= 8³ + 64³ = 36³ + 60³
21: 314496= 4³ + 68³ = 30³ + 66³
22: 320264= 18³ + 68³ = 32³ + 66³
23: 327763= 30³ + 67³ = 51³ + 58³
24: 373464= 6³ + 72³ = 54³ + 60³
25: 402597= 42³ + 69³ = 56³ + 61³
2000: 1671816384= 428³ +1168³ = 940³ + 944³
2001: 1672470592= 29³ +1187³ = 632³ +1124³
2002: 1673170856= 458³ +1164³ = 828³ +1034³
2003: 1675045225= 522³ +1153³ = 744³ +1081³
2004: 1675958167= 492³ +1159³ = 711³ +1096³
2005: 1676926719= 63³ +1188³ = 714³ +1095³
2006: 1677646971= 99³ +1188³ = 891³ + 990³
FIN.</pre>
=={{header|Python}}==
(Magic number 1201 found by trial and error)
<
from itertools import product
from pprint import pprint as pp
Line 2,449 ⟶ 3,160:
print('...')
for t in enumerate(taxied[2000-1:2000+6], 2000):
pp(t)</
{{out}}
Line 2,487 ⟶ 3,198:
Although, for this task it's simply faster to look up the cubes in the sum when we need to print them, because we can now store and sort only the sums:
<
# for cube root lookup
for x,x3 in enumerate(cubes): crev[x3] = x + 1
Line 2,506 ⟶ 3,217:
print "%4d: %10d"%(idx,n),
for x in p: print " = %4d^3 + %4d^3"%x,
print</
{{out}}Output trimmed to reduce clutter.
<pre>
Line 2,522 ⟶ 3,233:
===Using heapq module===
A priority queue that holds cube sums. When consecutive sums come out with the same value, they are taxis.
<
def cubesum():
Line 2,551 ⟶ 3,262:
if n >= 2006: break
if n <= 25 or n >= 2000:
print(n, x)</
{{out}}
<pre>
Line 2,590 ⟶ 3,301:
This is the straighforward implementation, so it finds
only the first 25 values in a sensible amount of time.
<
(define (cube x) (* x x x))
Line 2,616 ⟶ 3,327:
(when (< p 25)
(loop (add1 p) (add1 n))))
(loop p (add1 n)))))</
{{out}}
<pre>1: 1729 = 1^3 + 12^3 = 9^3 + 10^3
Line 2,648 ⟶ 3,359:
This uses a pretty simple search algorithm that doesn't necessarily return the Taxicab numbers in order. Assuming we want all the Taxicab numbers within some range S to N, we'll search until we find N values. When we find the Nth value, we continue to search up to the cube root of the largest Taxicab number found up to that point. That ensures we will find all of them inside the desired range without needing to search arbitrarily or use magic numbers. Defaults to returning the Taxicab numbers from 1 to 25. Pass in a different start and end value if you want some other range.
<syntaxhighlight lang="raku"
sub MAIN ($start = 1, $end = 25) {
Line 2,678 ⟶ 3,389:
(.value.map({ sprintf "%4d³ + %-s\³", |$_ })).join: ",\t"
for %this_stuff.grep( { $_.value.elems > 1 } ).sort( +*.key )[$start-1..$end-1];
}</
{{out}}With no passed parameters (default):
<pre> 1 1729 => 9³ + 10³, 1³ + 12³
Line 2,716 ⟶ 3,427:
=={{header|REXX}}==
Programming note: to ensure that the taxicab numbers are in order, an extra 10% are generated.
<
parse arg L.1 H.1 L.2 H.2 L.3 H.3 . /*obtain optional arguments from the CL*/
if L.1=='' | L.1=="," then L.1= 1 /*L1 is the low part of 1st range. */
Line 2,763 ⟶ 3,474:
end /*forever*/
end /*i*/
end /*while h>1*/; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,806 ⟶ 3,517:
=={{header|Ring}}==
<
# Project : Taxicab numbers
Line 2,832 ⟶ 3,543:
next
see "ok" + nl
</syntaxhighlight>
Output:
<pre>
Line 2,861 ⟶ 3,572:
25 402597 => 56³ + 61³, 42³ + 69³
ok
</pre>
=={{header|RPL}}==
A priority queue allows to get the first 25th taxicab numbers without being killed by the emulator timedog.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! Code
! Comments
|-
|
≪
{} 1 PQueue SIZE FOR j
IF OVER j ≠ THEN PQueue j GET 1 →LIST + END
NEXT
'PQueue' STO DROP
≫ 'PQPop' STO
≪
0 {} → idx item
≪ 0 1 PQueue SIZE FOR j
PQueue j GET 1 GET
IF DUP2 <
THEN SWAP PQueue j GET 'item' STO j 'idx' STO
END DROP
NEXT
DROP idx item
≫ ≫ 'PQMax' STO
≪ → pos
1 CF PQueue SIZE WHILE DUP 1 FC? AND REPEAT
IF PQueue OVER GET pos GET 3 PICK == THEN 1 SF END
1 -
END
DROP2 1 FS?
≫ ≫ 'PQin?' STO
≪ OVER 3 ^ OVER 3 ^ + ROT ROT
3 →LIST 1 →LIST PQueue + 'PQueue' STO
≫ 'PQAdd' STO
≪ → item
≪ IF item 1 GET LastItem 1 GET == THEN
{} item 1 GET + item 2 GET item 3 GET R→C +
LastItem 2 GET LastItem 3 GET R→C + 1 →LIST
TaxiNums + 'TaxiNums' STO
END
item 'LastItem' STO
≫ ≫ 'StoreIfTwice' STO
≪ WHILE PQueue SIZE REPEAT
PQMax DUP StoreIfTwice LIST→ DROP 4 ROLL PQPop → r c
≪ IF r 1 >
THEN IF r 1 - 2 PQin? NOT
THEN r 1 - c PQAdd END END
IF c 1 > c r > AND
THEN IF c 1 - 3 PQin? NOT
THEN r c 1 - PQAdd END
END
DROP
≫
END
≫ 'TAXI' STO
≪ → n
≪ { 0 0 0 } 'LastItem' STO
{ } DUP 'PQueue' STO 'TaxiNums' STO n n PQAdd
≫ ≫ 'INIT 'STO
|
''( j -- )''
Scan the priority queue
Copy all items except one
''( -- index { PQ_item } )''
Look for PQ item with max value
''( x pos -- boolean )''
''( r, c -- { PQ_item } )''
''( x pos -- boolean )''
PQ item = { r^3+c^3 r c }
''( -- )''
Removing max value from queue - and store it if déjà vu
can we add an item from the row above?
can we add an item from the left column and above diagonal?
''( magic_number -- )''
initialize global variables
|}
The following commands deliver what is required:
70 INIT TAXI
TaxiNums
{{out}}
<pre>
1: { { 1729 (9,10) (1,12) } { 4104 (9,15) (2,16) } { 13832 (18,20) (2,24) } { 20683 (19,24) (10,27) } { 32832 (18,30) (4,32) } { 39312 (15,33) (2,34) } { 40033 (16,33) (9,34) } { 46683 (27,30) (3,36) } { 64232 (26,36) (17,39) } { 65728 (31,33) (12,40) } { 110656 (36,40) (4,48) } { 110808 (27,45) (6,48) } { 134379 (38,43) (12,51) } { 149389 (29,50) (8,53) } { 165464 (38,48) (20,54) } { 171288 (24,54) (17,55) } { 195841 (22,57) (9,58) } { 216027 (22,59) (3,60) } { 216125 (45,50) (5,60) } { 262656 (36,60) (8,64) } { 314496 (30,66) (4,68) } { 320264 (32,66) (18,68) } { 327763 (51,58) (30,67) } { 402597 (56,61) (42,69) } }
</pre>
=={{header|Ruby}}==
<
[*1..nmax].repeated_combination(2).group_by{|x,y| x**3 + y**3}.select{|k,v| v.size>1}.sort
end
Line 2,872 ⟶ 3,714:
[*1..25, *2000...2007].each do |i|
puts "%4d: %10d" % [i, t[i][0]] + t[i][1].map{|a| " = %4d**3 + %4d**3" % a}.join
end</
{{out}}
<pre>
Line 2,910 ⟶ 3,752:
=={{header|Rust}}==
<
use std::collections::HashMap;
use itertools::Itertools;
Line 2,944 ⟶ 3,786:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,972 ⟶ 3,814:
=={{header|Scala}}==
<
import scala.math.pow
implicit class Pairs[A, B]( p:List[(A, B)]) {
def collectPairs:
}
Line 2,986 ⟶ 3,829:
case _ => 0 ->(0, 0)
} // Turn the list into the sum of two cubes and
.collectPairs // Only keep taxi cab numbers with a duplicate
.toList.sortBy(_._1) // Sort the results
Line 3,002 ⟶ 3,845:
case (p, a::b::Nil) => println( "%20d\t(%d\u00b3 + %d\u00b3)\t(%d\u00b3 + %d\u00b3)".format(p,a._1,a._2,b._1,b._2) )
}
}</syntaxhighlight>
{{out}}
<pre>
Line 3,045 ⟶ 3,887:
{{libheader|Scheme/SRFIs}}
<
(import (scheme base)
(scheme write)
Line 3,081 ⟶ 3,923:
(iota 7 1999))
)
</syntaxhighlight>
{{out}}
Line 3,121 ⟶ 3,963:
=={{header|Sidef}}==
{{trans|Raku}}
<
func display (h, start, end) {
Line 3,149 ⟶ 3,991:
}
}
}</
{{out}}
<pre>
Line 3,189 ⟶ 4,031:
2006 1677646971 => 891³ + 990³, 99³ + 1188³
</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">extension Array {
func combinations(_ k: Int) -> [[Element]] {
return Self._combinations(slice: self[startIndex...], k)
}
static func _combinations(slice: Self.SubSequence, _ k: Int) -> [[Element]] {
guard k != 1 else {
return slice.map({ [$0] })
}
guard k != slice.count else {
return [slice.map({ $0 })]
}
let chopped = slice[slice.index(after: slice.startIndex)...]
var res = _combinations(slice: chopped, k - 1).map({ [[slice.first!], $0].flatMap({ $0 }) })
res += _combinations(slice: chopped, k)
return res
}
}
let cubes = (1...).lazy.map({ $0 * $0 * $0 })
let taxis =
Array(cubes.prefix(1201))
.combinations(2)
.reduce(into: [Int: [[Int]]](), { $0[$1[0] + $1[1], default: []].append($1) })
let res =
taxis
.lazy
.filter({ $0.value.count > 1 })
.sorted(by: { $0.key < $1.key })
.map({ ($0.key, $0.value) })
.prefix(2006)
print("First 25 taxicab numbers:")
for taxi in res[..<25] {
print(taxi)
}
print("\n2000th through 2006th taxicab numbers:")
for taxi in res[1999..<2006] {
print(taxi)
}</syntaxhighlight>
{{out}}
<pre>First 25 taxicab numbers:
(1729, [[1, 1728], [729, 1000]])
(4104, [[8, 4096], [729, 3375]])
(13832, [[8, 13824], [5832, 8000]])
(20683, [[1000, 19683], [6859, 13824]])
(32832, [[64, 32768], [5832, 27000]])
(39312, [[8, 39304], [3375, 35937]])
(40033, [[729, 39304], [4096, 35937]])
(46683, [[27, 46656], [19683, 27000]])
(64232, [[4913, 59319], [17576, 46656]])
(65728, [[1728, 64000], [29791, 35937]])
(110656, [[64, 110592], [46656, 64000]])
(110808, [[216, 110592], [19683, 91125]])
(134379, [[1728, 132651], [54872, 79507]])
(149389, [[512, 148877], [24389, 125000]])
(165464, [[8000, 157464], [54872, 110592]])
(171288, [[4913, 166375], [13824, 157464]])
(195841, [[729, 195112], [10648, 185193]])
(216027, [[27, 216000], [10648, 205379]])
(216125, [[125, 216000], [91125, 125000]])
(262656, [[512, 262144], [46656, 216000]])
(314496, [[64, 314432], [27000, 287496]])
(320264, [[5832, 314432], [32768, 287496]])
(327763, [[27000, 300763], [132651, 195112]])
(373464, [[216, 373248], [157464, 216000]])
(402597, [[74088, 328509], [175616, 226981]])
2000th through 2006th taxicab numbers:
(1671816384, [[78402752, 1593413632], [830584000, 841232384]])
(1672470592, [[24389, 1672446203], [252435968, 1420034624]])
(1673170856, [[96071912, 1577098944], [567663552, 1105507304]])
(1675045225, [[142236648, 1532808577], [411830784, 1263214441]])
(1675958167, [[119095488, 1556862679], [359425431, 1316532736]])
(1676926719, [[250047, 1676676672], [363994344, 1312932375]])
(1677646971, [[970299, 1676676672], [707347971, 970299000]])</pre>
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
{{trans|Python}}
<
proc heappush {heapName item} {
Line 3,245 ⟶ 4,176:
for {set n 2000} {$n <= 2006} {incr n} {
puts ${n}:[join [lmap t [taxi $n] {format " %d = %d$3 + %d$3" {*}$t}] ","]
}</
{{out}}
<pre>
Line 3,283 ⟶ 4,214:
=={{header|VBA}}==
<
i As Variant
j As Variant
Line 3,416 ⟶ 4,347:
If (arrLbound < tmpHi) Then Quicksort vArray, arrLbound, tmpHi 'conquer
If (tmpLow < arrUbound) Then Quicksort vArray, tmpLow, arrUbound 'conquer
End Sub</
<pre> 4399 taxis
1 1729 = 9^3 + 10^3 = 1^3 + 12^3
Line 3,477 ⟶ 4,408:
4162 7668767232 = 44^3 +1972^3 = 1384^3 +1712^3 360^3 +1968^3
4359 8849601000 = 1017^3 +1983^3 = 1530^3 +1740^3 900^3 +2010^3</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">
Imports System.Text
Module Module1
Function GetTaxicabNumbers(length As Integer) As IDictionary(Of Long, IList(Of Tuple(Of Integer, Integer)))
Dim sumsOfTwoCubes As New SortedList(Of Long, IList(Of Tuple(Of Integer, Integer)))
For i = 1 To Integer.MaxValue - 1
For j = 1 To Integer.MaxValue - 1
Dim sum = CLng(Math.Pow(i, 3) + Math.Pow(j, 3))
If Not sumsOfTwoCubes.ContainsKey(sum) Then
sumsOfTwoCubes.Add(sum, New List(Of Tuple(Of Integer, Integer)))
End If
sumsOfTwoCubes(sum).Add(Tuple.Create(i, j))
If j >= i Then
Exit For
End If
Next
REM Found that you need to keep going for a while after the length, because higher i values fill in gaps
If sumsOfTwoCubes.AsEnumerable.Count(Function(t) t.Value.Count >= 2) >= length * 1.1 Then
Exit For
End If
Next
Dim values = (From t In sumsOfTwoCubes Where t.Value.Count >= 2 Select t) _
.Take(2006) _
.ToDictionary(Function(u) u.Key, Function(u) u.Value)
Return values
End Function
Sub PrintTaxicabNumbers(values As IDictionary(Of Long, IList(Of Tuple(Of Integer, Integer))))
Dim i = 1
For Each taxicabNumber In values.Keys
Dim output As New StringBuilder
output.AppendFormat("{0,10}" + vbTab + "{1,4}", i, taxicabNumber)
For Each numbers In values(taxicabNumber)
output.AppendFormat(vbTab + "= {0}^3 + {1}^3", numbers.Item1, numbers.Item2)
Next
If i <= 25 OrElse (i >= 2000 AndAlso i <= 2006) Then
Console.WriteLine(output.ToString)
End If
i += 1
Next
End Sub
Sub Main()
Dim taxicabNumbers = GetTaxicabNumbers(2006)
PrintTaxicabNumbers(taxicabNumbers)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre> 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</pre>
=={{header|Wren}}==
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var cubesSum = {}
Line 3,514 ⟶ 4,540:
var t = taxicabs[i-1]
Fmt.lprint("$,5d: $,13d = $3d³ + $,5d³ = $3d³ + $,5d³", [i, t[0], t[1][0], t[1][1], t[2][0], t[2][1]])
}</
{{out}}
Line 3,553 ⟶ 4,579:
2,005: 1,676,926,719 = 63³ + 1,188³ = 714³ + 1,095³
2,006: 1,677,646,971 = 99³ + 1,188³ = 891³ + 990³
</pre>
=={{header|XPL0}}==
Slow, brute force solution.
<syntaxhighlight lang="xpl0">int N, I, J, SI, SJ, Count, Tally;
[Count:= 0; N:= 0;
repeat Tally:= 0;
I:= 1;
repeat J:= I+1;
repeat if N = I*I*I + J*J*J then
[Tally:= Tally+1;
if Tally >= 2 then
[Count:= Count+1;
IntOut(0, Count); Text(0, ": ");
IntOut(0, N); Text(0, " = ");
IntOut(0, SI); Text(0, "^^3 + ");
IntOut(0, SJ); Text(0, "^^3 = ");
IntOut(0, I); Text(0, "^^3 + ");
IntOut(0, J); Text(0, "^^3");
CrLf(0);
J:= 1000; I:= J;
];
SI:= I; SJ:= J;
];
J:= J+1;
until I*I*I + J*J*J > N;
I:= I+1;
until I*I*I*2 > N;
N:= N+1;
until Count >= 25;
]</syntaxhighlight>
{{out}}
<pre>
1: 1729 = 1^3 + 12^3 = 9^3 + 10^3
2: 4104 = 2^3 + 16^3 = 9^3 + 15^3
3: 13832 = 2^3 + 24^3 = 18^3 + 20^3
4: 20683 = 10^3 + 27^3 = 19^3 + 24^3
5: 32832 = 4^3 + 32^3 = 18^3 + 30^3
6: 39312 = 2^3 + 34^3 = 15^3 + 33^3
7: 40033 = 9^3 + 34^3 = 16^3 + 33^3
8: 46683 = 3^3 + 36^3 = 27^3 + 30^3
9: 64232 = 17^3 + 39^3 = 26^3 + 36^3
10: 65728 = 12^3 + 40^3 = 31^3 + 33^3
11: 110656 = 4^3 + 48^3 = 36^3 + 40^3
12: 110808 = 6^3 + 48^3 = 27^3 + 45^3
13: 134379 = 12^3 + 51^3 = 38^3 + 43^3
14: 149389 = 8^3 + 53^3 = 29^3 + 50^3
15: 165464 = 20^3 + 54^3 = 38^3 + 48^3
16: 171288 = 17^3 + 55^3 = 24^3 + 54^3
17: 195841 = 9^3 + 58^3 = 22^3 + 57^3
18: 216027 = 3^3 + 60^3 = 22^3 + 59^3
19: 216125 = 5^3 + 60^3 = 45^3 + 50^3
20: 262656 = 8^3 + 64^3 = 36^3 + 60^3
21: 314496 = 4^3 + 68^3 = 30^3 + 66^3
22: 320264 = 18^3 + 68^3 = 32^3 + 66^3
23: 327763 = 30^3 + 67^3 = 51^3 + 58^3
24: 373464 = 6^3 + 72^3 = 54^3 + 60^3
25: 402597 = 42^3 + 69^3 = 56^3 + 61^3
</pre>
Line 3,558 ⟶ 4,643:
{{trans|D}}
An array of bytes is used to hold n, where array[n³+m³]==n.
<
const HeapSZ=0d5_000_000;
iCubes:=[1..120].apply("pow",3);
Line 3,575 ⟶ 4,660:
}
taxiNums.sort(fcn([(a,_)],[(b,_)]){ a<b })
}</
<
[n..].zip(taxiNums).pump(Console.println,fcn([(n,t)]){
"%4d: %10,d = %2d\u00b3 + %2d\u00b3 = %2d\u00b3 + %2d\u00b3".fmt(n,t.xplode())
Line 3,582 ⟶ 4,667:
}
taxiNums:=taxiCabNumbers(); // 63 pairs
taxiNums[0,25]:print(1,_);</
{{out}}
<pre>
Line 3,613 ⟶ 4,698:
{{trans|Python}}
Using a binary heap:
<
heap,n:=Heap(fcn([(a,_)],[(b,_)]){ a<=b }), 1; // heap cnt maxes out @ 244
while(1){
Line 3,642 ⟶ 4,727:
if(n >= 2006) break;
if(n <= 25 or n >= 2000) println(n,": ",x);
}</
And a quickie heap implementation:
<
fcn init(lteqFcn='<=){
var [const, private] heap=List().pad(64,Void); // a power of 2
Line 3,681 ⟶ 4,766:
var [proxy] top=fcn { if(cnt==0) Void else heap[0] };
var [proxy] empty=fcn{ (not cnt) };
}</
{{out}}
<pre>
Line 3,702 ⟶ 4,787:
You cannot fit the whole 1625-entry table of cubes (and this program on top) into the 16K ZX Spectrum. Replace all 1625s with 1200s to resolve; numerically unjustified as an exhaustive search, but we know this will be sufficient to find the 2006th number. Eventually.
<
20 FOR x=1 TO 1625
30 LET f(x)=x*x*x: REM x*x*x rather than x^3 as the ZX Spectrum's exponentiation function is legendarily slow
Line 3,737 ⟶ 4,822:
340 NEXT n
350 NEXT m
360 NEXT x</
{{out}}
Line 3,755 ⟶ 4,840:
This program produces the first 25 Taxicab numbers. It is written with speed in mind.
The runtime is about 45 minutes on a ZX Spectrum (3.5 Mhz).
<
20 DIM H(50): DIM Y(50,2): FOR D=1 TO 72: LET F(D)=D*D*D: NEXT D
30 FOR A=1 TO 58: FOR B=A+1 TO 72: LET S=F(A)+F(B): FOR D=B-1 TO A STEP -1
Line 3,775 ⟶ 4,860:
151 LPRINT T;"^3+";Y(A,2)-T*65536;"^3"
160 NEXT A: PRINT
170 STOP</
{{out}}
<pre>1:1729=1^3+12^3=9^3+10^3
|