扇階段数について
関連動画：電脳寺子屋 数学を学ぶシリーズ扇階段関数について：扇階段数とは / 1桁異なる差分の値 / 差分の値 / 数学的な定義 / 高速な計算式 金字塔数との関係 / 逆階段関数
扇階段関数のPythonのコード: for文を利用した実装 / 高速化した実装
扇数について 櫛数について 金字塔数について
関連動画
アンドールシステムサポートのYouTubeちゃんねるでは「扇数」を題材とし、組み込みの開発に役立つ解説を行っております。
電脳寺子屋 数学を学ぶ「扇数と再帰関数」扇関数を例に、再帰関数と組み込みにおけるスタック・メモリの影響について説明ます。
電脳寺子屋 数学を学ぶ「扇数とPython」- Pythonのすすめ扇関数をC言語で実装した例と、Pythonで実装した例を通して、C言語に馴染んでいる方向けに、C言語の記述例とPythonの記述例を比較する形で、 Pythonの文法や特長の一部を紹介させて頂きます。
扇階段数とは？
\(1, 12, 123, \ldots , 123456789\)のように、\(1\)桁の扇数から\(x\)桁の扇数までの順番に連続した値を、足し合わせて得られる値を、このページとアンドールシステムサポートのYouTubeちゃんねるでは、扇階段数と呼ぶ事にしました。
\(s = 1 + 11+ 111 + \cdots + 111\ldots1\)上記の式で求まる\(s\)を扇階段数と呼びます。
\(x\)桁のまでの扇数の合計で得られる階段数を求める関数を、扇階段関数 \(S(x)\)とした場合に、扇関数\(A(x)\)を利用すると下記の様に定義する事ができます。
\(S(x) = A(1) + A(2) + A(3) + \cdots + A(x)\)つまり、扇階段関数は一般項を扇数とする数列の総和と言えます。
総和の記法である、Σ(シグマ)を利用して、10進数のx桁の扇数を返す扇関数を記述すると下記式になります。
\(S(x, base = n)=\displaystyle \sum_{k=1}^{x}A(k)\)上記の総和の式の様に「\(x\)」個までの値を数える際に、一般的な数値の数え方では「1」をはじめの値としますが、
プログラムの世界では「0」をはじめの値として扱う事が多いです。この場合には、終わりに値は「\(x-1\)」となり、総和の式を「0」をはじめとして書き換えると下記の式となります。
総和の式をPythonで関数として記述すると下記の関数となります。
def S(x): s = 0 for k in range (0, x): s += A(k+1) return s
扇数を返す扇関数\(A(x)\)の実装コードについては、こちらのページをご参照ください。
上記の扇階段関数を利用して、引数を0から10桁までの扇関数を合計した値の変化を下記の表に示します。
| 扇階段関数と引数 | 10進数の扇数の値 | 引数は1から合計する連続した扇数の桁数 |
|---|---|---|
| \(S(0)\) | \(0\) | \(0\) |
| \(S(1)\) | \(1\) | \(1\) |
| \(S(2)\) | \(12\) | \(2\) |
| \(S(3)\) | \(123\) | \(3\) |
| \(S(4)\) | \(1234\) | \(4\) |
| \(S(5)\) | \(12345\) | \(5\) |
| \(S(6)\) | \(123456\) | \(6\) |
| \(S(7)\) | \(1234567\) | \(7\) |
| \(S(8)\) | \(12345678\) | \(8\) |
| \(S(9)\) | \(123456789\) | \(9\) |
| \(S(10)\) | \(1234567900\) | \(10\) |
10進数の扇階段数では、1桁から9桁の範囲まで、最上位の桁を１とし、桁が1つ減る度に、各桁に含まれる値が１つ増加するという規則正しい数値となります。
また、10桁を超えると、桁上りが生じる為この規則性は一部崩壊しますが、最下位の桁が、合計した桁数の最下位桁の値と一致するという規則性は常に守られます。
異なる桁の扇階段数どうしの引算の結果は特別な値となります。
例えば隣合う桁数の扇階段数の差分は扇数となります。
1桁値が異なる扇階段数どうしの値の差分で得られる値
\(x\)を整数とした場合、\(x > 0\) の条件で下記の式が成り立ちます。
\(S(x) – S(x – 1) = A(x)\)扇階段数の概念を利用すれば、下記の例のように、9桁までの扇数は、見た目が分かり易く、関数を一切使わずに、扇数の引算として、記述する事ができる事を意味しています。
\(S(1) – S(0) = 1 – 0 = 1 = A(1)\)\(S(2) – S(1) = 12 – 1 = 11 = A(2)\)
\(S(3) – S(2) = 123 – 12 = 111 = A(3)\)
\(S(4) – S(3) = 1234 – 123 = 1111 = A(4)\)
\(S(5) – S(4) = 12345 – 1234 = 11111 = A(5)\)
\(S(6) – S(5) = 123456 – 12345 = 111111 = A(6)\)
\(S(7) – S(6) = 1234567 – 123456 = 1111111 = A(7)\)
\(S(8) – S(7) = 12345678 – 1234567 = 11111111 = A(8)\)
\(S(9) – S(8) = 123456789 – 12345678 = 111111111 = A(9)\)
補足：Pythonのバージョン3.6以上であれば、下記の例のように数値の間にアンダースコア(_)を入れて分かり易く数値を表記できるようになりました。
>>> 111_111_111 111111111
桁数が異なる扇階段数どうしの値の差分で得られる値
\(x\)と\(d\)を整数とした場合、\(x \geqq d \geqq 0\) の条件で下記の式が成り立ちます。
\(S(x) – S(d) = S(x – d) \times 10^d + A(d) \times (x – d)\)実際に計算した例はこちら
例1:
\(S(9) – S(1) = S(9 – 1) \times 10^1 + A(1) \times (9 – 1)\)\(S(9) – S(1) = S(8) \times 10^1 + A(1) \times 8\)
\(123456789 – 1 = 12345678 \times 10^1 + 1 \times 8\)
\(123456788 = 123456780 + 8\)
例2:
\(S(9) – S(2) = S(9 – 2) \times 10^2 + A(2) \times (9 – 2)\)\(S(9) – S(2) = S(7) \times 10^2 + A(2) \times 7\)
\(123456789 – 12 = 1234567 \times 10^2 + 11 \times 7\)
\(123456777 = 123456700 + 77\)
例3:
\(S(9) – S(3) = S(9 – 3) \times 10^3 + A(3) \times (9 – 3)\)\(S(9) – S(3) = S(6) \times 10^3 + A(3) \times 6\)
\(123456789 – 123 = 123456 \times 10^3 + 111 \times 6\)
\(123456666 = 123456000 + 666\)
例4:
\(S(9) – S(4) = S(9 – 4) \times 10^4 + A(4) \times (9 – 4)\)\(S(9) – S(4) = S(5) \times 10^4 + A(4) \times 5\)
\(123456789 – 1234 = 12345 \times 10^4 + 1111 \times 5\)
\(123456789 – 1234 = 12345 \times 10^4 + 1111 \times 5\)
\(123455555 = 123450000 + 5555\)
例5:
\(S(9) – S(5) = S(9 – 5) \times 10^5 + A(5) \times (9 – 5)\)\(S(9) – S(5) = S(4) \times 10^5 + A(5) \times 4\)
\(123456789 – 12345 = 1234 \times 10^5 + 11111 \times 4\)
\(123444444 = 123400000 + 44444\)
例6:
\(S(9) – S(6) = S(9 – 6) \times 10^6 + A(6) \times (9 – 6)\)\(S(9) – S(6) = S(3) \times 10^6 + A(6) \times 3\)
\(123456789 – 123456 = 123 \times 10^6 + 111111 \times 3\)
\(123333333 = 123000000 + 333333\)
例7:
\(S(9) – S(7) = S(9 – 7) \times 10^7 + A(7) \times (9 – 7)\)\(S(9) – S(7) = S(2) \times 10^7 + A(7) \times 2\)
\(123456789 – 1234567 = 12 \times 10^7 + 1111111 \times 2\)
\(122222222 = 120000000 + 2222222\)
例8:
\(S(9) – S(8) = S(9 – 8) \times 10^8 + A(8) \times (9 – 8)\)\(S(9) – S(8) = S(1) \times 10^8 + A(8) \times 1\)
\(123456789 – 12345678 = 1 \times 10^8 + 11111111 \times 1\)
\(111111111 = 100000000 + 11111111\)
この他にも金字塔数になる式もあります。金字塔数は、この後の方で紹介します。
n進数の扇階段数の数学的な定義
扇階段数も、扇数と同様に、\(n\)進数に拡張して考える事ができます。
\(n\)進数の\(x\)桁のまでの扇数の合計で得られる階段数を求める関数を、扇階段関数 \(S(x, base = n)\)とした場合に、扇関数\(A(x, base = n)\)を利用すると下記の様に定義する事ができます。
\(S(x, base = n) = A(1, n) + A(2, n) + A(3, n) + \cdots + A(x, n)\)つまり、扇階段関数は一般項を扇数とする数列の総和と言えます。
総和の記法である、Σ(シグマ)を利用して、10進数のx桁の扇数を返す扇関数を記述すると下記式になります。
\(S(x, base = n)=\displaystyle \sum_{k=1}^{x}A(k, n)\)上記の総和の式の様に「x」個までの値を数える際に、一般的な数値の数え方では「1」をはじめの値としますが、
プログラムの世界では「0」をはじめの値として扱う事が多いです。この場合には、終わりに値は「x-1」となり、総和の式を「0」をはじめとして書き換えると下記の式となります。
n進数の扇階段数を返すPythonのコード
総和の式をPythonで関数として記述すると下記の関数となります。
def S(x, base = 10): s = 0 for k in range (0, x): s += A(k+1, base) return s
上記のコードは、for文を利用した繰り返しとなる為、桁数が大きくなるほど、処理時間が大きくなります。
n進数の扇階段数の総和を高速に求めるための式
扇数で等比数列の和の公式を利用する事で、for文を無くし、高速化できたように、扇階段数の値を求める事が可能な、より高速な計算式を下記に示します。
\(S(x, base = n)=\displaystyle \sum_{k=0}^{x-1}A(k+1, n) = \displaystyle \frac{n \times A(x , n) – x}{n – 1} = \displaystyle \frac{n^{x + 1}-n-(x \times (n – 1))}{(n – 1)^2}\)上記の式が成り立つことの証明はこちら
扇階段関数の式を次のように変形します。
\(S(x, base = n) = \displaystyle \frac{n \times A(x , n) – x}{n – 1}\)下記の式が求まります。
\(S(x + 1, base = n) = \displaystyle \frac{n \times A(x + 1 , n) – (x + 1)}{n – 1}\)扇関数の式を次のように変形します。
\(A(x, base = n) = \displaystyle \frac{n^x – 1}{n – 1}\)下記の式が求まります。
\(A(x + 1, base = n) = \displaystyle \frac{n^{x+1} – 1}{n – 1}\)次に、1桁値が異なる扇階段数どうしの値の差分で得られる値が、扇関数の値になる性質を利用します。
\(S(x + 1, base = n) – S(x, base = n) = A(x + 1, base = n)\)上記の式に扇階段関数の式を代入します。
\(\displaystyle \frac{n \times A(x + 1, n) – (x + 1)}{n – 1} – \displaystyle \frac{n \times A(x, n) – x}{n – 1} = \frac{n^{x + 1} – 1}{n – 1}\)この式を、次のように変形します。
\(n \times A(x + 1, n) – (x + 1) – n \times A(x, n) + x = n^{x + 1} – 1\)\(n \times A(x + 1, n) – x – 1 – n \times A(x, n) + x = n^{x + 1} – 1\)
\(n \times A(x + 1, n) – n \times A(x, n)= n^{x + 1}\)
\(n \times (A(x + 1, n) – A(x, n)) = n^{x + 1}\)
この式に扇関数の式を代入します。
\(n \times \left(\displaystyle \frac {n^{x + 1} – 1}{n – 1} – \displaystyle \frac {n^x – 1}{n – 1}\right) = n^{x + 1}\)\(n \times \left(\displaystyle \frac {n^{x + 1} – 1}{n – 1} – \displaystyle \frac {n^x – 1}{n – 1}\right) = \displaystyle \frac{(n – 1) \times n^{x + 1}}{n – 1}\)
\(\displaystyle \frac{n}{n -1} \times ((n^{x + 1} – 1) – (n^x – 1))= \displaystyle \frac{(n – 1) \times n^{x + 1}}{n – 1}\)
\(n \times ((n^{x + 1} – 1) – (n^x – 1))= (n – 1) \times n^{x + 1}\)
\(n \times (n^{x + 1} – 1 – n^x + 1)= (n – 1) \times n^{x + 1}\)
\(n \times (n^{x + 1} – n^x)= (n – 1) \times n^{x + 1}\)
\(n^{x + 2} – n^{x + 1} = n^{x + 2} – n^{x + 1}\)
上記の式が成り立つ事から、扇階段関数のより高速な計算式が正しい言えます。
n進数の扇階段関数のPythonの高速化コード
上記の式をもとに扇関数を利用して高速化したPythonの扇階段関数のコードを下記に示します。
def S(x, base = 10): return ((base * A(x, base)) -x) // (base - 1)
扇関数に対して等比数列の総和の公式を適用し展開した扇階段関数のPythonの高速化コードを下記に示します。
def S(x, base = 10): return (base**(x+1)-base-(x*(base-1))) // ((base-1)**2)
扇数を返す扇関数\(A(x)\)の実装コードについては、こちらのページの中にある、等比数列の総和を公式を利用した実装を利用すると、for文を完全に排除できるので、非常に高速なコードとなります。
扇階段数と金字塔数の関係
扇階段数どうしの引算は特定の組み合わせは、扇数の自乗である金字塔数となります。
\(x\)を整数とした場合、\(x \geqq 0\) の条件で下記の式が成り立ちます。
\(S( (x \times 2) + 1) – 2 \times S(x) = A(x + 1)^2 = P(x + 1)\)この式が成り立つ事は、数値の各桁毎の値を長さとして捉え、図形として考えると、分かると思います。
実際に計算した例はこちら
\(x = 0\)の場合：
\(S( (0 \times 2) + 1) – 2 \times S(0) = A(0 + 1)^2 = P(0 + 1)\)
\(S(1) – 2 \times S(0) = A(1)^2 = P(1)\)
\(1 – 2 \times 0 = 1^2 = 1\)
\(x = 1\)の場合：
\(S( (1 \times 2) + 1) – 2 \times S(1) = A(1 + 1)^2 = P(1 + 1)\)
\(S(3) – 2 \times S(1) = A(2)^2 = P(2)\)
\(123 – 2 \times 1 = 11^2 = 121\)
\(123 – 2 = 11^2 = 121\)
\(x = 2\)の場合：
\(S( (2 \times 2) + 1) – 2 \times S(2) = A(2 + 1)^2 = P(2 + 1)\)
\(S(5) – 2 \times S(2) = A(3)^2 = P(3)\)
\(12345 – 2 \times 12 = 111^2 = 12321\)
\(12345 – 24 = 111^2 = 12321\)
\(x = 3\)の場合：
\(S( (3 \times 2) + 1) – 2 \times S(3) = A(3 + 1)^2 = P(3 + 1)\)
\(S(7) – 2 \times S(3) = A(4)^2 = P(4)\)
\(1234567 – 2 \times 123 = 1111^2 = 1234321\)
\(1234567 – 246 = 1111^2 = 1234321\)
\(x = 4\)の場合：
\(S( (4 \times 2) + 1) – 2 \times S(4) = A(4 + 1)^2 = P(4 + 1)\)
\(S(9) – 2 \times S(4) = A(5)^2 = P(5)\)
\(123456789 – 2 \times 1234 = 11111^2 = 123454321\)
\(123456789 – 2468 = 11111^2 = 123454321\)
\(x = 5\)の場合：
\(S( (5 \times 2) + 1) – 2 \times S(5) = A(5 + 1)^2 = P(5 + 1)\)
\(S(11) – 2 \times S(5) = A(6)^2 = P(6)\)
\(12345679011 – 2 \times 12345 = 111111^2 = 12345654321\)
\(12345679011 – 24690 = 11111^2 = 12345654321\)
逆扇階段数
扇階段数の最上位から最下位までの桁値を入れ替えた値を逆扇階段数と呼ぶ事にします。
\(x\)桁の逆扇階段数を返す関数\(R(x)\)を逆扇階段関数と呼ぶ事とした場合、 10進数の場合は、0～9桁までの範囲で、下記の式が成り立ちます。
\(R(x) = (x + 1) \times A(x) – S(x)\)n進数で考えた場合は下記の式となります。
\(R(x, base = n) = (x + 1) \times A(x, n) – S(x, n)\)n進数対応の逆扇階段数を返すPythonのコードの実装例
def R(x, base = 10): return (x + 1) * A(x, base) - S(x, base)
n進数の場合は、n-1桁まで、上記のコードで値を求める事ができます。また、n桁を超えた場合は一致しなくなります。
扇数を小数点方向に拡張した降下扇数を利用して、階段数を実装したものを考えた場合に、n進数の降下扇階段数は、n-1桁まで、下位の桁に向かって値が延びていくため、上位桁に含まれる値が次々と増加する数となります。逆扇階段関数は降下扇階段数が返す値を検証する上でも役立つ概念になると考えられます。そのため、この概念は、浮動小数点で計算された関数の値を検証するために役立つ概念であるとも考えられます。
逆扇階段数の計算例
\(R(2) = (2 + 1) \times A(2) – S(2) = 3 \times 11 – 12 = 21\)
\(R(3) = (3 + 1) \times A(3) – S(3) = 4 \times 111 – 123 = 321\)
\(R(4) = (4 + 1) \times A(4) – S(4) = 5 \times 1111 – 1234 = 4321\)
\(R(5) = (5 + 1) \times A(5) – S(5) = 6 \times 11111 – 12345 = 54321\)
\(R(6) = (6 + 1) \times A(6) – S(6) = 7 \times 111111 – 123456 = 654321\)
\(R(7) = (7 + 1) \times A(7) – S(7) = 8 \times 1111111 – 1234567 = 7654321\)
\(R(8) = (8 + 1) \times A(8) – S(8) = 9 \times 11111111 – 12345678 = 87654321\)
\(R(9) = (9 + 1) \times A(9) – S(9) = 10 \times 111111111 – 123456789 = 987654321\)
\(x \geqq 0\)、つまりxが0以上の整数の場合に下記の式が成り立ちます。
\(R(x + 1) – R(x) = (x + 1) \times 10 ^x\)n進数の場合は下記の式が成り立ちます。
\(R(x + 1, base = n) – R(x, base = n) = (x + 1) \times n ^x\)
