Finding taxicab Numbers

Question

Find the first n taxicab numbers. Given a value n. I would like to find the first n taxicab numbers. A taxicab being a number that can be expressed as the sum of two perfect cubes in more than one way.

(Note that there are two related but different sets referred to as 'taxicab numbers': the sums of 2 cubes in more than 1 way, and the smallest numbers that are the sum of 2 positive integral cubes in n ways. This question is about the former set, since the latter set has only the first six members known)

For example:

1^3 + 12^3 = 1729 = 9^3 + 10^3

I would like a rough overview of the algorithm or the C snippet of how to approach the problem.

The first five of these are:

   I    J      K    L      Number 
---------------------------------
   1   12      9   10      1729       
   2   16      9   15      4104      
   2   24     18   20     13832       
  10   27     19   24     20683      
   4   32     18   30     32832    

Answer 1

I figured out the answer could be obtained this way:

#include<stdio.h>

int main() {
    int n, i, count=0, j, k, int_count;
    printf("Enter the number of values needed: ");
    scanf("%d", &n);
    i = 1;
    while(count < n) {
       int_count = 0;
       for (j=1; j<=pow(i, 1.0/3); j++) {
          for(k=j+1; k<=pow(i,1.0/3); k++) {
              if(j*j*j+k*k*k == i)
              int_count++;
          }
       }
       if(int_count == 2) {
          count++;
          printf("\nGot %d Hardy-Ramanujan numbers %d", count, i);  
       }
       i++;
    }
}

Since a^3+b^3 = n, a should be less than n^(1/3).

Answer 2

There are two ways to write the solution in Python: dynamic programming & brute force.

def ramanujanDynamicProgramming(n):
    numbers = []
    Ds = dict()

    # Init List
    for d in xrange(0, n ** 3):
        Ds[d] = False

    # Fill list
    for d in xrange(0, n):
        Ds[d**3] = d

    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):

                if a != b and a != c and b != c:
                    d = a ** 3 + b ** 3 - c ** 3

                    if a != d and b != d and c != d and d >= 0 and d < n ** 3:
                        if Ds[d] != False:
                            numbers.append((a, b, c, Ds[d]))

        return numbers 
print "Dynamic Programming"
print ramanujanDynamicProgramming(n)

The DP approach only takes O(n^3).

def ramanujanBruteForce(n):
    numbers = []
    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):
                for d in xrange(0, n):
                    if a != b and a != c and a != d and b != c and b != d and c != d:
                        if a ** 3 + b ** 3 == c ** 3 + d ** 3:
                            numbers.append((a, b, c, d))

        return numbers
print "Brute Force"
print ramanujanBruteForce(n)

The BF approach is BF is O(n^4).

Answer 3

This solution (in python) generates the first n taxi cab number in a bottom up approach. The time complexity is m^2 where m is the highest number it will go to generate the n numbers.

def generate_taxi_cab_numbers(n):
    generated_number = 0
    v = {}
    c = {}
    i = 0
    while generated_number < n:
        c[i] = i*i*i
        for j in xrange(i):
            s = c[j] + c[i]
            if s in v:
                generated_number = generated_number + 1
                yield (s, (j, i), v[s])
            v[s] = (j,i)
        i = i + 1


def m(n):
    for x in generate_taxi_cab_numbers(n):
       print x

Answer 4

Below is the even better java code for printing N ramanujan numbers as it has even less time complexity. Because, it has only one for loop.

import java.util.*;
public class SolutionRamanujan 
{
    public static void main(String args[] ) throws Exception 
    {
        SolutionRamanujan s=new SolutionRamanujan();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int i=0,k=1;
        while(i<n){
            if(s.checkRamanujan(k))
            {
                i=i+1;
                System.out.println(i+" th ramanujan number is "+k);
            }
            k++;
        }
        scan.close();
    }
    //checking whether a number is ramanujan number
    public boolean checkRamanujan(int a)
    {   
        int count=0;
        int cbrt=(int)Math.cbrt(a);
        //numbers only below and equal to cube th root of number
        for(int i=1;i<=cbrt;i++)
        {
            int difference=a-(i*i*i);
            int a1=(int) Math.cbrt(difference);                //checking whether the difference is perfect cube 

            if(a1==Math.cbrt(difference)){
                count=count+1;
            }
            if(count>2){            //checking if two such pairs exists i.e. (a*a*a)+(b*b*b)=(c*c*c)+(d*d*d)=number
                return true;
            }
        }
        return false;
    }
}

