Taxicab numbers: Difference between revisions

{{trans|Python}}

 

[Int64 = Int64] crev

L(x3) cubes

L(x1, x2) p

print(‘ = #4^3 + #4^3’.format(x1, x2), end' ‘ ’)

 

{{out}}

 

=={{header|AWK}}==

# syntax: GAWK -f TAXICAB_NUMBERS.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

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<^

 

{{out}}

=={{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>

 

}

return 0;

{{out}}

<pre>

=={{header|C++}}==

{{trans|C#}}

#include <iomanip>

#include <iostream>

 

return 0;

{{out}}

<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:

 

=={{header|C sharp}}==

using System.Collections.Generic;

using System.Linq;

}

}

 

===Alternate Algorithm===

Based on the second Python example where only the sums are stored and sorted. Also shows the first 10 Taxicab Number triples.

using System.Collections.Generic; using System.Linq;

 

dump(string.Format("\n\nFound {0} triple Taxicabs under {1}:", trips.Count, 2007), trips);

Write("\n\nElasped: {0}ms", (DateTime.Now - st).TotalMilliseconds); }

{{out}} (from TIO.run)

<pre>First 25 Taxicab Numbers, the 2000th, plus the next half-dozen:

 

=={{header|Clojure}}==

(:gen-class))

 

(show-result n sample))

 

 

{{out}}

===High Level Version===

{{trans|Python}}

import std.stdio, std.range, std.algorithm, std.typecons, std.string;

 

writeln;

}

{{out}}

<pre> 1: 1729 = 1^3 + 12^3 = 9^3 + 10^3

===Heap-Based Version===

{{trans|Java}}

 

struct CubeSum {

writeln;

}

{{out}}

<pre> 1: 1729 = 10^3 + 9^3 = 12^3 + 1^3

===Low Level Heap-Based Version===

{{trans|C}}

alias CubesSumT = uint; // Or ulong.

 

'\n'.putchar;

}

{{out}}

<pre> 1: 1729 = 12^3 + 1^3 = 10^3 + 9^3

