C：4桁のカプレカ数を再現してみる

カプレカ数というのをご存じですか？
わたしはつい最近まで知りませんでした（笑）数学に疎いもので．．．

カプレカ数の定義は2つあります。

カプレカ数（カプレカすう、Kaprekar Number）とは、次のいずれかで定義される整数である。
１．2乗して前の部分と後ろの部分に分けて和を取ったとき、元の値に等しくなるもの。
２．桁を並べ替えて最大にしたものから最小にしたものの差を取ったとき、元の値に等しくなるもの。
名前はインドの数学者D. R. カプレカにちなむ。

Wikipediaより引用 – カプレカ数

カプレカ数は、上記の定義2の方が有名です。

カプレカ数について
処理の流れ
C言語で作ってみる
ソースコード全体
1. 実行イメージ

カプレカ数について

カプレカ数を例としてあげると…

最初の数が、4019だったとします。

この4つの数字を並べ替えて最大値と最小値を作ります。

最大値 9410
最小値 0149（この場合先頭が0なので149とします）

最大値から最小値を引きます。

9410 – 149 = 9261

計算で出た9261を再度元の値として、同じように最大値、最小値に分け計算をしていきます。

【2回目】
9621 – 1269 = 8352

【3回目】
8532 – 2358 = 6174

【4回目】
7641 – 1467 = 6174

【5回目】
7641 – 1467 = 6174
：
：

おやおや？
何か気づきませんか？

このまま6174が続いていきますね。
これがカプレカ数です。（わたしも最近知ったので偉そうに言えないですが．．．）
4桁は必ずこの6174に収束するのです。（ちなみに3桁だと495となる）

処理の流れ

次のような流れで考えました。

1.乱数で適当な4つ数値を生成
2.生成した4つの数値から最大値と最小値を求める
3.最大値－最小値を求める
4.3で求めた数値を使って再度最大値と最小値を求める
5.3と4を「6174」が2回連続して再現されるまで繰り返す

C言語で作ってみる

以上の流れをC言語に直すとそれぞれこうなります。

乱数で適当な4つ数値を生成

/* 4桁の適当な数を生成 */
len = MAX;
for(i=0; i<len; i++){
	r[i] = rand() % 10 + 48;	/* '0'~'9'の文字として代入 */
}
r[len] = '\0';	/* 生成した数値文字列の最後尾にヌル文字代入 */

ポイントは、rand() % 10 として0から9の乱数を発生させるのではなく、rand() % 10 + 48 として48を足すことでASCIIコード文字として数値文字を保存している点です。
その方が最大値と最小値への数値並べ替えがしやすいと考えました。（もっといい方法があれば知りたいです）

生成した4つの数値から最大値と最小値を求める

/* 最大値と最小値の数値組み合わせを決定(昇順と降順に並べ替え） */
for(i=0; i<len-1; i++){
	for(j=i+1; j<len; j++){
		if(max[i] < max[j]){	/* max: 降順に並べ替え */
			work = max[i];
			max[i] = max[j];
			max[j] = work;
		}
		if(min[i] > min[j]){	/* min: 昇順に並べ替え */
			work = min[i];
			min[i] = min[j];
			min[j] = work;
		}
	}
}

隣り合う配列の数値文字を比較して降順（最大値用）と昇順（最小値用）に並べ替えています。
バブルソートというアルゴリズムです。

最大値－最小値を求める

まずは文字配列だった数値をatoi関数で整数に直して

iMax = atoi(max);
iMin = atoi(min);

最大値－最小値を求めます。

		
kaprekar = iMax - iMin;

求めた数値を使って再度最大値と最小値を求める

あとは1回目に求めた数値を元に、2～3の繰り返しです。
最大値と最小値に再度数値並べ替えをするために、一旦数値化した数を数値文字に直しておきます。

sprintf(r, "%d", kaprekar);

「6174」が2回連続して再現されるまで繰り返す

前回の計算結果をsaveKaprekarという変数に保存しておき、同じだったら計算ループを抜けています。
変数saveKaprekar初期値の-1は適当な数です。

int saveKaprekar = -1;

while(1){
		:
		:

	/* 終了判定 */
	if(saveKaprekar == kaprekar) break;	/* 同じ値が2回続けばカプレカ数なのでループ終了 */
	
	/* 1つ前の計算状態を保存しておく */
	saveKaprekar = kaprekar;
		:

}