java - 使 Hardy-Ramanujan 第 n 个数字查找器更有效率

Question

我试图制定一个算法来找到第 n 个 Hardy-Ramanujan 数(一个可以用多种方式表示为 2 个立方体之和的数)。除了我基本上是用另一个立方体检查每个立方体，看看它是否等于另外 2 个立方体的总和。关于如何提高效率的任何提示？我有点难过。

public static long nthHardyNumber(int n) {

    PriorityQueue<Long> sums = new PriorityQueue<Long>();
    PriorityQueue<Long> hardyNums = new PriorityQueue<Long>();
    int limit = 12;
    long lastNum = 0;

    //Get the first hardy number
    for(int i=1;i<=12;i++){
        for(int j = i; j <=12;j++){
            long temp = i*i*i + j*j*j;
            if(sums.contains(temp)){
                if(!hardyNums.contains(temp))
                    hardyNums.offer(temp);
                if(temp > lastNum)
                    lastNum = temp;
            }
            else
                sums.offer(temp);
        }
    }
    limit++;

    //Find n hardy numbers
    while(hardyNums.size()<n){
        for(int i = 1; i <= limit; i++){
            long temp = i*i*i + limit*limit*limit;
            if(sums.contains(temp)){
                if(!hardyNums.contains(temp))
                    hardyNums.offer(temp);
                if(temp > lastNum)
                    lastNum = temp;
            }
            else
                sums.offer(temp);
        }
        limit++;
    }

    //Check to see if there are hardy numbers less than the biggest you found
    int prevLim = limit;
    limit = (int) Math.ceil(Math.cbrt(lastNum));
    for(int i = 1; i <= prevLim;i++){
        for(int j = prevLim; j <= limit; j++){
            long temp = i*i*i + j*j*j;
            if(sums.contains(temp)){
                if(!hardyNums.contains(temp))
                    hardyNums.offer(temp);
                if(temp > lastNum)
                    lastNum = temp;
            }
            else
                sums.offer(temp);
        }
    }

    //Get the nth number from the pq
    long temp = 0;
    int count = 0;
    while(count<n){
        temp = hardyNums.poll();
        count++;
    }
    return temp;

}

Answer 1

这些号码有时被称为“出租车”号码:

The mathematician G. H. Hardy was on his way to visit his collaborator Srinivasa Ramanujan who was in the hospital. Hardy remarked to Ramanujan that he traveled in a taxi cab with license plate 1729, which seemed a dull number. To this, Ramanujan replied that 1729 was a very interesting number — it was the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed, 10³ + 9³ = 12³ + 1³ = 1729.

由于x和y这两个数的立方之和必须都在0和n的立方根之间，一个解决方案是对 x 和 y 的所有组合进行详尽搜索。一个更好的解决方案从 x = 0 和 y n 的立方根开始，然后重复做出三向决策:如果 x³ + y³ <n，增加x，如果 x³ + y³> n，减少y，或者如果 x³ + y³ = n，报告成功并继续寻找更多:

function taxicab(n)
    x, y = 0, cbrt(n)
    while x <= y:
        s = x*x*x + y*y*y
        if s < n then x = x + 1
        else if n < s then y = y - 1
        else output x, y
             x, y = x + 1, y - 1

下面是 100000 以内的出租车号码:

1729: ((1 12) (9 10))
4104: ((2 16) (9 15))
13832: ((2 24) (18 20))
20683: ((10 27) (19 24))
32832: ((4 32) (18 30))
39312: ((2 34) (15 33))
40033: ((9 34) (16 33))
46683: ((3 36) (27 30))
64232: ((17 39) (26 36))
65728: ((12 40) (31 33))

我在 my blog 讨论这个问题.