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:
- Initialize variables: result = 0, num = 1, and count = 0.
- 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.
- If the count is equal to 2, it means we have found a taxicab number:
- Print the taxicab number (num).
- Increment the result variable.
- Increment the num variable.
- Reset the count variable to 0.
- 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
39312package 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
39312import 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
39312import 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
39312Output 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.
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