PHP
アルゴリズム
競技プログラミング

プログラマ脳を鍛える数学パズル Q.6「(改造版)コラッツの予想」

More than 1 year has passed since last update.

引き続き問題を解いていきます。

問題はプログラマ脳を鍛える数学パズルより。


今回の問題


数学の未解決問題の1つに「コラッツの予想」があります。

コラッツの予想


自然数nについて

・nが偶数の場合、nを2で割る

・nが奇数の場合、nに3をかけて1を足す

という操作を繰り返すとき、初期値がどんな数があっても必ず1に到達する(1→4→2→1のように繰り返す)


この予想の内容を少し変えて、初期値が偶数の場合、初回のみnに3をかけて1を足すことから始めることとし、「最初の数」に戻るものを考えます。

例えば、2で始めた場合は以下のようになります。

2→7→22→11→(中略)→2

同様に、4で始めると以下のようになります。

4→13→(中略)→4

しかし、6で始めると

6→(中略)→

となり、6に戻ってくることはありません。

問題

10000以下の偶数のうち、上記の2や4のような「最初の数に戻る数」がいくつあるか、その個数を求めてください。



実装手順

①2から10000までの偶数をループさせて初期値(最初の数)を設定する

②初期値に3をかけて1を足す

③上記で設定した値が初期値に戻るか、1になるまでループさせる

④上記のループ文の中で値が偶数、奇数の場合で処理を分ける

⑤値が初期値と一致した回数を数える

⑥出力する


書いたPHPコードと出力結果


q06.php

<?php

// 問題の条件を満たす数字をカウントする変数
$count = 0;

// ①2から10000までの偶数をループさせて初期値を設定する
for ($initial_number = 2; $initial_number <= 10000; $initial_number += 2) {
// ②初期値に3をかけて1を足す処理
$original = $initial_number*3+1;
// ③$originalが初期値に戻るか、1になるかするまでループさせる
while ($original !== $initial_number && $original !== 1) {
// ④偶数、奇数の場合で処理を分ける
if ($original%2 === 0) {
$original = $original/2;
} else {
$original = $original*3+1;
}

// ⑤$originalが$initial_numberと一致すれば$countに1を足す
if ($original === $initial_number) {
$count = $count + 1;
}
}
}

// ⑥結果を出力する
echo $count;

// 結果
34



今回の学び

・ループ文の使い分け。今まではforeach80%、for20%のくらいの割合で使用していたがwhileが使いやすい場面もある。

・for文の第3引数の設定で、どのくらいの間隔でループ処理するか柔軟に変えられる。