JavaScriptで範囲内の「1に収束する素数」を数える方法

問題概要

2つの数値からなる範囲配列を受け取るJavaScript関数を作成します。この関数は、範囲内にある素数のうち、各桁の数字の2乗の和を繰り返し計算すると最終的に1に到達する数の個数を返します。

たとえば23は素数であり、次のように計算が進みます。

22 + 32 = 13
12 + 32 = 10
12 + 02 = 1

最終的に1になったため、23は条件を満たす有効な数です。なお、この性質を持つ数は一般に「ハッピー数」と呼ばれ、素数であるハッピー数は「ハッピー素数」として知られています。

コード例

以下が実際のコードです −

const range = [2, 212];
String.prototype.reduce = Array.prototype.reduce;
const isPrime = (n) => {
   if ( n<2 ) return false;
   if ( n%2===0 ) return n===2;
   if ( n%3===0 ) return n===3;
   for ( let i=5; i*i<=n; i+=4 ) {
      if ( n%i===0 ) return false;
         i+=2;
      if ( n%i===0 ) return false;
   }
   return true;
}
const desiredSeq = (n) => {
   let t=[n];
   while ( t.indexOf(n)===t.length-1 && n!==1 )
   t.push(n=Number(String(n).reduce( (acc,v) => acc+v*v, 0 )));
   return n===1;
}
const countDesiredPrimes = ([a, b]) => {
   let res=0;
   for ( ; a<b; a++ )
      if ( isPrime(a) && desiredSeq(a) )
      res++;
   return res;
}
console.log(countDesiredPrimes(range));

コードの仕組み

isPrime関数：素数判定

引数の数が素数かどうかを判定します。2と3については個別に処理し、それ以降は5から始めて2と4を交互に加えながら試し割りを行うことで、不要な除算を省いた効率的な判定（6k±1方式の最適化）を実現しています。

desiredSeq関数：1への収束チェック

各桁の2乗の和を繰り返し計算し、その途中経過を配列tに記録していきます。同じ数が再び現れた時点（＝循環に入った時点）、または1に到達した時点でループを終了し、最終的な値が1であればtrueを返します。これにより、4→16→37…のような循環に陥ってしまう数を確実に除外できます。

なお、冒頭のString.prototype.reduce = Array.prototype.reduce;は、Arrayのreduceメソッドを文字列でも使えるよう拡張する記述です。これによって、数値を文字列化した各桁（各文字）に対して手軽に畳み込み計算が行えます。

countDesiredPrimes関数：集計処理

範囲[a, b)の各整数に対して、「素数であること」と「desiredSeqがtrueを返すこと」の両方を確認し、どちらも満たす数だけをカウントして結果として返します。

出力

12

この結果は、2以上212未満の範囲には12個のハッピー素数（7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193）が存在することを示しています。