Finding taxicab Numbers
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
Related videos on Youtube
Comments
-
sasidhar about 1 year
Find the first
n
taxicab numbers. Given a valuen
. 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 over 11 yearsNote 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 over 11 yearsToo localized? Seriously? Come on guys, this is a perfectly good programming question.
-
-
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 over 11 yearsI 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 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 over 11 yearsAlso, could the downvoters please explain what is wrong with the algorithm?
-
sasidhar over 11 yearsto 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 over 11 yearsI 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 over 11 yearsPrecisely, 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 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 over 11 years@nico see my answer, it takes a lot less computations and space i guess
-
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 over 10 yearsWhat is the running time of this algorithm? O(n^2)?
-
sreeprasad about 9 yearsNeat. 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 ).