Answer 5

EDIT: for those who do not know what R is, here is a link.

My C being a bit rusty... I will write a solution in R, it should not be difficult to adapt. The solution runs very fast in R, so it should be even faster in C.

# Create an hash table of cubes from 1 to 100

numbers <- 1:100
cubes <- numbers ^ 3

# The possible pairs of numbers
pairs <- combn(numbers, 2)

# Now sum the cubes of the combinations
# This takes every couple and sums the values of the cubes
# with the appropriate index 
sums <- apply(pairs, 2, function(x){sum(cubes[x])})

So:

numbers will be: 1, 2, 3, 4, ..., 98, 99, 100
cubes will be: 1, 8, 27, 64, ..., 941192, 970299, 1000000
pairs will contain:

     [,1] [,2] [,3] [,4] [,5] ... [,4949] [,4950]
[1,]    1    1    1    1    1 ...      98      99
[2,]    2    3    4    5    6 ...     100     100

sums will be: 9 28 65 126 217 344 ... 1911491 1941192 1970299

A quick check that we are on the right track...

> which(sums == 1729)
[1]  11 765  <--- the ids of the couples summing to 1729
> pairs[,11]
[1]  1 12
> pairs[,765]
[1]  9 10

Now, let's find which are the couples with the same sums.

table(sums) gives us a neat summary like

> 9 28 35 65 72 91 ...                        1674 1729 1736    
  1  1  1  1  1  1 .... <lots of 1s here> ...    1    2    1

So let's just find which elements of table(sums) are == 2

doubles <- which(table(sums) == 2)

taxi.numbers <- as.integer(names(doubles))
 [1]    1729    4104   13832   20683   32832   39312   40033   46683   64232   65728
[11]  110656  110808  134379  149389  165464  171288  195841  216027  216125  262656
[21]  314496  320264  327763  373464  402597  439101  443889  513000  513856  515375
[31]  525824  558441  593047  684019  704977  805688  842751  885248  886464  920673
[41]  955016  984067  994688 1009736 1016496

And finally (to be read two-by-two), the corresponding integer pairs

> pairs[,doubles]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
[1,]    1    9    2    9    2   18   10   19    4    18     2    15     9    16     3
[2,]   12   10   16   15   24   20   27   24   32    30    34    33    34    33    36
     [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29]
[1,]    27    17    26    12    31     4    36     6    27    12    38     8    29    20
[2,]    30    39    36    40    33    48    40    48    45    51    43    53    50    54
     [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38] [,39] [,40] [,41] [,42] [,43]
[1,]    38    17    24     9    22     3    22     5    45     8    36     4    30    18
[2,]    48    55    54    58    57    60    59    60    50    64    60    68    66    68
     [,44] [,45] [,46] [,47] [,48] [,49] [,50] [,51] [,52] [,53] [,54] [,55] [,56] [,57]
[1,]    32    30    51     6    54    42    56     5    48    17    38    10    45    34
[2,]    66    67    58    72    60    69    61    76    69    76    73    80    75    78
     [,58] [,59] [,60] [,61] [,62] [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71]
[1,]    52    15    54    24    62    30    57     7    63    51    64     2    41    11
[2,]    72    80    71    80    66    81    72    84    70    82    75    89    86    93
     [,72] [,73] [,74] [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85]
[1,]    30    23    63     8    72    12    54    20    33    24    63    35    59    29
[2,]    92    94    84    96    80    96    90    97    96    98    89    98    92    99
     [,86] [,87] [,88] [,89] [,90]
[1,]    60    50    59    47    66
[2,]    92    96    93    97    90

So:

1,12 and 9,10 give 1729
2,16 and 9,15 give 4104
2,24 and 18,20 give 13832
and so on!

Answer 6

Quick and naive algorithm (if I correctly understand the problem):

Let's compute the cubes of all natives integer from 1 to N; then computes all sums of two cubes. These sums can be stored in a triangular matrix; avoid filling the whole square matrix. Finally, find the non-unique elements in your triangular matrix, these are the very HR numbers (if you let me call the numbers we want to compute like this). Moreover, by sorting the array while keeping original indices, you can easily deduce the decompositions of such a number.

My solution has a little defect: I don't know how to fix N depending on your input n, that is how many cubes do I have to compute in order to have at least n HR numbers? Interesting problem left.