How to resolve the algorithm Taxicab numbers step by step in the EchoLisp programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Taxicab numbers step by step in the EchoLisp programming language
Table of Contents
Problem Statement
A 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:
Taxicab numbers are also known as:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Taxicab numbers step by step in the EchoLisp programming language
Source code in the echolisp programming language
(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)))))
(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
You may also check:How to resolve the algorithm Arithmetic/Complex step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Ethiopian multiplication step by step in the PL/SQL programming language
You may also check:How to resolve the algorithm Order two numerical lists step by step in the F# programming language
You may also check:How to resolve the algorithm Horner's rule for polynomial evaluation step by step in the ERRE programming language
You may also check:How to resolve the algorithm Cartesian product of two or more lists step by step in the Swift programming language