人生reject

思いついたことをなんとなく書く

『Golomb数列』について

Golomb sequenceとは、『ソロモン・ゴロム』によって定義された数列で、以下のような数列である。
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, \cdots

定義

\{a_{n}\}は増加列であるとする。
以下のように定義される。
a_{1}=1とする。
a_{2}>a_{1}よりa_{2}=2とする。
2に対してa_{2}=2であるから、2を2回連続させる(a_{2}=a_{3}=2とする)。
3に対してa_{3}=2であるから、3を2回連続させる(a_{4}=a_{5}=3とする)。
4に対してa_{4}=3であるから、4を3回連続させる(a_{6}=a_{7}=a_{8}=4とする)。
一般のnに対してa_{n}=mのとき、nm回連続させる。(a_{k}=\cdots = a_{k+m}=n)。

漸化式

この数列は漸化式で

\left\{
\begin{array}{l}
a(1)=1 \\
a(n+1)=1+a(n+1-a((n)))
\end{array}
\right.
と表すことができる。