4

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;

}
4

2 に答える 2

5

これらの番号は「タクシー番号」と呼ばれることもあります。

数学者の GH Hardy は、入院中の共同研究者である Srinivasa Ramanujan を訪ねる途中でした。ハーディはラマヌジャンに、彼がナンバープレート 1729 のタクシーで旅行したことを述べましたが、それは鈍い番号に見えました。これに対して、ラマヌジャンは、1729 は非常に興味深い数であると答えました。これは、2 つの数の立方体の合計として 2 つの異なる方法で表現できる最小の数でした。実際、10 3 + 9 3 = 12 3 + 1 3 = 1729 です。

立方体を合計する 2 つの数値xとyは両方とも 0 とnの立方根の間にある必要があるため、1 つの解決策はxとyのすべての組み合わせを徹底的に検索することです。より良い解決策は、x = 0 とyがnの立方根で始まり、3 方向の決定を繰り返します。x 3 + y 3 < nの場合はxを増やし、x 3 + y 3 > nの場合はyを減らします。もし× 3+ y 3 = 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))

この問題については私のブログで説明しています。

于 2015-10-01T01:33:11.577 に答える
0

あなたのアプローチの基本的な違いは、(i,j) と (j,i) にアクセスすることです。
@ user448810 によって提案されたアルゴリズムは、i が while 条件で常に j より小さいため、1 回だけアクセスします。

上記のコードの Java 実装:

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

}
于 2016-01-21T16:27:52.900 に答える