JavaScriptを使ってn回の操作後に開いている水道の蛇口の数を求める方法

問題

ある学校の創立記念日の行事で、次のようなゲームが行われたとします−

「n」個の水道の蛇口があり、「n」人の生徒が無作為に選ばれます。先生は最初の生徒に、すべての蛇口へ行って開けるよう指示します。続いて2番目の生徒には、2番目ごとの蛇口を閉めさせます。3番目の生徒は、3番目ごとの蛇口に対して、閉まっていれば開け、開いていれば閉めます。4番目の生徒も同様に、4番目ごとの蛇口に対して同じ操作を行います。この操作をn番目の生徒まで終えたとき、何個の蛇口が開いていることになるでしょうか。

ここで求められているのは、数値 n を受け取り、開いている蛇口の数を返す JavaScript 関数を作成することです。

考え方

i 番目の蛇口が開けられたり閉められたりする回数は、i の約数の個数と一致します。たいていの数は約数が偶数個あるため、最終的には閉じた状態に戻ります。ところが完全平方数だけは例外で、約数が奇数個（例：9 の約数は 1・3・9 の3つ）存在するため、奇数回の操作を経ても最後まで開いたままになります。

したがって、開いている蛇口の数は「n 以下の完全平方数の個数」、すなわち ⌊√n⌋ に等しいことが分かります。これにより、全員の操作を実際にシミュレーションしなくても、O(√n) で効率的に答えを求められます。

例

以下がそのコードです−

const num = 15;
const openTaps = (num = 1) => {
   const arr = [];
   let index = 1;
   while(index ** 2 <= num){
      arr.push(index++ ** 2);
   };
   return arr.length;
};
console.log(openTaps(num));

出力

3

num = 15 の場合、15 以下の完全平方数は 1・4・9 の3つだけなので、開いたまま残る蛇口は3個となります。コードは n 以下の完全平方数を順に配列へ格納し、その個数を返すことでこの数学的な性質をシンプルに利用しています。