等差数列に関わる問題。

1. 問題文
長さp (3<=p<=30内の素数)の等差数列にならない最小数列(細かい定義は元問題文を参照)に対し、そのn (1<=n<=20000000000) 番目の項を示せ。

2. 実例
p=3の時の最小数列は 1,2,4,5,10,11,13,14,28,29,… になっている。数列のどの3項を取ってきても等差数列にならない。

しかし、たとえば、1,2,4,5,9,10,… という数列ではダメだ。1,5,9が等差数列になってしまうから。

3. 解き方
ブログ内の昔の記事にも書いたが、数列を扱う問題では、オンライン整数列大辞典が大いに参考になる。

本問題に関しても、1,2,4,5,10,11と数列を打ち込むと直ちに ID: A003278が表示される。COMMENTを読み、とくにFORMULAを注意深く観察すると、それらしき計算式が表示されていることが多い。今回も

a(n) = b(n+1) with b(0)=1, b(2n)=3b(n)-2, b(2n+1)=3b(n)-1

という一行が役に立ちそう。

数式に沿ってプログラムを組み、最初に数項が正しく計算されることを確認し、3以外の素数への拡張を推測していく。省略するが、最終的に以下の通り計算を行う。

int p;  /* 問題文の素数 */
long long calc(long long n)
{
    if (n == 0) return 1;
    return p*calc(n/(p-1)) + n%(p-1) - (p-1);
}

上の関数を calc(n-1) で呼び出す。nの値の対数回計算で結果が出る。

問題文を楽しむなら、ここで紹介したやり方ではいけないが、自分で同じ数式を探し当てることができるなら素晴らしいけど、無駄なことをやらなくてもいいじゃないかな。

Comments are closed.

Post Navigation