Taxicab numbers: Difference between revisions

{{task|Mathematics}}

 

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.

 

The first taxicab number is   '''1729''',   which is:

::: 9³   +   10³.

 

 

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

 

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

2006:1677646971 = 990^3 + 891^3 = 1188^3 + 99^3

</pre>

 

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

using System.Collections.Generic;

using System.Linq;

}

}

 

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

2005: 1676926719 = 1095^3 + 714^3 = 1188^3 + 63^3

2006: 1677646971 = 990^3 + 891^3 = 1188^3 + 99^3</pre>

 

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

2006 : {1677646971, [{891, 990}, {99, 1188}]}

</pre>

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

 

 

taxis :: Int -> [[(Int, ((Int, Int), (Int, Int)))]]

taxis nCubes =

filter ((> 1) . length) $

[ (fst x + fst y, (x, y))

| (x:t) <- tails $ ((^ 3) >>= (,)) <$> [1 .. nCubes]

, y <- t ]

 

 

taxiRow :: (Int, [(Int, ((Int, Int), (Int, Int)))]) -> [String]

taxiRow (n, [(a, ((axc, axr), (ayc, ayr))), (b, ((bxc, bxr), (byc, byr)))]) =

]

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>

2006: 1677646971 = 990^3 + 891^3 = 1188^3 + 99^3

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

2006: 1677646971 = 990^3 + 891^3 = 1188^3 + 99^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])

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

402597 = 61^3 + 56^3

402597 = 69^3 + 42^3</pre>

=={{header|Pascal}}==

{{works with |Free Pascal}}

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>

2006: 1677646971 = 99^3 + 1188^3 = 891^3 + 990^3

</pre>

 

=={{header|Phix}}==

{{out}}

<pre>

</pre>

 

=={{header|PicoLisp}}==

 

(off 'B)

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

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

 

{{out}}

1677646971 ((891 990) (99 1188))

</pre>

 

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

24: 373464 = 6^3 + 72^3 = 54^3 + 60^3

25: 402597 = 42^3 + 69^3 = 56^3 + 61^3</pre>

 

=={{header|REXX}}==

Programming note: &nbsp; to ensure that the taxicab numbers are in order, an extra 10% are generated.

if L.1=='' | L.1=="," then L.1= 1 /*L1 is the low part of 1st range. */

if H.1=='' | H.1=="," then H.1= 25 /*H1 " " high " " " " */

if L.3=='' | L.3=="," then L.3=2000 /*L3 " " low " " 3rd " */

if H.3=='' | H.3=="," then H.3=2006 /*H3 " " high " " " " */

numeric digits max(9, ww) /*prepare to use some larger numbers. */

$.= /* [↓] generate extra taxicab numbers.*/

A.=

call Esort mx /*sort taxicab #s with an exchange sort*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

U: return right(arg(1), w)'^3'arg(2) /*right─justify a number, append "^3" */

/*──────────────────────────────────────────────────────────────────────────────────────*/

do forever; parse var A.k xk .; parse var A.j xj .; if xk>=xj then leave

end /*forever*/

end /*i*/

<pre>

1: 1729 ───► 10^3 + 9^3 ──and── 12^3 + 1^3

 

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

2005: 1676926719 = 63**3 + 1188**3 = 714**3 + 1095**3

2006: 1677646971 = 99**3 + 1188**3 = 891**3 + 990**3

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

 

func display (h, start, end) {

}

}

{{out}}

<pre>

2006 1677646971 => 891³ + 990³, 99³ + 1188³

</pre>

 

=={{header|Tcl}}==

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

2005: 1676926719 = 1095³ + 714³, 1676926719 = 1188³ + 63³

2006: 1677646971 = 990³ + 891³, 1677646971 = 1188³ + 99³

</pre>

 

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