Taxicab numbers: Difference between revisions
Content added Content deleted
Keithpinson (talk | contribs) (Updated for compatibility with Scala 3) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 36: | Line 36: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">V cubes = (1..1199).map(x -> Int64(x) ^ 3) |
||
[Int64 = Int64] crev |
[Int64 = Int64] crev |
||
L(x3) cubes |
L(x3) cubes |
||
Line 60: | Line 60: | ||
L(x1, x2) p |
L(x1, x2) p |
||
print(‘ = #4^3 + #4^3’.format(x1, x2), end' ‘ ’) |
print(‘ = #4^3 + #4^3’.format(x1, x2), end' ‘ ’) |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 99: | Line 99: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f TAXICAB_NUMBERS.AWK |
# syntax: GAWK -f TAXICAB_NUMBERS.AWK |
||
BEGIN { |
BEGIN { |
||
Line 127: | Line 127: | ||
exit(0) |
exit(0) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 162: | Line 162: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="befunge">v+1$$<_v#!`**::+1g42$$_v#<!`**::+1g43\g43::<<v,,.g42,< |
||
>004p:0>1+24p:24g\:24g>>1+:34p::**24g::**+-|p>9,,,14v, |
>004p:0>1+24p:24g\:24g>>1+:34p::**24g::**+-|p>9,,,14v, |
||
,,,"^3 + ^3= ^3 + ^3".\,,,9"= ".:\_v#g40g43<^v,,,,.g<^ |
,,,"^3 + ^3= ^3 + ^3".\,,,9"= ".:\_v#g40g43<^v,,,,.g<^ |
||
5+,$$$\1+:38*`#@_\::"~"1+:24p34p0\0>14p24g04^>,04g.,,5</ |
5+,$$$\1+:38*`#@_\::"~"1+:24p34p0\0>14p24g04^>,04g.,,5</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 197: | Line 197: | ||
=={{header|C}}== |
=={{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). |
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). |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 280: | Line 280: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 319: | Line 319: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iomanip> |
#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 403: | Line 403: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen: |
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen: |
||
Line 452: | Line 452: | ||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 527: | Line 527: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
===Alternate Algorithm=== |
===Alternate Algorithm=== |
||
Based on the second Python example where only the sums are stored and sorted. Also shows the first 10 Taxicab Number triples. |
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; |
using System.Collections.Generic; using System.Linq; |
||
Line 565: | Line 565: | ||
dump(string.Format("\n\nFound {0} triple Taxicabs under {1}:", trips.Count, 2007), trips); |
dump(string.Format("\n\nFound {0} triple Taxicabs under {1}:", trips.Count, 2007), trips); |
||
Write("\n\nElasped: {0}ms", (DateTime.Now - st).TotalMilliseconds); } |
Write("\n\nElasped: {0}ms", (DateTime.Now - st).TotalMilliseconds); } |
||
}</ |
}</syntaxhighlight> |
||
{{out}} (from TIO.run) |
{{out}} (from TIO.run) |
||
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen: |
<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen: |
||
Line 616: | Line 616: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(ns test-project-intellij.core |
||
(:gen-class)) |
(:gen-class)) |
||
Line 683: | Line 683: | ||
(show-result n sample)) |
(show-result n sample)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 724: | Line 724: | ||
===High Level Version=== |
===High Level Version=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">void main() /*@safe*/ { |
||
import std.stdio, std.range, std.algorithm, std.typecons, std.string; |
import std.stdio, std.range, std.algorithm, std.typecons, std.string; |
||
Line 742: | Line 742: | ||
writeln; |
writeln; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1: 1729 = 1^3 + 12^3 = 9^3 + 10^3 |
<pre> 1: 1729 = 1^3 + 12^3 = 9^3 + 10^3 |
||
Line 781: | Line 781: | ||
===Heap-Based Version=== |
===Heap-Based Version=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.string, std.container; |
||
struct CubeSum { |
struct CubeSum { |
||
Line 845: | Line 845: | ||
writeln; |
writeln; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1: 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
<pre> 1: 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
||
Line 883: | Line 883: | ||
===Low Level Heap-Based Version=== |
===Low Level Heap-Based Version=== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="d">struct Taxicabs { |
||
alias CubesSumT = uint; // Or ulong. |
alias CubesSumT = uint; // Or ulong. |
||
Line 983: | Line 983: | ||
'\n'.putchar; |
'\n'.putchar; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1: 1729 = 12^3 + 1^3 = 10^3 + 9^3 |
<pre> 1: 1729 = 12^3 + 1^3 = 10^3 + 9^3 |
||
Line 1,021: | Line 1,021: | ||
=={{header|DCL}}== |
=={{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; |
We invoke external utility SORT which I suppose technically speaking is not a formal part of the language but is darn handy at times; |
||
< |
<syntaxhighlight lang="dcl">$ close /nolog sums_of_cubes |
||
$ on control_y then $ goto clean |
$ on control_y then $ goto clean |
||
$ open /write sums_of_cubes sums_of_cubes.txt |
$ open /write sums_of_cubes sums_of_cubes.txt |
||
Line 1,075: | Line 1,075: | ||
$ clean: |
$ clean: |
||
$ close /nolog sorted_sums_of_cubes |
$ close /nolog sorted_sums_of_cubes |
||
$ close /nolog sums_of_cubes</ |
$ close /nolog sums_of_cubes</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>$ @taxicab_numbers |
<pre>$ @taxicab_numbers |
||
Line 1,118: | Line 1,118: | ||
=={{header|EchoLisp}}== |
=={{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) ...). |
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) ...). |
||
< |
<syntaxhighlight lang="scheme"> |
||
(require '(heap compile)) |
(require '(heap compile)) |
||
Line 1,167: | Line 1,167: | ||
(for ((i (in-naturals nfrom)) (taxi (sublist taxis nfrom nto))) |
(for ((i (in-naturals nfrom)) (taxi (sublist taxis nfrom nto))) |
||
(writeln (taxi->string i (first taxi))))) |
(writeln (taxi->string i (first taxi))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="scheme"> |
||
(define S (stack 'S)) ;; to push taxis |
(define S (stack 'S)) ;; to push taxis |
||
(define H (make-heap < )) ;; make min heap of all scubes |
(define H (make-heap < )) ;; make min heap of all scubes |
||
Line 1,214: | Line 1,214: | ||
1660. 1148834232 = 846^3 + 816^3 = 920^3 + 718^3 = 1044^3 + 222^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 |
1837. 1407672000 = 1050^3 + 630^3 = 1104^3 + 396^3 = 1120^3 + 140^3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Taxicab do |
||
def numbers(n \\ 1200) do |
def numbers(n \\ 1200) do |
||
(for i <- 1..n, j <- i..n, do: {i,j}) |
(for i <- 1..n, j <- i..n, do: {i,j}) |
||
Line 1,231: | Line 1,231: | ||
IO.puts "#{i+1} : #{inspect x}" |
IO.puts "#{i+1} : #{inspect x}" |
||
end |
end |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,275: | Line 1,275: | ||
{{works with|gforth|0.7.3}} |
{{works with|gforth|0.7.3}} |
||
< |
<syntaxhighlight lang="forth">variable taxicablist |
||
variable searched-cubessum |
variable searched-cubessum |
||
73 constant max-constituent \ uses magic numbers |
73 constant max-constituent \ uses magic numbers |
||
Line 1,330: | Line 1,330: | ||
build-taxicablist |
build-taxicablist |
||
25 list-taxicabs</ |
25 list-taxicabs</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,363: | Line 1,363: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
< |
<syntaxhighlight lang="fortran"> |
||
! A non-bruteforce approach |
! A non-bruteforce approach |
||
PROGRAM POOKA |
PROGRAM POOKA |
||
Line 1,440: | Line 1,440: | ||
END FUNCTION TAXICAB |
END FUNCTION TAXICAB |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> Print first 25 numbers |
<pre> Print first 25 numbers |
||
Line 1,482: | Line 1,482: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 11-10-2016 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,581: | Line 1,581: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> Print first 25 numbers |
<pre> Print first 25 numbers |
||
Line 1,622: | Line 1,622: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,734: | Line 1,734: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,781: | Line 1,781: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (groupBy, sortOn, tails, transpose) |
||
import Data.Function (on) |
import Data.Function (on) |
||
Line 1,818: | Line 1,818: | ||
] |
] |
||
where |
where |
||
term r c l = ["(", show r, "^3=", show c, ")", l]</ |
term r c l = ["(", show r, "^3=", show c, ")", l]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> 1. 1729 = ( 1^3= 1) + ( 12^3= 1728) or ( 9^3= 729) + ( 10^3= 1000) |
<pre> 1. 1729 = ( 1^3= 1) + ( 12^3= 1728) or ( 9^3= 729) + ( 10^3= 1000) |
||
Line 1,855: | Line 1,855: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">cubes=: 3^~1+i.100 NB. first 100 cubes |
||
triples=: /:~ ~. ,/ (+ , /:~@,)"0/~cubes NB. ordered pairs of cubes (each with their sum) |
triples=: /:~ ~. ,/ (+ , /:~@,)"0/~cubes NB. ordered pairs of cubes (each with their sum) |
||
candidates=: ;({."#. <@(0&#`({.@{.(;,)<@}."1)@.(1<#))/. ])triples |
candidates=: ;({."#. <@(0&#`({.@{.(;,)<@}."1)@.(1<#))/. ])triples |
||
Line 1,911: | Line 1,911: | ||
├──┼──────┼────────────┼─────────────┤ |
├──┼──────┼────────────┼─────────────┤ |
||
│25│402597│74088 328509│175616 226981│ |
│25│402597│74088 328509│175616 226981│ |
||
└──┴──────┴────────────┴─────────────┘</ |
└──┴──────┴────────────┴─────────────┘</syntaxhighlight> |
||
Explanation: |
Explanation: |
||
Line 1,929: | Line 1,929: | ||
Extra credit: |
Extra credit: |
||
< |
<syntaxhighlight lang="j"> x:each 7 {. 1999 }. (,.~ <@>:@i.@#) ;({."#. <@(0&#`({.@{.(;,)<@}."1)@.(1<#))/. ])/:~~.,/(+,/:~@,)"0/~3^~1+i.10000 |
||
┌────┬──────────┬────────────────────┬────────────────────┬┐ |
┌────┬──────────┬────────────────────┬────────────────────┬┐ |
||
│2000│1671816384│78402752 1593413632 │830584000 841232384 ││ |
│2000│1671816384│78402752 1593413632 │830584000 841232384 ││ |
||
Line 1,944: | Line 1,944: | ||
├────┼──────────┼────────────────────┼────────────────────┼┤ |
├────┼──────────┼────────────────────┼────────────────────┼┤ |
||
│2006│1677646971│970299 1676676672 │707347971 970299000 ││ |
│2006│1677646971│970299 1676676672 │707347971 970299000 ││ |
||
└────┴──────────┴────────────────────┴────────────────────┴┘</ |
└────┴──────────┴────────────────────┴────────────────────┴┘</syntaxhighlight> |
||
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. |
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}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.util.PriorityQueue; |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.List; |
import java.util.List; |
||
Line 2,023: | Line 2,023: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,061: | Line 2,061: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">var n3s = [], |
||
s3s = {} |
s3s = {} |
||
for (var n = 1, e = 1200; n < e; n += 1) n3s[n] = n * n * n |
for (var n = 1, e = 1200; n < e; n += 1) n3s[n] = n * n * n |
||
Line 2,087: | Line 2,087: | ||
} |
} |
||
document.write('<br>') |
document.write('<br>') |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
1: 1729 = 1<sup>3</sup>+12<sup>3</sup> = 9<sup>3</sup>+10<sup>3</sup> |
1: 1729 = 1<sup>3</sup>+12<sup>3</sup> = 9<sup>3</sup>+10<sup>3</sup> |
||
Line 2,135: | Line 2,135: | ||
{{works with|jq|1.4}} |
{{works with|jq|1.4}} |
||
< |
<syntaxhighlight lang="jq"># Output: an array of the form [i^3 + j^3, [i, j]] sorted by the sum. |
||
# Only cubes of 1 to ($in-1) are considered; the listing is therefore truncated |
# 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. |
# as it might not capture taxicab numbers greater than $in ^ 3. |
||
Line 2,173: | Line 2,173: | ||
| [ ., [taxicabs0] ] |
| [ ., [taxicabs0] ] |
||
| until( .[1] | length >= $m; (.[0] + $increment) | [., [taxicabs0]] ) |
| until( .[1] | length >= $m; (.[0] + $increment) | [., [taxicabs0]] ) |
||
| .[1][0:$n] ;</ |
| .[1][0:$n] ;</syntaxhighlight> |
||
'''The task''' |
'''The task''' |
||
< |
<syntaxhighlight lang="jq">2006 | taxicabs as $t |
||
| (range(0;25), range(1999;2006)) as $i |
| (range(0;25), range(1999;2006)) as $i |
||
| "\($i+1): \($t[$i][0]) ~ \($t[$i][1]) and \($t[$i][2])"</ |
| "\($i+1): \($t[$i][0]) ~ \($t[$i][1]) and \($t[$i][2])"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -n -r -f Taxicab_numbers.jq |
||
1: 1729 ~ [1,12] and [9,10] |
1: 1729 ~ [1,12] and [9,10] |
||
2: 4104 ~ [2,16] and [9,15] |
2: 4104 ~ [2,16] and [9,15] |
||
Line 2,212: | Line 2,212: | ||
2004: 1675958167 ~ [492,1159] and [711,1096] |
2004: 1675958167 ~ [492,1159] and [711,1096] |
||
2005: 1676926719 ~ [63,1188] and [714,1095] |
2005: 1676926719 ~ [63,1188] and [714,1095] |
||
2006: 1677646971 ~ [99,1188] and [891,990]</ |
2006: 1677646971 ~ [99,1188] and [891,990]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">using Printf, DataStructures, IterTools |
||
function findtaxinumbers(nmax::Integer) |
function findtaxinumbers(nmax::Integer) |
||
Line 2,269: | Line 2,269: | ||
end |
end |
||
findtaxinumbers(1200)</ |
findtaxinumbers(1200)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,340: | Line 2,340: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
import java.util.PriorityQueue |
import java.util.PriorityQueue |
||
Line 2,400: | Line 2,400: | ||
println() |
println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,439: | Line 2,439: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">sums, taxis, limit = {}, {}, 1200 |
||
for i = 1, limit do |
for i = 1, limit do |
||
for j = 1, i-1 do |
for j = 1, i-1 do |
||
Line 2,456: | Line 2,456: | ||
end |
end |
||
end |
end |
||
print("* n=3")</ |
print("* n=3")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 : 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
<pre> 1 : 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
||
Line 2,503: | Line 2,503: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{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] |
Take[findTaxiNumbers[100], 25] |
||
found=findTaxiNumbers[1200][[2000 ;; 2005]] |
found=findTaxiNumbers[1200][[2000 ;; 2005]] |
||
Map[Reduce[x^3 + y^3 == # && x >= y && x > 0 && y > 0, {x, y}, Integers] &, found]</ |
Map[Reduce[x^3 + y^3 == # && x >= y && x > 0 && y > 0, {x, y}, Integers] &, found]</syntaxhighlight> |
||
{{out}} |
{{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} |
<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} |
||
Line 2,525: | Line 2,525: | ||
Execution time is excellent: about 45 ms on our laptop (I5). |
Execution time is excellent: about 45 ms on our laptop (I5). |
||
< |
<syntaxhighlight lang="nim">import heapqueue, strformat |
||
type |
type |
||
Line 2,569: | Line 2,569: | ||
for s in t: |
for s in t: |
||
stdout.write &" = {s.x:4}^3 + {s.y:4}^3" |
stdout.write &" = {s.x:4}^3 + {s.y:4}^3" |
||
echo()</ |
echo()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,606: | Line 2,606: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">taxicab(n)=my(t); for(k=sqrtnint((n-1)\2,3)+1, sqrtnint(n,3), if(ispower(n-k^3, 3), if(t, return(1), t=1))); 0; |
||
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"))) |
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]) |
select(taxicab, [1..402597]) |
||
apply(cubes, %);</ |
apply(cubes, %);</syntaxhighlight> |
||
{{out}} |
{{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] |
<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 2,673: | Line 2,673: | ||
Its impressive, that over all one check takes ~3.5 cpu-cycles on i4330 3.5Ghz |
Its impressive, that over all one check takes ~3.5 cpu-cycles on i4330 3.5Ghz |
||
< |
<syntaxhighlight lang="pascal">program taxiCabNo; |
||
uses |
uses |
||
sysutils; |
sysutils; |
||
Line 2,808: | Line 2,808: | ||
writeln('count of solutions ',AllSolHigh); |
writeln('count of solutions ',AllSolHigh); |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> 1 1729 = 12^3 + 1^3 = 10^3 + 9^3 |
<pre> 1 1729 = 12^3 + 1^3 = 10^3 + 9^3 |
||
2 4104 = 16^3 + 2^3 = 15^3 + 9^3 |
2 4104 = 16^3 + 2^3 = 15^3 + 9^3 |
||
Line 2,827: | Line 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. |
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. |
||
< |
<syntaxhighlight lang="perl">my($beg, $end) = (@ARGV==0) ? (1,25) : (@ARGV==1) ? (1,shift) : (shift,shift); |
||
my $lim = 1e14; # Ought to be dynamic as should segment size |
my $lim = 1e14; # Ought to be dynamic as should segment size |
||
Line 2,880: | Line 2,880: | ||
@retlist = sort { $a->[0] <=> $b->[0] } @retlist; |
@retlist = sort { $a->[0] <=> $b->[0] } @retlist; |
||
return @retlist; |
return @retlist; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,921: | Line 2,921: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Taxicab_numbers.exw</span> |
<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;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 2,965: | Line 2,965: | ||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">np1</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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,014: | Line 3,014: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(load "@lib/simul.l") |
||
(off 'B) |
(off 'B) |
||
Line 3,030: | Line 3,030: | ||
(println (car L) (caddr L)) ) |
(println (car L) (caddr L)) ) |
||
(for L (head 7 (nth R 2000)) |
(for L (head 7 (nth R 2000)) |
||
(println (car L) (caddr L)) )</ |
(println (car L) (caddr L)) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,069: | Line 3,069: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">#MAX=1189 |
||
Macro q3(a,b) |
Macro q3(a,b) |
||
Line 3,107: | Line 3,107: | ||
Next |
Next |
||
PrintN("FIN.") : Input() |
PrintN("FIN.") : Input() |
||
EndIf</ |
EndIf</syntaxhighlight>{{out}} |
||
<pre> 1: 1729= 1³ + 12³ = 9³ + 10³ |
<pre> 1: 1729= 1³ + 12³ = 9³ + 10³ |
||
2: 4104= 2³ + 16³ = 9³ + 15³ |
2: 4104= 2³ + 16³ = 9³ + 15³ |
||
Line 3,144: | Line 3,144: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
(Magic number 1201 found by trial and error) |
(Magic number 1201 found by trial and error) |
||
< |
<syntaxhighlight lang="python">from collections import defaultdict |
||
from itertools import product |
from itertools import product |
||
from pprint import pprint as pp |
from pprint import pprint as pp |
||
Line 3,160: | Line 3,160: | ||
print('...') |
print('...') |
||
for t in enumerate(taxied[2000-1:2000+6], 2000): |
for t in enumerate(taxied[2000-1:2000+6], 2000): |
||
pp(t)</ |
pp(t)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,198: | Line 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: |
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: |
||
< |
<syntaxhighlight lang="python">cubes, crev = [x**3 for x in range(1,1200)], {} |
||
# for cube root lookup |
# for cube root lookup |
||
for x,x3 in enumerate(cubes): crev[x3] = x + 1 |
for x,x3 in enumerate(cubes): crev[x3] = x + 1 |
||
Line 3,217: | Line 3,217: | ||
print "%4d: %10d"%(idx,n), |
print "%4d: %10d"%(idx,n), |
||
for x in p: print " = %4d^3 + %4d^3"%x, |
for x in p: print " = %4d^3 + %4d^3"%x, |
||
print</ |
print</syntaxhighlight> |
||
{{out}}Output trimmed to reduce clutter. |
{{out}}Output trimmed to reduce clutter. |
||
<pre> |
<pre> |
||
Line 3,233: | Line 3,233: | ||
===Using heapq module=== |
===Using heapq module=== |
||
A priority queue that holds cube sums. When consecutive sums come out with the same value, they are taxis. |
A priority queue that holds cube sums. When consecutive sums come out with the same value, they are taxis. |
||
< |
<syntaxhighlight lang="python">from heapq import heappush, heappop |
||
def cubesum(): |
def cubesum(): |
||
Line 3,262: | Line 3,262: | ||
if n >= 2006: break |
if n >= 2006: break |
||
if n <= 25 or n >= 2000: |
if n <= 25 or n >= 2000: |
||
print(n, x)</ |
print(n, x)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,301: | Line 3,301: | ||
This is the straighforward implementation, so it finds |
This is the straighforward implementation, so it finds |
||
only the first 25 values in a sensible amount of time. |
only the first 25 values in a sensible amount of time. |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define (cube x) (* x x x)) |
(define (cube x) (* x x x)) |
||
Line 3,327: | Line 3,327: | ||
(when (< p 25) |
(when (< p 25) |
||
(loop (add1 p) (add1 n)))) |
(loop (add1 p) (add1 n)))) |
||
(loop p (add1 n)))))</ |
(loop p (add1 n)))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1: 1729 = 1^3 + 12^3 = 9^3 + 10^3 |
<pre>1: 1729 = 1^3 + 12^3 = 9^3 + 10^3 |
||
Line 3,359: | Line 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. |
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. |
||
<lang |
<syntaxhighlight lang="raku" line>constant @cu = (^Inf).map: { .³ } |
||
sub MAIN ($start = 1, $end = 25) { |
sub MAIN ($start = 1, $end = 25) { |
||
Line 3,389: | Line 3,389: | ||
(.value.map({ sprintf "%4d³ + %-s\³", |$_ })).join: ",\t" |
(.value.map({ sprintf "%4d³ + %-s\³", |$_ })).join: ",\t" |
||
for %this_stuff.grep( { $_.value.elems > 1 } ).sort( +*.key )[$start-1..$end-1]; |
for %this_stuff.grep( { $_.value.elems > 1 } ).sort( +*.key )[$start-1..$end-1]; |
||
}</ |
}</syntaxhighlight> |
||
{{out}}With no passed parameters (default): |
{{out}}With no passed parameters (default): |
||
<pre> 1 1729 => 9³ + 10³, 1³ + 12³ |
<pre> 1 1729 => 9³ + 10³, 1³ + 12³ |
||
Line 3,427: | Line 3,427: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Programming note: to ensure that the taxicab numbers are in order, an extra 10% are generated. |
Programming note: to ensure that the taxicab numbers are in order, an extra 10% are generated. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program displays the specified first (lowest) taxicab numbers (for three ranges).*/ |
||
parse arg L.1 H.1 L.2 H.2 L.3 H.3 . /*obtain optional arguments from the CL*/ |
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. */ |
if L.1=='' | L.1=="," then L.1= 1 /*L1 is the low part of 1st range. */ |
||
Line 3,474: | Line 3,474: | ||
end /*forever*/ |
end /*forever*/ |
||
end /*i*/ |
end /*i*/ |
||
end /*while h>1*/; return</ |
end /*while h>1*/; return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 3,517: | Line 3,517: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Taxicab numbers |
# Project : Taxicab numbers |
||
Line 3,543: | Line 3,543: | ||
next |
next |
||
see "ok" + nl |
see "ok" + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 3,575: | Line 3,575: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def taxicab_number(nmax=1200) |
||
[*1..nmax].repeated_combination(2).group_by{|x,y| x**3 + y**3}.select{|k,v| v.size>1}.sort |
[*1..nmax].repeated_combination(2).group_by{|x,y| x**3 + y**3}.select{|k,v| v.size>1}.sort |
||
end |
end |
||
Line 3,583: | Line 3,583: | ||
[*1..25, *2000...2007].each do |i| |
[*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 |
puts "%4d: %10d" % [i, t[i][0]] + t[i][1].map{|a| " = %4d**3 + %4d**3" % a}.join |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,621: | Line 3,621: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
use std::collections::HashMap; |
use std::collections::HashMap; |
||
use itertools::Itertools; |
use itertools::Itertools; |
||
Line 3,655: | Line 3,655: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,683: | Line 3,683: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">import scala.collection.MapView |
||
import scala.math.pow |
import scala.math.pow |
||
Line 3,714: | Line 3,714: | ||
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) ) |
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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,756: | Line 3,756: | ||
{{libheader|Scheme/SRFIs}} |
{{libheader|Scheme/SRFIs}} |
||
< |
<syntaxhighlight lang="scheme"> |
||
(import (scheme base) |
(import (scheme base) |
||
(scheme write) |
(scheme write) |
||
Line 3,792: | Line 3,792: | ||
(iota 7 1999)) |
(iota 7 1999)) |
||
) |
) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,832: | Line 3,832: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">var (start=1, end=25) = ARGV.map{.to_i}... |
||
func display (h, start, end) { |
func display (h, start, end) { |
||
Line 3,860: | Line 3,860: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,903: | Line 3,903: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">extension Array { |
||
func combinations(_ k: Int) -> [[Element]] { |
func combinations(_ k: Int) -> [[Element]] { |
||
return Self._combinations(slice: self[startIndex...], k) |
return Self._combinations(slice: self[startIndex...], k) |
||
Line 3,950: | Line 3,950: | ||
for taxi in res[1999..<2006] { |
for taxi in res[1999..<2006] { |
||
print(taxi) |
print(taxi) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,993: | Line 3,993: | ||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
proc heappush {heapName item} { |
proc heappush {heapName item} { |
||
Line 4,045: | Line 4,045: | ||
for {set n 2000} {$n <= 2006} {incr n} { |
for {set n 2000} {$n <= 2006} {incr n} { |
||
puts ${n}:[join [lmap t [taxi $n] {format " %d = %d$3 + %d$3" {*}$t}] ","] |
puts ${n}:[join [lmap t [taxi $n] {format " %d = %d$3 + %d$3" {*}$t}] ","] |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,083: | Line 4,083: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">Public Type tuple |
||
i As Variant |
i As Variant |
||
j As Variant |
j As Variant |
||
Line 4,216: | Line 4,216: | ||
If (arrLbound < tmpHi) Then Quicksort vArray, arrLbound, tmpHi 'conquer |
If (arrLbound < tmpHi) Then Quicksort vArray, arrLbound, tmpHi 'conquer |
||
If (tmpLow < arrUbound) Then Quicksort vArray, tmpLow, arrUbound 'conquer |
If (tmpLow < arrUbound) Then Quicksort vArray, tmpLow, arrUbound 'conquer |
||
End Sub</ |
End Sub</syntaxhighlight>{{out}} |
||
<pre> 4399 taxis |
<pre> 4399 taxis |
||
1 1729 = 9^3 + 10^3 = 1^3 + 12^3 |
1 1729 = 9^3 + 10^3 = 1^3 + 12^3 |
||
Line 4,280: | Line 4,280: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet"> |
||
Imports System.Text |
Imports System.Text |
||
Line 4,338: | Line 4,338: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
<pre> 1 1729 = 10^3 + 9^3 = 12^3 + 1^3 |
||
Line 4,376: | Line 4,376: | ||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/sort" for Sort |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 4,409: | Line 4,409: | ||
var t = taxicabs[i-1] |
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]]) |
Fmt.lprint("$,5d: $,13d = $3d³ + $,5d³ = $3d³ + $,5d³", [i, t[0], t[1][0], t[1][1], t[2][0], t[2][1]]) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,452: | Line 4,452: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Slow, brute force solution. |
Slow, brute force solution. |
||
< |
<syntaxhighlight lang="xpl0">int N, I, J, SI, SJ, Count, Tally; |
||
[Count:= 0; N:= 0; |
[Count:= 0; N:= 0; |
||
repeat Tally:= 0; |
repeat Tally:= 0; |
||
Line 4,478: | Line 4,478: | ||
N:= N+1; |
N:= N+1; |
||
until Count >= 25; |
until Count >= 25; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,512: | Line 4,512: | ||
{{trans|D}} |
{{trans|D}} |
||
An array of bytes is used to hold n, where array[n³+m³]==n. |
An array of bytes is used to hold n, where array[n³+m³]==n. |
||
< |
<syntaxhighlight lang="zkl">fcn taxiCabNumbers{ |
||
const HeapSZ=0d5_000_000; |
const HeapSZ=0d5_000_000; |
||
iCubes:=[1..120].apply("pow",3); |
iCubes:=[1..120].apply("pow",3); |
||
Line 4,529: | Line 4,529: | ||
} |
} |
||
taxiNums.sort(fcn([(a,_)],[(b,_)]){ a<b }) |
taxiNums.sort(fcn([(a,_)],[(b,_)]){ a<b }) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">fcn print(n,taxiNums){ |
||
[n..].zip(taxiNums).pump(Console.println,fcn([(n,t)]){ |
[n..].zip(taxiNums).pump(Console.println,fcn([(n,t)]){ |
||
"%4d: %10,d = %2d\u00b3 + %2d\u00b3 = %2d\u00b3 + %2d\u00b3".fmt(n,t.xplode()) |
"%4d: %10,d = %2d\u00b3 + %2d\u00b3 = %2d\u00b3 + %2d\u00b3".fmt(n,t.xplode()) |
||
Line 4,536: | Line 4,536: | ||
} |
} |
||
taxiNums:=taxiCabNumbers(); // 63 pairs |
taxiNums:=taxiCabNumbers(); // 63 pairs |
||
taxiNums[0,25]:print(1,_);</ |
taxiNums[0,25]:print(1,_);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,567: | Line 4,567: | ||
{{trans|Python}} |
{{trans|Python}} |
||
Using a binary heap: |
Using a binary heap: |
||
< |
<syntaxhighlight lang="zkl">fcn cubeSum{ |
||
heap,n:=Heap(fcn([(a,_)],[(b,_)]){ a<=b }), 1; // heap cnt maxes out @ 244 |
heap,n:=Heap(fcn([(a,_)],[(b,_)]){ a<=b }), 1; // heap cnt maxes out @ 244 |
||
while(1){ |
while(1){ |
||
Line 4,596: | Line 4,596: | ||
if(n >= 2006) break; |
if(n >= 2006) break; |
||
if(n <= 25 or n >= 2000) println(n,": ",x); |
if(n <= 25 or n >= 2000) println(n,": ",x); |
||
}</ |
}</syntaxhighlight> |
||
And a quickie heap implementation: |
And a quickie heap implementation: |
||
< |
<syntaxhighlight lang="zkl">class Heap{ // binary heap |
||
fcn init(lteqFcn='<=){ |
fcn init(lteqFcn='<=){ |
||
var [const, private] heap=List().pad(64,Void); // a power of 2 |
var [const, private] heap=List().pad(64,Void); // a power of 2 |
||
Line 4,635: | Line 4,635: | ||
var [proxy] top=fcn { if(cnt==0) Void else heap[0] }; |
var [proxy] top=fcn { if(cnt==0) Void else heap[0] }; |
||
var [proxy] empty=fcn{ (not cnt) }; |
var [proxy] empty=fcn{ (not cnt) }; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,656: | Line 4,656: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="zxbasic">10 DIM f(1625): REM populating a cube table at the start will be faster than computing the cubes on the fly |
||
20 FOR x=1 TO 1625 |
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 |
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 4,691: | Line 4,691: | ||
340 NEXT n |
340 NEXT n |
||
350 NEXT m |
350 NEXT m |
||
360 NEXT x</ |
360 NEXT x</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,709: | Line 4,709: | ||
This program produces the first 25 Taxicab numbers. It is written with speed in mind. |
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). |
The runtime is about 45 minutes on a ZX Spectrum (3.5 Mhz). |
||
< |
<syntaxhighlight lang="zxbasic"> 10 LET T=0: DIM F(72): LET D=0: LET S=0: LET B=0: LET A=0: LET C=0 |
||
20 DIM H(50): DIM Y(50,2): FOR D=1 TO 72: LET F(D)=D*D*D: NEXT D |
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 |
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 4,729: | Line 4,729: | ||
151 LPRINT T;"^3+";Y(A,2)-T*65536;"^3" |
151 LPRINT T;"^3+";Y(A,2)-T*65536;"^3" |
||
160 NEXT A: PRINT |
160 NEXT A: PRINT |
||
170 STOP</ |
170 STOP</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1:1729=1^3+12^3=9^3+10^3 |
<pre>1:1729=1^3+12^3=9^3+10^3 |