櫛数について

櫛数について

櫛数とは？

櫛は、髪を梳かすための道具として、等間隔に設けられた複数の歯が付いた道具です。
数値の各桁の値を数列と見なし、「1」を櫛の歯、「0」を隙間と見なす、「1」と「0」だけの値からなる数値を櫛数と呼ぶ事にしました。

例えば、櫛歯の本数が4本、隙間を1本とした場合の櫛数は「1010101」となり、 歯の本数が4本、隙間を2本とした場合の櫛数は「1001001001」となり、 歯の本数が4本、隙間を3本とした場合の櫛数は「1000100010001」となります。
また、隙間の数を0本とした場合は、「1111」となり扇数そのものになります。

櫛関数の数式

櫛の歯の本数を\(x\),　歯の隙間の本数を\(s\)とした櫛数を返す関数\(C(x, s)\)を櫛関数と呼ぶ事とします。

櫛関数をシグマ(シグマ)総和の記号を利用して記述すると以下の式となります。

櫛関数をPythonで記述した例

def C(x , s = 0):
	y = 0
	for k in range(0, x):
		y += 10**(k * (s + 1))
	return y

櫛関数の返す値の例

後で、解説しますが、櫛数はものの見方次第(観測者がどの進数として、その数値を観測するのかの違い)で、扇数そのものと言う事もできます。

n進数の櫛関数の数式

\(n\)進数の櫛の歯の本数を\(x\),　歯の隙間の本数を\(s\)とした櫛数を返す関数\(C(x, s, base = n)\)を櫛関数と呼ぶ事とします。

\(n\)進数の櫛関数をシグマ(シグマ)総和の記号を利用して記述すると以下の式となります。

n進数の櫛関数をPythonで記述した例

n進数の櫛関数をPythonの関数として記述した例を下記に示します。

def C(x , s = 0, base = 10):
	y = 0
	for k in range(0, x):
		y += base**(k * (s + 1))
	return y

櫛数の概念の応用について

2進数の櫛数の概念を利用する事で、LEDの点灯検査パターンなどの、規則性のある検査パターンを数学的に作る事ができます。
櫛数で扱う概念は、扇数、扇階段数、金字塔数にもそのまま応用する事ができるので、この考え方を適用する事で、より桁数の大きなテストパターンの数値を簡単に作る事ができるようになります。

扇数とは？

def A(x, base = 10):
   s = 0
   for k in range (0, x):
       s += base**k
   return s

扇数の関連動画

アンドールシステムサポートのYouTubeちゃんねるでは「扇数」を題材とし、組み込みの開発に役立つ解説を行っております。

扇関数を例に、再帰関数と組み込みにおけるスタック・メモリの影響について説明ます。

扇関数をC言語で実装した例と、Pythonで実装した例を通して、C言語に馴染んでいる方向けに、C言語の記述例とPythonの記述例を比較する形で、 Pythonの文法や特長の一部を紹介させて頂きます。

櫛数と扇数の関係

櫛数とは、nのm乗進数の扇数を、n進数から観測して見える数である言う事もできます。

前提知識として、観測者がその数値をどの進数で観測しているのかによって、その数値の見え方は変化します。
Pythonでは、変数xに対し、str(x)で10進数、bin(x)で2進数、oct(x)で8進数、hex(x)で16進数の文字列に変換する事ができます。
下記に、10進数で0から17までの値をそれぞれの進数として観測した場合にどの様に見えるのかを表に示します。

この表では、扇数となっている部分の数値を強調しています。

0と1は、どの進数で観測しても、同じように見えますが、10進数で2以上の値は、2進数からは別の値として観測されます。
10進数で、7までの値は、8進数と16進数でも同じ値として観測されます。
10進数で、9までの値は、10進数と16進数でも同じ値として観測されます。

10進数で9は、8進数で2桁の扇数であり、2進数として観測した場合は、櫛数となり、歯の本数は2本、歯の隙間の間隔が2本分となります。

10進数で17は、16進数で2桁の扇数であり、2進数として観測した場合は、櫛数となり、歯の本数は2本、歯の隙間の間隔が3本分となります。

更に、扇数(櫛数)に基数の累乗を掛けた値となている数も強調した表を下記に示します。

扇数どうしの除算と櫛数の関係

n進数の扇数どうしは、桁数が割り切れる値どうしであれば、割り切るとができます。
扇数を扇数で割り切って得られる値は、櫛数となります。

桁数が割り切れる値の扇数で、扇数を割る事で櫛の歯のように 1と0の値の組み合わせの値を得る事ができます。
このページやアンドールのYouTubeちゃんねるの中では、下記の計算式で得れる値\(c\)を櫛数と呼ぶ事にしました。

\(A(x \times d, base = n) \div A(d, base = n) = c\)

扇数を扇数をで割る事は、扇数の桁数どうしの割算となり、進数の変換が発生します。

櫛数になる扇数どうしの割算の例 :

このことは、観測者がその値を10進数として観測する場合、100進数で1桁の値は、10進数上では2桁で1組の値となります。
同様に、1000進数で1桁の値は、10進数上では3桁で1組の値、 10000進数で1桁の値は、10進数上では4桁で1組の値になります。

\(c = A(x, base = n^d)\)

櫛数と扇数の対応の例

\(1010101 = A(4, 10^2) = C(4, 1, 10)\)
櫛歯の本数が4本、櫛歯の隙間が1本の櫛数は、100進数上で4桁の扇数を10進数として観測した値と言えます。

\(10001 = A(2, 10^4) = C(2, 3, 10)\)
櫛歯の本数が2本、櫛歯の隙間が3本の櫛数は、1000進数上で2桁の扇数を10進数として観測した値と言えます。

櫛関数と扇関数の関係についてのまとめ

上記では、扇数の割算から櫛数の関係を見てみました。
次に、櫛数の値を返す櫛関数から扇数の値を返す扇関数の関係を見てみましょう。

xが0以上の整数、sが0以上の整数、nが2以上の整数の場合、
つまり、 \( x \geqq 0, s \geqq 0, n \geqq 2 \)の場合に下記の式が成り立ちます。

\(C(x, s, base = n)\) \(=A(x \times d, base = n) \div A(d, base = n)\) \(= A(x, base = n^d)\)
上記の式に\(d = s + 1\)を代入すると下記の式になります。
\( C(x, s, base = n) = A(x \times (s + 1), base =n) \div A(s + 1, base = n ) = A(x, base = n^{s + 1}) \)
つまり下記の式が成り立ちます。
\( C(x, s, base = n) = A(x, base = n^{s + 1}) \)

櫛関数の応用