Posted on by Kalkicode
Code Number

Taxicab Numbers

Taxicab numbers are a special type of numbers that can be expressed as the sum of two cubes in two different ways. They are named after an incident involving the British mathematician G.H. Hardy. Hardy visited the Indian mathematician Srinivasa Ramanujan while he was in a hospital. Hardy mentioned that he traveled to see him in a taxi with the number 1729, which he thought was a rather dull number. However, Ramanujan quickly corrected him, stating that it was, in fact, a very interesting number as it is the smallest number that can be expressed as the sum of two cubes in two distinct ways: 1³ + 12³ and 9³ + 10³.

Problem Statement

The problem is to find the nth taxicab number, where n is a given integer. A taxicab number is a number that can be expressed as the sum of two cubes in two different ways. In other words, we need to find a number that can be written as a³ + b³ = c³ + d³, where a, b, c, and d are positive integers.

Example

Let's consider the case where we need to find the 6th taxicab number. The expected output for this case is: 1729, 4104, 13832, 20683, 32832, 39312. These numbers are the first six taxicab numbers.

Algorithm

The algorithm to find the nth taxicab number can be explained as follows:

  1. Initialize variables: result = 0, num = 1, and count = 0.
  2. While result is less than n, do the following:
    • Iterate over values of a from 1 to the cube root of num.
    • Within the first loop, iterate over values of b from a+1 to the cube root of num.
    • If a³ + b³ is equal to num, increment the count variable.
  3. If the count is equal to 2, it means we have found a taxicab number:
    • Print the taxicab number (num).
    • Increment the result variable.
  4. Increment the num variable.
  5. Reset the count variable to 0.
  6. Repeat the above steps until we find the nth taxicab number.

Pseudocode


function findNTaxicabNo(n):
	result = 0
	num = 1
	count = 0

	while result < n:
		for a from 1 to the cube root of num:
			for b from a + 1 to the cube root of num:
				if (a³ + b³) equals num:
					count++

		if count equals 2:
			print num
			result++

		num++
		count = 0


Code Solution

Here given code implementation process.

/*
    Java program for
    Taxicab Numbers
*/
public class TaxicabNumber
{
	public void findNTaxicabNo(int n)
	{
		// Auxiliary variables
		int result = 0;
		int num = 1;
		int count = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			for (int a = 1; 
                     a <= Math.pow(num, 0.3333333333); ++a)
			{
				for (int b = a + 1; 
                     b <= Math.pow(num, 0.3333333333); ++b)
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count++;
					}
				}
			}
			if (count == 2)
			{
				// Display Taxicab number
				System.out.println(num);
				// Increase result count
				result++;
			}
			// Increase number count
			num++;
			// Reset count
			count = 0;
		}
	}
	public static void main(String[] args)
	{
		TaxicabNumber task = new TaxicabNumber();
		// Test
		task.findNTaxicabNo(6);
	}
}

Output

1729
4104
13832
20683
32832
39312
// Include header file
#include <iostream>
#include <math.h>

using namespace std;
/*
    C++ program for
    Taxicab Numbers
*/
class TaxicabNumber
{
	public: void findNTaxicabNo(int n)
	{
		// Auxiliary variables
		int result = 0;
		int num = 1;
		int count = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			for (int a = 1; a <= pow(num, 0.3333333333); ++a)
			{
				for (int b = a + 1; b <= pow(num, 0.3333333333); ++b)
				{
					if ((a *a *a) + (b *b *b) == num)
					{
						// When a³ + b³ = num
						count++;
					}
				}
			}
			if (count == 2)
			{
				// Display Taxicab number
				cout << num << endl;
				// Increase result count
				result++;
			}
			// Increase number count
			num++;
			// Reset count
			count = 0;
		}
	}
};
int main()
{
	TaxicabNumber *task = new TaxicabNumber();
	// Test
	task->findNTaxicabNo(6);
	return 0;
}

Output

1729
4104
13832
20683
32832
39312
// Include namespace system
using System;
/*
    Csharp program for
    Taxicab Numbers
*/
public class TaxicabNumber
{
	public void findNTaxicabNo(int n)
	{
		// Auxiliary variables
		int result = 0;
		int num = 1;
		int count = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			for (int a = 1; a <= 
                 Math.Pow(num, 0.3333333333); ++a)
			{
				for (int b = a + 1; b <= 
                     Math.Pow(num, 0.3333333333); ++b)
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count++;
					}
				}
			}
			if (count == 2)
			{
				// Display Taxicab number
				Console.WriteLine(num);
				// Increase result count
				result++;
			}
			// Increase number count
			num++;
			// Reset count
			count = 0;
		}
	}
	public static void Main(String[] args)
	{
		TaxicabNumber task = new TaxicabNumber();
		// Test
		task.findNTaxicabNo(6);
	}
}

