Taxicab numbers: Difference between revisions

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

<lang scheme>

(require '(heap compile))

(define (scube a b) (+ (* a a a) (* b b b)))

(compile 'scube "-f") ; "-f" means : no bigint, no rational used

;; is n - a^3 a cube b^3?

;; if yes return b, else #f

(define (taxi? n a (b 0))

(set! b (cbrt (- n (* a a a)))) ;; cbrt is ∛

(when (and (< b a) (integer? b)) b))

(compile 'taxi? "-f")

#|-------------------

looking for taxis

--------------------|#

;; remove from heap until heap-top >= a

;; when twins are removed, it is a taxicab number : push it

;; at any time (top stack) = last removed

(define (clean-taxi H limit: a min-of-heap: htop)

(when (and htop (> a htop))

(when (!= (stack-top S) htop) (pop S))

(push S htop)

(heap-pop H)

(clean-taxi H a (heap-top H))))

(compile 'clean-taxi "-f")

;; loop on a and b, b <=a , until n taxicabs found

(define (taxicab (n 2100))

(for ((a (in-naturals)))

(clean-taxi H (* a a a) (heap-top H))

#:break (> (stack-length S) n)

(for ((b a))

(heap-push H (scube a b)))))

#|------------------

printing taxis

---------------------|#

;; string of all decompositions

(define (taxi->string i n)

(string-append (format "%d. %d " (1+ i) n)

(for/string ((a (cbrt n)))

#:when (taxi? n a)

(format " = %4d^3 + %4d^3" a (taxi? n a)))))

(define (taxi-print taxis (nfrom 0) (nto 26))

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

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

</lang>

{{out}}

<lang scheme>

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

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

(taxicab 2100)

(define taxis (group (stack->list S)))

(taxi-print taxis )

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

#| ... |#

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

25. 402597 = 61^3 + 56^3 = 69^3 + 42^3

26. 439101 = 69^3 + 48^3 = 76^3 + 5^3

(taxi-print taxis 1999 2006)

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

;; extra bonus : print all taxis which are triplets

(define (taxi-tuples taxis (nfrom 0) (nto 2000))

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

#:when (> (length taxi) 1) ;; filter for tuples is here

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

(taxi-tuples taxis)

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

</lang>