みけCATのにっき（仮）
つれづれなるまゝに、日くらし、PCにむかひて、心に移りゆくよしなし事を、そこはかとなく書きつくれば、あやしうこそものぐるほしけれ。
（本当か！？）
出典

「数探し」とコラッツ予想

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

「数探し」とコラッツ予想

投稿記事 by みけCAT » 9年前

数探し(WebArchive)というゲームがあります。

そのルールは単純。
数探し さんが書きました:1、偶数なら２で割る
2、奇数なら３倍して１を足す

これを繰り返して●を691コ以上つぶしてください。
一見、コラッツ予想の計算かな？と思いますが、実はそんなに単純ではありません。
まず、「●を691コ以上つぶしてください」と書いてありますが、●がつぶれる条件が明記されていません。すなわち、「未定義」です。

とりあえずやってみましょう。
まずは適当に、「3」を入力すると、「●は7コつぶれました。」と出ました。
「65537」を入力すると、「●は99コつぶれました。」と出ました。
ということは、「(つぶれる●の数)=(コラッツ予想の計算の反復回数)」と予想できます。

しかし、予想はあくまでも予想です。
試しに「96883183」と入力してみます。
すると、コラッツ予想の計算の反復回数は810なのに、なんと「●は748コつぶれました。」と出ました。予想はハズレです。
kazusagasi_test.png
適当な数を入力してみる
kazusagasi_test.png (56.1 KiB) 閲覧数: 362 回
ところで、この「数探し」のページには、
「数発見者ＴＯＰ５！」(WebArchive)というページと、
「数発見者！」(WebArchive)というページがあり、
それぞれ●がつぶれた個数の多い順と数の小さい順であると予想できます。
では、本当かどうか検証してみましょう。

CODE: 

数              | 数探しで●がつぶれた個数 | コラッツ予想の反復回数 | 出典
----------------+--------------------------+------------------------+---------------------
456516565122594 |                      748 |                    827 |
456516565122595 |                      748 |                    827 |
456516565122584 |                      748 |                    827 | 数発見者ＴＯＰ５！
276749658141367 |                      697 |                    697 |
934030096227116 |                      691 |                    691 |
----------------+--------------------------+------------------------+---------------------
        3732423 |                      596 |                    596 |
        5649499 |                      612 |                    612 |
        8397953 |                      592 |                    592 |
       10011263 |                      618 |                    618 |
       11197270 |                      595 |                    595 |
 45651656512259 |                      635 |                    635 | 数発見者！
456516565122595 |                      748 |                    827 |
456516565122594 |                      748 |                    827 |
601787017641345 |                      662 |                    662 |
197021973422908 |                      681 |                    681 |
276749658141367 |                      697 |                    697 |
934030096227116 |                      691 |                    691 |
どうやら、先ほどの実験で「96883183」を入力した時に●が748コしか潰れなかったのは、
単にカンストだったようです。(なぜこのような一見中途半端な数値でカンストなのかはわかりませんが)
しかし、新たな不自然な点が出てきました。
「数発見者！」のページに載っている数字のほとんどが、●を(一般的な意味で)691コ以上潰していないのに、
このページに登録されている点です。
さらに、例えば●を596コつぶす数字を入力してもダイアログは出ませんでしたが、
●を681コつぶす数字を入力すると、「●が691コ以上つぶれました！」というダイアログが出てきました。
表に載っている数字だからかと思い、表に載っていない「18901151」を入力してみたところ、やはりダイアログが出てきました。
kazusagasi_giwaku.png
疑惑の判定
kazusagasi_giwaku.png (43.38 KiB) 閲覧数: 357 回
●を691コつぶす「14934241」を入力してもダイアログが出て、
それぞれ671、661、651、641、631、621、611、601コつぶす
23456487、29921758、37869727、48562939、58237599、13002751、16497899、19906257を入力してもダイアログが出なかったので、
おとぎの国の高橋君の要領で数字の大小関係が入れ替わっている、ということもなさそうです。

もう少し検証してみましょう。
試しに「1234567890123456」と入力してみると「15桁以内にしてください」と怒られてしまったので、
言われた通りに15桁の「999999999999999」を入力します。
すると、なんと●は399コしかつぶれませんでした！この数に対するコラッツ予想の計算の反復回数は567です。
kazusagasi_not_collatz.png
いつから単純なコラッツ予想の計算だと錯覚していた…
kazusagasi_not_collatz.png (19.09 KiB) 閲覧数: 357 回
やはり、カンストとは別に、「(●がつぶれる数)＝(コラッツ予想の計算の反復回数)」という予想は誤りだったことがわかりました。

[hr]
今回検証用の数を求めたプログラム

CODE: 

#include 
#include 

const int CC_MAX = 99999999;
const int OUTPUT_MAX = 100000;

int cc(long long n) {
	int count = 0;
	while (n > 1) {
		n = (n % 2 == 1 ? n * 3 + 1 : n / 2);
		count++;
	}
	return count;
}

struct cc_t {
	int n, count;
	// countの降順、nの昇順で並べ替える用
	bool operator cct.count;
	}
};

int main(void) {
	static cc_t cc_list[CC_MAX];
	#ifdef _OPENMP
	#pragma omp parallel for schedule(dynamic)
	#endif
	for (int i = 0; i < CC_MAX; i++) {
		cc_list[i].n = i + 1;
		cc_list[i].count = cc(i + 1);
	}
	std::sort(cc_list, cc_list + CC_MAX);
	puts("#   rank        n count");
	for (int i = 0; i < OUTPUT_MAX && i < CC_MAX; i++) {
		printf("%8d %8d %5d\n", i + 1, cc_list[i].n, cc_list[i].count);
	}
	if (OUTPUT_MAX < CC_MAX) {
		if (OUTPUT_MAX * 2 < CC_MAX) {
			putchar('\n');
			for (int i = CC_MAX - OUTPUT_MAX; i < CC_MAX; i++) {
				printf("%8d %8d %5d\n", i + 1, cc_list[i].n, cc_list[i].count);
			}
		} else {
			for (int i = OUTPUT_MAX; i < CC_MAX; i++) {
				printf("%8d %8d %5d\n", i + 1, cc_list[i].n, cc_list[i].count);
			}
		}
	}
	return 0;
}
実行結果

[hr]
今回検証に使用した環境

Windows Vista Home Premium SP2 32ビット
Intel(R) Core(TM)2Duo T8100 @2.10GHz 2.10GHz
RAM 4.00GB
Firefox 31.0
ページトップ
コメントはまだありません。