Output

1729
4104
13832
20683
32832
39312
package main
import "math"
import "fmt"
/*
    Go program for
    Taxicab Numbers
*/

func findNTaxicabNo(n int) {
	// Auxiliary variables
	var result int = 0
	var num int = 1
	var count int = 0
	// This loop are executed until result count are not have to n.
	for (result < n) {
		for a := 1 ; float64(a) <= math.Pow(float64(num), 0.3333333333) ; a++ {
			for b := a + 1 ; float64(b) <= math.Pow(float64(num), 0.3333333333) ; b++ {
				if (a * a * a) + (b * b * b) == num {
					// When a³ + b³ = num
					count++
				}
			}
		}
		if count == 2 {
			// Display Taxicab number
			fmt.Println(num)
			// Increase result count
			result++
		}
		// Increase number count
		num++
		// Reset count
		count = 0
	}
}
func main() {

	// Test
	findNTaxicabNo(6)
}

Output

1729
4104
13832
20683
32832
39312
<?php
/*
    Php program for
    Taxicab Numbers
*/
class TaxicabNumber
{
	public	function findNTaxicabNo($n)
	{
		// Auxiliary variables
		$result = 0;
		$num = 1;
		$count = 0;
		// This loop are executed until result count are not have to n.
		while ($result < $n)
		{
			for ($a = 1; 
                 $a <= pow($num, 0.3333333333); ++$a)
			{
				for ($b = $a + 1; 
                     $b <= pow($num, 0.3333333333); ++$b)
				{
					if (($a * $a * $a) + ($b * $b * $b) == $num)
					{
						// When a³ + b³ = num
						$count++;
					}
				}
			}
			if ($count == 2)
			{
				// Display Taxicab number
				echo($num.
					"\n");
				// Increase result count
				$result++;
			}
			// Increase number count
			$num++;
			// Reset count
			$count = 0;
		}
	}
}

function main()
{
	$task = new TaxicabNumber();
	// Test
	$task->findNTaxicabNo(6);
}
main();

Output

1729
4104
13832
20683
32832
39312
/*
    Node JS program for
    Taxicab Numbers
*/
class TaxicabNumber
{
	findNTaxicabNo(n)
	{
		// Auxiliary variables
		var result = 0;
		var num = 1;
		var count = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			for (var a = 1; 
                 a <= Math.pow(num, 0.3333333333); ++a)
			{
				for (var b = a + 1; 
                     b <= Math.pow(num, 0.3333333333); ++b)
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count++;
					}
				}
			}
			if (count == 2)
			{
				// Display Taxicab number
				console.log(num);
				// Increase result count
				result++;
			}
			// Increase number count
			num++;
			// Reset count
			count = 0;
		}
	}
}

function main()
{
	var task = new TaxicabNumber();
	// Test
	task.findNTaxicabNo(6);
}
main();

Output

1729
4104
13832
20683
32832
39312
import math
#    Python 3 program for
#    Taxicab Numbers
class TaxicabNumber :
    def findNTaxicabNo(self, n) :
        #  Auxiliary variables
        result = 0
        num = 1
        count = 0
        #  This loop are executed until result count are not have to n.
        while (result < n) :
            a = 1
            while (a <= (num ** (1/3))) :
                b = a + 1
                while (b <= (num ** (1/3))) :
                    if ((a * a * a) + (b * b * b) == num) :
                        #  When a³ + b³ = num
                        count += 1
                    
                    b += 1
                
                a += 1
            
            if (count == 2) :
                #  Display Taxicab number
                print(num)
                #  Increase result count
                result += 1
            
            #  Increase number count
            num += 1
            #  Reset count
            count = 0
        
    

def main() :
    task = TaxicabNumber()
    #  Test
    task.findNTaxicabNo(6)

if __name__ == "__main__": main()

Output

