Ramanujan's number in C

Question

[Hardy about Ramanujan]: I remember once going to see him when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."

The two different ways are 1³ + 12³ and 9³ + 10³

I'm writing a series of functions (in C) to calculate different things related to Ramanujan's numbers. I'm now trying to write a function that returns the i-th Ramanujan's number. Since I've already created a function that checks whether a number is a Ramanujan number or not, the easy way would be to check every number, from 0 to infinity. If a given number is a Ramanujan number, increment a counter by one. Once the counter equals the index I'm looking for, I return the number. In code:

unsigned long ramanujan_index (unsigned long x, int counter, int index) 
{
    if (counter == index)
        return x - 1;
    if (is_ramanujan(x))
        return ramanujan_index(x + 1, counter + 1, index);
    else
        return ramanujan_index(x + 1, counter, index);
}

It works, sure, but I'm a little worried that it's not as efficient as it could possibly be. Checking every number doesn't seem like the best solution. More so if we consider the first number is 1729, and the second is 4104. It seems that it'd take quite a lot of steps to find the 5th Ramanujan number (32832 steps, actually, since it has to check every number from 0 to 32832, which is the 5th number). Is there a better way to do so?

Use an array to count the number of realisations for a resulting sum. — wildplasser, Oct 21 '21 at 23:23
There is no need to use recursion for this, and it is wasteful. — Eric Postpischil, Oct 21 '21 at 23:46
Consider testing each integer in sequence takes n trials to find a Ramanujan number that is n. But if we make a list of all cubes of integers up to cbrt(n) and then combine all pairs of those, we produce about cbrt(n)^2/2 pairs, through which we can seek duplicates, which are Ramanujan numbers. So consecutive testing is not the best way. There may be other improvements. — Eric Postpischil, Oct 21 '21 at 23:50
Interesting question, for a different view on this problem, take a look at the Online Encyclopedia of Integer Sequences (a web search will find it) and see what it says about sequences which start with 1729, 4104, 32832. — Robert Dodier, Oct 22 '21 at 00:19
In can be done in C, but you need a min-heap to do it efficiently. So you might want to consider a different language. — user3386109, Oct 22 '21 at 00:28
@EricPostpischil that sounds quite reasonable. Thank you, I'll try it. — Crash Bandicoot, Oct 22 '21 at 00:56
@RobertDodier: The OEIS says [“Sorry, but the terms do not match anything in the table.”](https://oeis.org/search?q=1729%2C+4104%2C+32832&language=english&go=Search) — Eric Postpischil, Oct 22 '21 at 01:11
@CrashBandicoot: That may not be the best option, just pointing it out to show that consecutive testing is not the best. — Eric Postpischil, Oct 22 '21 at 01:11
These are sometimes called [taxicab numbers](https://oeis.org/A001235), although that name usually refers to a different sequence: taxicab(n) is the smallest number expressible as the sum of two cubes in `n` different ways, for every `n`. Our sequence of 'Ramanujan numbers', which OP did not define but presumably means all numbers expressible in at least two different ways, is easier to compute : if m is in the sequence, so is `m*k^3` for every positive `k`, so you can restrict your testing to cubefree numbers — kcsquared, Oct 22 '21 at 03:39

chqrlie · Answer 1 · 2021-10-24T15:08:18.020

Here is a simple program using nested loops to enumerate Ramanujan numbers of different orders. It uses an array to store the number of ways and enumerates cubes to generate sums. The computation is performed in slices to take advantage of CPU caches and allow for ranges that exceed memory size.

This program enumerates Ramanujan numbers of order 2 up to 1 million in less than 0.01s and finds the smallest Ramanujan number of order 4 in a few hours: 6963472309248

#include <stdio.h>
#include <stdlib.h>

#define MAX_SLICE   0x400000   // use 4MB at a time

int main(int argc, char **argv) {
    int order = 2;
    size_t min = 0, max = 1000000, a, a3, b, n, i, n1, n2;

    while (*++argv) {
        char *p;
        n = strtoull(*argv, &p, 0);
        if (*p == '-') {
            min = n;
            max = strtoull(p + 1, NULL, 0);
        } else {
            if (n < 10)
                order = n;
            else
                max = n;
        }
    }
    for (n1 = min; n1 <= max; n1 = n2) {
        size_t slice = (max + 1 - n1 <= MAX_SLICE) ? max + 1 - n1 : MAX_SLICE;
        unsigned char *count = calloc(slice, 1);
        n2 = n1 + slice;
        for (a = 1; (a3 = a * a * a) < n2; a++) {
            if (a3 + a3 >= n1) {
                for (b = 1; b <= a && (n = a3 + b * b * b) < n2; b++) {
                    if (n >= n1)
                        count[n - n1]++;
                }
            }
        }
        for (i = n1; i < n2; i++) {
            if (count[i - n1] >= order)
                printf("%llu\n", (long long unsigned int)i);
        }
        free(count);
    }
    return 0;
}

Runs:

chqrlie$ time ./rama
1729
4104
13832
20683
32832
39312
40033
46683
64232
65728
110656
110808
134379
149389
165464
171288
195841
216027
216125
262656
314496
320264
327763
373464
402597
439101
443889
513000
513856
515375
525824
558441
593047
684019
704977
805688
842751
885248
886464
920673
955016
984067
994688

real    0m0.008s
user    0m0.002s
sys     0m0.002s

chqrlie$ time ./rama 10000000000 2 | wc -l
    4724

real    0m7.526s
user    0m7.373s
sys     0m0.061s

chqrlie$ time ./rama 6963000000000-6964000000000 4
6963472309248

real    0m10.383s
user    0m10.243s
sys     0m0.050s

Ramanujan's number in C

1 Answers1