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

数学 C++

距離ごとに分布を調べてみた。
次は、距離62のときの、距離62の自然数の個数の2n 〜 2n+1倍の間にある個数を数えたものである。



 n    個数

 0   3572

 1   9147

 3  25136

 6  55717

 8  67762

 9  35219

11 158332

13   8793

14 196219

16 223037

19 203270

21 154112

24  96605

26    185

27  49242

29  20290

32   6519

34   1578

37    271

39      1

40     28

42      1

分布が露骨にまだらになっている。


グラフを書いてみた。
横軸が自然数の対数、縦軸が距離、
青がその距離の自然数が存在する部分、白は全くない部分、
横軸は4ピクセルで2倍。
このようなきれいな分布になる。




#include 

#include 

#include 

#include 
using namespace std;
void main() {

    const int   dist_limit = 62;

    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;

        }

    }

    

    map    distribute[dist_limit+1];

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

    int     counter = 0;

    while(!stk.empty()) {

        __int64     n = stk.top().first;

        int     dist = stk.top().second;

        stk.pop();

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

            __int64 a = n / num[dist];

            int     b = 0;

            while(a) {

                b++;

                a >>= 1;

            }

            distribute[dist][b]++;

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

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

            n <<= 1;

        }

    }

    

    typedef map::const_iterator    MIT;

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

        const map& d = distribute[dist];

        for(MIT p = d.begin(); p != d.end(); ++p) {

            cout << dist << "," << p->first << "," << p->second << endl;

        }

    }

}