有限自然数列のナンバリング案１

KuDaH

有限自然数列

有限自然数列とは、項数が有限で、各項が自然数（正整数）である数列を指します。有限自然数列と分類される全ての数列に対し、唯一の番号を与え、　

数列　　⇔　　番号

という一対一の対応付けを実現しようというのが本稿の目的です。
今回はその定式化案その１です。


定式化（番号設定のルール）

・数列 $${\{1\}}$$ の番号を $${1}$$ とする。
・番号 $${k}$$ が与えられてある数列に対し、新しい項として、 $${1}$$ を付け加えただけの数列があった場合、その数列 の番号を、$${2k}$$ とする。
・番号 $${k}$$ が与えられてある数列に対し、最終項が、 $${1}$$ 大きいだけの違いを持つ数列があった場合、その数列 の番号を、$${2k+1}$$ とする。


具体例

数列と数字（自然数）が、$${“=”}$$で結ばれている時、数列の番号が、その数字で表される数値である事とします。
前述のルールにより、次のように定まります。

$${ 1 = \{1\}, \hspace{60pt} 13 = \{2,2\},  \hspace{50pt} 25 = \{2,1,2\},}$$
$${ 2 = \{1,1\}, \hspace{50pt} 14 = \{3,1\} ,\hspace{52pt} 26 = \{2,2,1\},}$$
$${ 3 = \{2\}, \hspace{60pt} 15 = \{4\} ,\hspace{62pt} 27 = \{2,3\},}$$
$${ 4 = \{1,1,1\}, \hspace{40pt} 16 = \{1,1,1,1,1\} ,\hspace{26pt} 28 = \{3,1,1\},}$$
$${ 5 = \{1,2\}, \hspace{50pt} 17 = \{1,1,1,2\} ,\hspace{36pt} 29 = \{3,2\},}$$
$${ 6 = \{2,1\}, \hspace{50pt} 18 = \{1,1,2,1\} ,\hspace{36pt} 30 = \{4,1\},}$$
$${ 7 = \{3\}, \hspace{60pt} 19 = \{1,1,3\} ,\hspace{44pt} 31 = \{5\},}$$
$${ 8 = \{1,1,1,1\}, \hspace{32pt} 20 = \{1,2,1,1\} ,\hspace{34pt} 32 = \{1,1,1,1,1,1\},}$$
$${ 9 = \{1,1,2\}, \hspace{42pt} 21 = \{1,2,2\} ,\hspace{45pt} 33 = \{1,1,1,1,2\},}$$
$${10 = \{1,2,1\}, \hspace{36pt} 22 = \{1,3,1\} ,\hspace{45pt} 34 = \{1,1,1,2,1\},}$$
$${11 = \{1,3\}, \hspace{46pt} 23 = \{1,4\} ,\hspace{55pt} 35 = \{1,1,1,3\},}$$
$${12 = \{2,1,1\} ,\hspace{37pt} 24 = \{2,1,1,1\} ,\hspace{36pt} 36 = \{1,1,2,1,1\},…}$$

性質

番号$${1}$$の数列$${\{1\}}$$は、数列の全項の和が$${1}$$です。
番号$${2,3}$$の数列は、数列の全項の和が$${2}$$です。
番号$${4～7}$$の数列は、数列の全項の和が$${3}$$です。
番号$${8～15}$$の数列は、数列の全項の和が$${4}$$です。
以後同様です。これらから、全項の和が$${k}$$である数列には$${2^{k-1}～2^k-1}$$の番号が当てられていることが解ります。
また、この範囲の数字は、二進法で表すと、$${k}$$桁になります。


数列→番号　変換方法

数列$${\{a_1,a_2,a_3,…,a_n\}}$$が与えられ、この数列の番号を求めるには、次のような方法があります。

数列$${\{a_1,a_2,a_3,…,a_n\}}$$に対し、初項だけ$${1}$$増やした、次のような「数字の並び」を考える。
$${[a_1+1,a_2,a_3,…,a_n]}$$
この「数字の並び」の各項が、$${1,2,3,4,5,6,...}$$であった場合、それぞれ、$${0,01,011,0111,01111,011111,…}$$という文字の置き換えを行う。
コンマを取り除くと、$${0}$$と$${1}$$だけの並びになるが、二進数と見なして数値に直すとそれが、その数列の番号になります。