1729
4104
13832
20683
32832
39312
#    Ruby program for
#    Taxicab Numbers
class TaxicabNumber 
	def findNTaxicabNo(n) 
		#  Auxiliary variables
		result = 0
		num = 1
		count = 0
		#  This loop are executed until result count are not have to n.
		while (result < n) 
			a = 1
			while (a <= num ** (1/3.0)) 
				b = a + 1
				while (b <= num ** (1/3.0)) 
					if ((a * a * a) + (b * b * b) == num) 
						#  When a³ + b³ = num
						count += 1
					end

					b += 1
				end

				a += 1
			end

			if (count == 2) 
				#  Display Taxicab number
				print(num, "\n")
				#  Increase result count
				result += 1
			end

			#  Increase number count
			num += 1
			#  Reset count
			count = 0
		end

	end

end

def main() 
	task = TaxicabNumber.new()
	#  Test
	task.findNTaxicabNo(6)
end

main()

Output

1729
4104
13832
20683
32832
39312
/*
    Scala program for
    Taxicab Numbers
*/
class TaxicabNumber()
{
	def findNTaxicabNo(n: Int): Unit = {
		// Auxiliary variables
		var result: Int = 0;
		var num: Int = 1;
		var count: Int = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			var a: Int = 1;
			while (a <= Math.pow(num, 0.3333333333))
			{
				var b: Int = a + 1;
				while (b <= Math.pow(num, 0.3333333333))
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count += 1;
					}
					b += 1;
				}
				a += 1;
			}
			if (count == 2)
			{
				// Display Taxicab number
				println(num);
				// Increase result count
				result += 1;
			}
			// Increase number count
			num += 1;
			// Reset count
			count = 0;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: TaxicabNumber = new TaxicabNumber();
		// Test
		task.findNTaxicabNo(6);
	}
}

Output

1729
4104
13832
20683
32832
39312
import Foundation;
/*
    Swift 4 program for
    Taxicab Numbers
*/
class TaxicabNumber
{
	func findNTaxicabNo(_ n: Int)
	{
		// Auxiliary variables
		var result: Int = 0;
		var num: Int = 1;
		var count: Int = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			var a: Int = 1;
			while (Double(a) <= pow(Double(num), 0.3333333333))
			{
				var b: Int = a + 1;
				while (Double(b) <= pow(Double(num), 0.3333333333))
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count += 1;
					}
					b += 1;
				}
				a += 1;
			}
			if (count == 2)
			{
				// Display Taxicab number
				print(num);
				// Increase result count
				result += 1;
			}
			// Increase number count
			num += 1;
			// Reset count
			count = 0;
		}
	}
}
func main()
{
	let task: TaxicabNumber = TaxicabNumber();
	// Test
	task.findNTaxicabNo(6);
}
main();

Output

1729
4104
13832
20683
32832
39312
/*
    Kotlin program for
    Taxicab Numbers
*/
class TaxicabNumber
{
	fun findNTaxicabNo(n: Int): Unit
	{
		// Auxiliary variables
		var result: Int = 0;
		var num: Int = 1;
		var count: Int = 0;
		// This loop are executed until result count are not have to n.
		while (result < n)
		{
			var a: Int = 1;
			while (a <= Math.pow(num.toDouble(), 0.3333333333))
			{
				var b: Int = a + 1;
				while (b <= Math.pow(num.toDouble(), 0.3333333333))
				{
					if ((a * a * a) + (b * b * b) == num)
					{
						// When a³ + b³ = num
						count += 1;
					}
					b += 1;
				}
				a += 1;
			}
			if (count == 2)
			{
				// Display Taxicab number
				println(num);
				// Increase result count
				result += 1;
			}
			// Increase number count
			num += 1;
			// Reset count
			count = 0;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: TaxicabNumber = TaxicabNumber();
	// Test
	task.findNTaxicabNo(6);
}

Output

1729
4104
13832
20683
32832
39312

Output Explanation

The output provided by the code represents the first six taxicab numbers when the input is set to 6. These numbers are: 1729, 4104, 13832, 20683, 32832, and 39312.

Time Complexity

The time complexity of this code can be analyzed as follows:

  • The outer while loop will iterate until the result count reaches n.
  • The two nested for loops iterate up to the cube root of num, which can be considered as O(n^0.3333333333), where n is the current value of num.

Therefore, the overall time complexity of the code can be approximated to O(n^(1.6666666667)), where n is the input parameter representing the nth taxicab number to be found.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment