等差数列に関わる問題。

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の値の対数回計算で結果が出る。

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

優先度付きキューとは,キュー (Queue) からデータを取り出す順は,FIFO (First In First Out) というルールに従うのではなく,データの大きい順(または小さい順)に従う,というデータ構造.

例えば、優先度付きキューに、 10, -2, 5, 1 という4つのデータが格納されているとする。小さい値が優先だとすれば、4つのデータの取り出される順は、-2, 1, 5, 10 になる。

以下の実装法は,15パズルを解くために用意したもの.恐らく,もっとも短い実装法のひとつだと思う.
MIN-Priority-queue (小さい順優先).

サポートする操作は2種類のみ.
 void enq(QUE *q)  データをキューに格納(挿入)する操作
 int deq(QUE *q)  最小値のデータをキューから取り出す操作(成功時はリターン値が 1.失敗時は 0)

(下のソースプログラムのテキスト版は こちら

#include <stdio.h>
#include <string.h>
#define QSIZE 10000 /* Queue size */
int qsize; typedef struct { int key; int xx; /* ...... */ } QUE; QUE que[QSIZE+1];
#define PARENT(i) ((i)>>1) #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1)+1)
void init(void) { qsize = 0; }
static void min_heapify(int i) { int l, r; int smallest;
l = LEFT(i), r = RIGHT(i); if (l < qsize && que[l].key < que[i].key) smallest = l; else smallest = i; if (r < qsize && que[r].key < que[smallest].key) smallest = r; if (smallest != i) { QUE t = que[i]; que[i] = que[smallest]; que[smallest] = t; min_heapify(smallest); } }
int deq(QUE *q) { if (qsize == 0) return 0; memcpy(q, &que[0], sizeof(QUE)); que[0] = que[--qsize]; min_heapify(0); return 1; }
void enq(QUE *q) { int i, ii;
i = qsize++; memcpy(&que[i], q, sizeof(QUE)); while (i > 0 && que[ii = PARENT(i)].key > que[i].key) { QUE t = que[i]; que[i] = que[ii]; que[ii] = t; i = ii; } }
int main(void) { int i; QUE q;
init();
for (i = 10; i >= -5; i--) { q.key = i; enq(&q); }
while (deq(&q)) printf("-677368720 ", q.key); printf("\n"); return 0; }

最後のmain() 関数部分では,テストも兼ねて,キューの使い方を説明している.10 から ー5 までの順で整数をキューに挿入したのに対し,取り出した順は -5 から 10 となっている.

ご利用の際に,キューの大きさ(QSIZE) や,キューの構造体(QUE)を適宜変更してください.

なお,最大値優先キュー MAX-Priority-queue (大きい順優先)の実装プログラムは こちら にあり,上のMIN-Priority-queue とは,本質的に,値比較のための不等号向き3つが異なるだけだ.