=={{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

$ clean:

$ close /nolog sorted_sums_of_cubes

{{out}}

<pre>$ @taxicab_numbers

=={{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))

 

(for ((i (in-naturals nfrom)) (taxi (sublist taxis nfrom nto)))

(writeln (taxi->string i (first taxi)))))

 

{{out}}

(define S (stack 'S)) ;; to push taxis

(define H (make-heap < )) ;; make min heap of all scubes

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

 

=={{header|Elixir}}==

def numbers(n \\ 1200) do

(for i <- 1..n, j <- i..n, do: {i,j})

IO.puts "#{i+1} : #{inspect x}"

end

 

{{out}}

{{works with|gforth|0.7.3}}

 

variable searched-cubessum

73 constant max-constituent \ uses magic numbers

 

build-taxicablist

 

{{out}}

 

=={{header|Fortran}}==

! A non-bruteforce approach

PROGRAM POOKA

END FUNCTION TAXICAB

{{out}}

<pre> Print first 25 numbers

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> Print first 25 numbers

 

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

=={{header|Haskell}}==

 

import Data.Function (on)

 

]

where

{{Out}}

<pre> 1. 1729 = ( 1^3= 1) + ( 12^3= 1728) or ( 9^3= 729) + ( 10^3= 1000)

=={{header|J}}==

 

triples=: /:~ ~. ,/ (+ , /:~@,)"0/~cubes NB. ordered pairs of cubes (each with their sum)

candidates=: ;({."#. <@(0&#`({.@{.(;,)<@}."1)@.(1<#))/. ])triples

├──┼──────┼────────────┼─────────────┤

│25│402597│74088 328509│175616 226981│

 

Explanation:

Extra credit:

 

┌────┬──────────┬────────────────────┬────────────────────┬┐

│2000│1671816384│78402752 1593413632 │830584000 841232384 ││

├────┼──────────┼────────────────────┼────────────────────┼┤

│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;

}

}

{{out}}

<pre>

 

=={{header|JavaScript}}==

s3s = {}

for (var n = 1, e = 1200; n < e; n += 1) n3s[n] = n * n * n

}

document.write('<br>')

{{out}}

1: 1729 = 1³+12³ = 9³+10³

{{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.

| [ ., [taxicabs0] ]

| until( .[1] | length >= $m; (.[0] + $increment) | [., [taxicabs0]] )

 

'''The task'''

| (range(0;25), range(1999;2006)) as $i

{{out}}

1: 1729 ~ [1,12] and [9,10]

2: 4104 ~ [2,16] and [9,15]

2004: 1675958167 ~ [492,1159] and [711,1096]

2005: 1676926719 ~ [63,1188] and [714,1095]

 

=={{header|Julia}}==

{{trans|Python}}

 

function findtaxinumbers(nmax::Integer)

end

 

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.PriorityQueue

println()

}

 

{{out}}

 

=={{header|Lua}}==

for i = 1, limit do

for j = 1, i-1 do

end

end

{{out}}

<pre> 1 : 1729 = 10^3 + 9^3 = 12^3 + 1^3

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Take[findTaxiNumbers[100], 25]

found=findTaxiNumbers[1200][[2000 ;; 2005]]

{{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}

Execution time is excellent: about 45 ms on our laptop (I5).

 

 

type

for s in t:

stdout.write &" = {s.x:4}^3 + {s.y:4}^3"

 

{{out}}

 

=={{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])

{{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]

Its impressive, that over all one check takes ~3.5 cpu-cycles on i4330 3.5Ghz

 

uses

sysutils;

writeln('count of solutions ',AllSolHigh);

end.

<pre> 1 1729 = 12^3 + 1^3 = 10^3 + 9^3

2 4104 = 16^3 + 2^3 = 15^3 + 9^3

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

@retlist = sort { $a->[0] <=> $b->[0] } @retlist;

return @retlist;

{{out}}

<pre>

 

=={{header|Phix}}==

{{out}}

<pre>

</pre>

 

=={{header|PicoLisp}}==

 

(off 'B)

(println (car L) (caddr L)) )

(for L (head 7 (nth R 2000))

 

{{out}}

 

=={{header|PureBasic}}==

 

Macro q3(a,b)

Next

PrintN("FIN.") : Input()

<pre> 1: 1729= 1³ + 12³ = 9³ + 10³

2: 4104= 2³ + 16³ = 9³ + 15³

=={{header|Python}}==

(Magic number 1201 found by trial and error)

from itertools import product

from pprint import pprint as pp

print('...')

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

 

{{out}}

 

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

print "%4d: %10d"%(idx,n),

for x in p: print " = %4d^3 + %4d^3"%x,

{{out}}Output trimmed to reduce clutter.

<pre>

===Using heapq module===

A priority queue that holds cube sums. When consecutive sums come out with the same value, they are taxis.

 

def cubesum():

if n >= 2006: break

if n <= 25 or n >= 2000:

{{out}}

<pre>

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))

(when (< p 25)

(loop (add1 p) (add1 n))))

{{out}}

<pre>1: 1729 = 1^3 + 12^3 = 9^3 + 10^3

 

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.

 

sub MAIN ($start = 1, $end = 25) {

(.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³

=={{header|REXX}}==

Programming note: &nbsp; 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. */

end /*forever*/

end /*i*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Taxicab numbers

 

next

see "ok" + nl

Output:

<pre>

25 402597 => 56³ + 61³, 42³ + 69³

ok

</pre>

 

=={{header|Ruby}}==

[*1..nmax].repeated_combination(2).group_by{|x,y| x**3 + y**3}.select{|k,v| v.size>1}.sort

end

[*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

{{out}}

<pre>

 

=={{header|Rust}}==

use std::collections::HashMap;

use itertools::Itertools;

}

}

{{out}}

<pre>

 

=={{header|Scala}}==

 

implicit class Pairs[A, B]( p:List[(A, B)]) {

}

 

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

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) )

}

{{out}}

<pre>

{{libheader|Scheme/SRFIs}}

 

(import (scheme base)

(scheme write)

(iota 7 1999))

)

 

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

 

func display (h, start, end) {

}

}

{{out}}

<pre>

=={{header|Swift}}==

 

func combinations(_ k: Int) -> [[Element]] {

return Self._combinations(slice: self[startIndex...], k)

for taxi in res[1999..<2006] {

print(taxi)

 

{{out}}

{{works with|Tcl|8.6}}

{{trans|Python}}

 

proc heappush {heapName item} {

for {set n 2000} {$n <= 2006} {incr n} {

puts ${n}:[join [lmap t [taxi $n] {format " %d = %d$3 + %d$3" {*}$t}] ","]

{{out}}

<pre>

 

=={{header|VBA}}==

i As Variant

j As Variant

If (arrLbound < tmpHi) Then Quicksort vArray, arrLbound, tmpHi 'conquer

If (tmpLow < arrUbound) Then Quicksort vArray, tmpLow, arrUbound 'conquer

<pre> 4399 taxis

1 1729 = 9^3 + 10^3 = 1^3 + 12^3

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Imports System.Text

 

End Sub

 

{{out}}

<pre> 1 1729 = 10^3 + 9^3 = 12^3 + 1^3

{{libheader|Wren-sort}}

{{libheader|Wren-fmt}}

 

var cubesSum = {}

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}}

=={{header|XPL0}}==

Slow, brute force solution.

[Count:= 0; N:= 0;

repeat Tally:= 0;

N:= N+1;

until Count >= 25;

 

{{out}}

{{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);

}

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())

}

taxiNums:=taxiCabNumbers(); // 63 pairs

{{out}}

<pre>

{{trans|Python}}

Using a binary heap:

heap,n:=Heap(fcn([(a,_)],[(b,_)]){ a<=b }), 1; // heap cnt maxes out @ 244

while(1){

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

var [proxy] top=fcn { if(cnt==0) Void else heap[0] };

var [proxy] empty=fcn{ (not cnt) };

{{out}}

<pre>

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

340 NEXT n

350 NEXT m

 

{{out}}

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

151 LPRINT T;"^3+";Y(A,2)-T*65536;"^3"

160 NEXT A: PRINT

{{out}}

<pre>1:1729=1^3+12^3=9^3+10^3