数列の全項の和を$${N}$$とすると、「数字の並び」の全項の和は$${N+1}$$になります。文字の置き換えでは、置き換える前の数字の値が、置き換えた後の文字の数に一致するので、$${N+1}$$個の文字の並びになるが、この文字列は必ず$${01}$$から始まるので、$${N}$$桁の二進数となります。$${N}$$桁の二進数は、$${2^{N-1}～2^N-1}$$までの値を表現でき、これは、前述の性質の通りです。

例：
$${\{1,1,1,1,1\}→[2,1,1,1,1]→[01,0,0,0,0]→010000_2=16}$$
$${\{1,2,3,4,5\}→[2,2,3,4,5]→[01,01,011,0111,01111]}$$
$${\hspace{125pt}→0101011011101111_2=22255}$$

確認
$${{\small\{1,2,3\}=((1×2×2+1)×2×2+1)×2+1=(5×4+1)×2+1=43}}$$
$${{\small\{1,2,3,4\}=((43×2×2+1)×2+1)×2+1=(173×2+1)×2+1=695}}$$
$${{\small\{1,2,3,4,5\}=(((695×2×2+1)×2+1)×2+1)×2+1=22255}}$$

番号→数列　変換方法

番号から、それに対応する数列へ変換する方法は前述の方法を逆に行えば良いのですが、具体的には次のようになります。

番号を二進数に変換します。
先頭と最後に$${0}$$を付加し、以後これを文字列と呼びます。
文字列を左から見ていって、
　$${00...}$$→　数列に$${1}$$を追加し、文字列から一番左の$${0}$$を削除。
　$${010...}$$→　数列に$${2}$$を追加し、文字列左側にある$${01}$$を削除。
　$${0110...}$$→　数列に$${3}$$を追加し、同様に$${011}$$を削除。
　$${01110...}$$→　数列に$${4}$$を追加し、同様に$${0111}$$を削除。
　．．．
　$${011…110... {\scriptsize(k-1個の1が0に挟まれている状態)}}$$→数列に$${k}$$を追加し、$${011…11}$$を削除。
以下同様
これを文字列が一文字（最初に付加した後方の$${0}$$）になるまで繰り返す。
数列の最初の数字を$${1}$$小さく変更。

これで、番号から数列への変換ができます。

