Finding taxicab Numbers

17,327

Solution 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).

Solution 2

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;
    }
}

Solution 3

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!

Solution 4

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.

Solution 5

Better Algorithm than Nikhitha Reddy above. We dont have to check (i,j) and (j,i) both.

Here is Java code.

import java.util.*;

public class efficientRamanujan{

public static void main(String[] args) {
    efficientRamanujan s=new efficientRamanujan();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int i=0,k=1;
        while(i<n){
           if(s.efficientRamanujan(k))
        {
            i=i+1;
            System.out.println(i+" th ramanujan number is "+k);
        }
        k++;
    }
    scan.close();
   }






public boolean efficientRamanujan(int n){
    int count=0;

    int x = 1;
    int y = (int) Math.cbrt(n);

    while (x<y){

        int sum = (int) Math.pow(x,3) + (int) Math.pow(y,3);
        if(sum<n){
           x = x+1;
        }else if(sum>n){
           y = y-1;
        }else{
           count++;
           x = x+1;
           y = y-1;
    }

    if(count>=2){
        return true;
    }
}

return false;
}

  }

Reference: blog

Share:
17,327

Related videos on Youtube

sasidhar
Author by

sasidhar

I am a computer science engineering student.

Updated on August 19, 2022

Comments

  • sasidhar
    sasidhar about 1 year

    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    
    
    • nico
      nico over 11 years
      Note that 1729 is the Hardy Ramanujan Number, there is no generic name for numbers that can be expressed as sum of cubes of two different pairs of integers. Interesting question nevertheless
    • nico
      nico over 11 years
      Too localized? Seriously? Come on guys, this is a perfectly good programming question.
  • nico
    nico over 11 years
    @sasidhar: what? You are asking for an algorithm, here is a fast algorithm that works as intended. No need to downvote just because it is not in C. I even added comments and output to help you understand it.
  • sasidhar
    sasidhar over 11 years
    I am not the one who down voted it dude. I didn't understand it and so i left it intact. I will upvote it once i get what you are trying do there.
  • nico
    nico over 11 years
    @sasidhar: OK, sorry, I should not have implied it was you. Anyway, I am creating an hash table of cubes, an hash table of pairs of numbers and summing the cubes of the pairs. Then I find the couple with equal sums. R makes it particularly easy to manipulate this kind of data.
  • nico
    nico over 11 years
    Also, could the downvoters please explain what is wrong with the algorithm?
  • sasidhar
    sasidhar over 11 years
    to my understanding, you are computing this for the numbers between 1-100 right? how do you claim that this will be sufficient in all cases?? At times, this will be underdoing things and at times this will be overdoing it right??
  • nico
    nico over 11 years
    I am just computing a table of taxi numbers, you can just change the 100 to whatever suits your needs. If you want a precise number of numbers then you would have to do a loop which (at least in the case of R) is way slower. With numbers in [1,100] you will compute 45 numbers, and it is almost instantaneous. My PC calculates all the combinations of numbers in [1,1000] in a couple of seconds.
  • sasidhar
    sasidhar over 11 years
    Precisely, given n, what is the upper limit that is sufficient? and besides finding the similar items that have distinct numbers as array indices in any normal programming language is a problem again, this approach though promises part of the solution is seeming like a brute force approach. (upvoted)
  • nico
    nico over 11 years
    @sasidhar: surely, it is an "half-brute force" way. (btw you get ~1500 numbers with [1,1000]). An analytical solution to your problem would be very neat, but my numerical calculus classes are a bit too far away in time... maybe on Math.SE?
  • sasidhar
    sasidhar over 11 years
    @nico see my answer, it takes a lot less computations and space i guess
  • nico
    nico over 11 years
    @sasidhar: will surely be faster most of the times, slightly difficult to compare as R is not a compiled language!
  • Neel
    Neel over 10 years
    What is the running time of this algorithm? O(n^2)?
  • sreeprasad
    sreeprasad about 9 years
    Neat. The time complexity of your algorithm should be O(n^(4/3)) assuming Math.cbrt(a) can be found in constant time ( this part I doubt ).