ツリー状の自然数の列（3）

前回のような計算はGPUを使うと画期的に速くなる。
実際、25倍くらい速くなった。
2²⁸で、計算が返ってこなくなった。
原因はまだ分からない。

前回、距離が同じ自然数の集合の個数は、
距離が1長くなると4/3倍になると推定したが、
これを確認してみよう。

最後のほうを取り出すと、

57  408002 1.263676599

58  515542 1.263577139

59  651407 1.263538179

60  823238 1.263784393

61 1040490 1.263899383

62 1315036 1.263862219

63 1661989 1.263835363

3カラム目は、その行の個数から1つ上で割ったもの。
だいたい1.264になっている。

#include 

#include 
using namespace std;
typedef unsigned int    uint;
int calc_length(int m);
void main() {

    const int   dist_limit = 63;

    int     num[dist_limit+1];

    for(int i = 0; i <= dist_limit; i++) {

        num[i] = 0;

    }

    

    stack >   stk;    // (n, dist)

    stk.push(make_pair(1, 0));

    while(!stk.empty()) {

        __int64     n = stk.top().first;

        int     dist = stk.top().second;

        stk.pop();

        for( ; dist <= dist_limit; dist++) {

            num[dist]++;

            if(dist < dist_limit && n > 4 && n % 6 == 4)

                stk.push(make_pair(n / 3, dist + 1));

            n <<= 1;

        }

    }

    

    for(int dist = 0; dist <= dist_limit; dist++) {

        cout << dist << " " << num[dist] << endl;

    }

}
int calc_length(int m) {

    const uint  limit = 0xFFFFFFFE / 3;

    uint    n[2];

    n[0] = m; n[1] = 0;

    int     len;

    for(len = 0; n[0] != 1 || n[1] != 0; len++) {

        if(n[0] & 1) {

            if(n[1] > limit) {

                cerr << "overflow." << endl;

                exit(1);

            }

            triple(n);

        }

        else {

            half(n);

        }

    }

    return len;

}