例：
$${100=1100100_2 → “011001000" →“001000",\{3\} →“01000",\{3,1\}}$$
$${→“000",\{3,1,2\} →“00",\{3,1,2,1\} →“0", \{3,1,2,1,1\}→\{2,1,2,1,1\}}$$
確認
上述のように$${25 = \{2,1,2\}}$$です。これに、$${1}$$が二つ加わっているので、$${100}$$は確かに$${\{2,1,2,1,1\}}$$であることが判ります。

もし文頭の定式化ルールに忠実に変換を行うならば、次のようになります。

番号が偶数の数列は、[番号/2]で与えられる数列に、$${1}$$が付け加えられた数列です。奇数ならば、[番号/2]で与えられる数列の最終項を$${1}$$大きくした数列です。
従って、[番号/2]の番号の数列が解れば、この番号の数列が解ります。
つまり、偶数か奇数かを記録し、番号を[番号/2]に変更。これを、番号が$${0}$$になるまで繰り返し、数列を逆操作で再現します。
ただし、番号$${0}$$に対応する数列はありません。$${\{0\}}$$なる数列は、有限自然数列に分類されないので、番号を与えていないのですが、例外的に、

$${0}$$　＝　$${\{0\}}$$

として大丈夫です。
番号$${0}$$を$${2}$$倍して$${1}$$加えたのが$${1}$$であり、また、$${\{0\}}$$の最終項を$${1}$$大きくしたのが、$${\{1\}}$$という数列なので、ルールに合致するからです。

直前に「番号が偶数か奇数かを記録し、番号を[番号/2]に変更」と書きましたが、これは、番号を二進数に変換することを意味します。記録の最後の方から読み取ることは、二進数に直した数字の大きな桁の方から、数字を読み取る事を意味します。従って、数列$${\{0\}}$$に対し、
・数字が$${1}$$なら、数列の最終項を$${1}$$大きくする
・数字が$${0}$$なら、数列に、$${1}$$を追加する
を繰り返せばよいことになります。

例、$${100=1100100_2}$$
$${1}$$が二つ続くので、数列$${\{0\}}$$に対し、最終項を$${2}$$大きくして、数列は$${\{2\}}$$に変更。続いて、$${0}$$が二つ続くので、$${1}$$を二つ付け加え、$${\{2,1,1\}}$$に。続いて、$${1}$$なので、最終項を$${1}$$大きくして、$${\{2,1,2\}}$$に。続いて、$${0}$$が二つ続くので、$${1}$$を二つ付け加え、$${\{2,1,2,1,1\}}$$。確かにこれは、$${100}$$に対応する数列です。

以下、番号から数列へ、数列から番号へ変換するCのプログラムを添えておきます。


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

void f(int n){
    static char r[100];
    int msb=1,flag=0;
    while(msb<=n)msb*=2;
    for(r[0]=0;(msb/=2)>0;)if(n & msb) r[flag]++;else r[++flag]=1;
    printf("{%d",r[0]);
    for(int i=1;i<=flag;i++)printf(",%d",r[i]);
    printf("}");
}
int g(char *b){
    int i=0,j,k,r=(1<<b[0])-1;
    while((j=b[++i])>0)for(r=2*r,k=1;k<j;k++)r=2*r+1;
    return r;
}
int main(int argc,char *argv[]){
    int i,x,lx=0;
    char b[6]={0,0,0,0,0,0},c[][3]={"",",1",",2",",3",",4",",5",",6",",7",",8",",9"};

    for(i=1;i<101;i++)printf("\n%4d = ",i),f(i);
    printf("\n\n");
    for(b[0]=1;b[0]<5;b[0]++)    for(b[1]=0;b[1]<4;b[1]++)
    for(b[2]=0;b[2]<3;b[2]++)    for(b[3]=0;b[3]<3;b[3]++)
    for(b[4]=0;b[4]<3;b[4]++){
        x=g(b);
        if(x!=lx)printf("\n%4d = {%d%s%s%s%s}",x,b[0],c[b[1]],c[b[2]],c[b[3]],c[b[4]]);
        lx=x;
    }

    printf("\nend\n");
    return 0;
}





   1 = {1}
   2 = {1,1}
   3 = {2}
   4 = {1,1,1}
   5 = {1,2}
   6 = {2,1}
   7 = {3}
   8 = {1,1,1,1}
   9 = {1,1,2}
  10 = {1,2,1}
  11 = {1,3}
  12 = {2,1,1}
  13 = {2,2}
  14 = {3,1}
  15 = {4}
  16 = {1,1,1,1,1}
  17 = {1,1,1,2}
  18 = {1,1,2,1}
  19 = {1,1,3}
  20 = {1,2,1,1}
  21 = {1,2,2}
  22 = {1,3,1}
  23 = {1,4}
  24 = {2,1,1,1}
  25 = {2,1,2}
  26 = {2,2,1}
  27 = {2,3}
  28 = {3,1,1}
  29 = {3,2}
  30 = {4,1}
  31 = {5}
  32 = {1,1,1,1,1,1}
  33 = {1,1,1,1,2}
  34 = {1,1,1,2,1}
  35 = {1,1,1,3}
  36 = {1,1,2,1,1}
  37 = {1,1,2,2}
  38 = {1,1,3,1}
  39 = {1,1,4}
  40 = {1,2,1,1,1}
  41 = {1,2,1,2}
  42 = {1,2,2,1}
  43 = {1,2,3}
  44 = {1,3,1,1}
  45 = {1,3,2}
  46 = {1,4,1}
  47 = {1,5}
  48 = {2,1,1,1,1}
  49 = {2,1,1,2}
  50 = {2,1,2,1}
  51 = {2,1,3}
  52 = {2,2,1,1}
  53 = {2,2,2}
  54 = {2,3,1}
  55 = {2,4}
  56 = {3,1,1,1}
  57 = {3,1,2}
  58 = {3,2,1}
  59 = {3,3}
  60 = {4,1,1}
  61 = {4,2}
  62 = {5,1}
  63 = {6}
  64 = {1,1,1,1,1,1,1}
  65 = {1,1,1,1,1,2}
  66 = {1,1,1,1,2,1}
  67 = {1,1,1,1,3}
  68 = {1,1,1,2,1,1}
  69 = {1,1,1,2,2}
  70 = {1,1,1,3,1}
  71 = {1,1,1,4}
  72 = {1,1,2,1,1,1}
  73 = {1,1,2,1,2}
  74 = {1,1,2,2,1}
  75 = {1,1,2,3}
  76 = {1,1,3,1,1}
  77 = {1,1,3,2}
  78 = {1,1,4,1}
  79 = {1,1,5}
  80 = {1,2,1,1,1,1}
  81 = {1,2,1,1,2}
  82 = {1,2,1,2,1}
  83 = {1,2,1,3}
  84 = {1,2,2,1,1}
  85 = {1,2,2,2}
  86 = {1,2,3,1}
  87 = {1,2,4}
  88 = {1,3,1,1,1}
  89 = {1,3,1,2}
  90 = {1,3,2,1}
  91 = {1,3,3}
  92 = {1,4,1,1}
  93 = {1,4,2}
  94 = {1,5,1}
  95 = {1,6}
  96 = {2,1,1,1,1,1}
  97 = {2,1,1,1,2}
  98 = {2,1,1,2,1}
  99 = {2,1,1,3}
 100 = {2,1,2,1,1}


   1 = {1}
   2 = {1,1}
   4 = {1,1,1}
   8 = {1,1,1,1}
  16 = {1,1,1,1,1}
  33 = {1,1,1,1,2}
  17 = {1,1,1,2}
  34 = {1,1,1,2,1}
  69 = {1,1,1,2,2}
   9 = {1,1,2}
  18 = {1,1,2,1}
  36 = {1,1,2,1,1}
  73 = {1,1,2,1,2}
  37 = {1,1,2,2}
  74 = {1,1,2,2,1}
 149 = {1,1,2,2,2}
   5 = {1,2}
  10 = {1,2,1}
  20 = {1,2,1,1}
  40 = {1,2,1,1,1}
  81 = {1,2,1,1,2}
  41 = {1,2,1,2}
  82 = {1,2,1,2,1}
 165 = {1,2,1,2,2}
  21 = {1,2,2}
  42 = {1,2,2,1}
  84 = {1,2,2,1,1}
 169 = {1,2,2,1,2}
  85 = {1,2,2,2}
 170 = {1,2,2,2,1}
 341 = {1,2,2,2,2}
  11 = {1,3}
  22 = {1,3,1}
  44 = {1,3,1,1}
  88 = {1,3,1,1,1}
 177 = {1,3,1,1,2}
  89 = {1,3,1,2}
 178 = {1,3,1,2,1}
 357 = {1,3,1,2,2}
  45 = {1,3,2}
  90 = {1,3,2,1}
 180 = {1,3,2,1,1}
 361 = {1,3,2,1,2}
 181 = {1,3,2,2}
 362 = {1,3,2,2,1}
 725 = {1,3,2,2,2}
   3 = {2}
   6 = {2,1}
  12 = {2,1,1}
  24 = {2,1,1,1}
  48 = {2,1,1,1,1}
  97 = {2,1,1,1,2}
  49 = {2,1,1,2}
  98 = {2,1,1,2,1}
 197 = {2,1,1,2,2}
  25 = {2,1,2}
  50 = {2,1,2,1}
 100 = {2,1,2,1,1}
 201 = {2,1,2,1,2}
 101 = {2,1,2,2}
 202 = {2,1,2,2,1}
 405 = {2,1,2,2,2}
  13 = {2,2}
  26 = {2,2,1}
  52 = {2,2,1,1}
 104 = {2,2,1,1,1}
 209 = {2,2,1,1,2}
 105 = {2,2,1,2}
 210 = {2,2,1,2,1}
 421 = {2,2,1,2,2}
  53 = {2,2,2}
 106 = {2,2,2,1}
 212 = {2,2,2,1,1}
 425 = {2,2,2,1,2}
 213 = {2,2,2,2}
 426 = {2,2,2,2,1}
 853 = {2,2,2,2,2}
  27 = {2,3}
  54 = {2,3,1}
 108 = {2,3,1,1}
 216 = {2,3,1,1,1}
 433 = {2,3,1,1,2}
 217 = {2,3,1,2}
 434 = {2,3,1,2,1}
 869 = {2,3,1,2,2}
 109 = {2,3,2}
 218 = {2,3,2,1}
 436 = {2,3,2,1,1}
 873 = {2,3,2,1,2}
 437 = {2,3,2,2}
 874 = {2,3,2,2,1}
1749 = {2,3,2,2,2}
   7 = {3}
  14 = {3,1}
  28 = {3,1,1}
  56 = {3,1,1,1}
 112 = {3,1,1,1,1}
 225 = {3,1,1,1,2}
 113 = {3,1,1,2}
 226 = {3,1,1,2,1}
 453 = {3,1,1,2,2}
  57 = {3,1,2}
 114 = {3,1,2,1}
 228 = {3,1,2,1,1}
 457 = {3,1,2,1,2}
 229 = {3,1,2,2}
 458 = {3,1,2,2,1}
 917 = {3,1,2,2,2}
  29 = {3,2}
  58 = {3,2,1}
 116 = {3,2,1,1}
 232 = {3,2,1,1,1}
 465 = {3,2,1,1,2}
 233 = {3,2,1,2}
 466 = {3,2,1,2,1}
 933 = {3,2,1,2,2}
 117 = {3,2,2}
 234 = {3,2,2,1}
 468 = {3,2,2,1,1}
 937 = {3,2,2,1,2}
 469 = {3,2,2,2}
 938 = {3,2,2,2,1}
1877 = {3,2,2,2,2}
  59 = {3,3}
 118 = {3,3,1}
 236 = {3,3,1,1}
 472 = {3,3,1,1,1}
 945 = {3,3,1,1,2}
 473 = {3,3,1,2}
 946 = {3,3,1,2,1}
1893 = {3,3,1,2,2}
 237 = {3,3,2}
 474 = {3,3,2,1}
 948 = {3,3,2,1,1}
1897 = {3,3,2,1,2}
 949 = {3,3,2,2}
1898 = {3,3,2,2,1}
3797 = {3,3,2,2,2}
  15 = {4}
  30 = {4,1}
  60 = {4,1,1}
 120 = {4,1,1,1}
 240 = {4,1,1,1,1}
 481 = {4,1,1,1,2}
 241 = {4,1,1,2}
 482 = {4,1,1,2,1}
 965 = {4,1,1,2,2}
 121 = {4,1,2}
 242 = {4,1,2,1}
 484 = {4,1,2,1,1}
 969 = {4,1,2,1,2}
 485 = {4,1,2,2}
 970 = {4,1,2,2,1}
1941 = {4,1,2,2,2}
  61 = {4,2}
 122 = {4,2,1}
 244 = {4,2,1,1}
 488 = {4,2,1,1,1}
 977 = {4,2,1,1,2}
 489 = {4,2,1,2}
 978 = {4,2,1,2,1}
1957 = {4,2,1,2,2}
 245 = {4,2,2}
 490 = {4,2,2,1}
 980 = {4,2,2,1,1}
1961 = {4,2,2,1,2}
 981 = {4,2,2,2}
1962 = {4,2,2,2,1}
3925 = {4,2,2,2,2}
 123 = {4,3}
 246 = {4,3,1}
 492 = {4,3,1,1}
 984 = {4,3,1,1,1}
1969 = {4,3,1,1,2}
 985 = {4,3,1,2}
1970 = {4,3,1,2,1}
3941 = {4,3,1,2,2}
 493 = {4,3,2}
 986 = {4,3,2,1}
1972 = {4,3,2,1,1}
3945 = {4,3,2,1,2}
1973 = {4,3,2,2}
3946 = {4,3,2,2,1}
7893 = {4,3,2,2,2}
end


#整列 #数列 #ナンバリング #C #プログラム #連分数 #二進数 #有限自然数列

この記事が気に入ったらサポートをしてみませんか？