自然数列のn番目の数字を求めるJavaScript関数の実装方法

数学において、自然数とは1から始まり無限に続く数のことを指します。

最初の15個の自然数は以下のとおりです。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

この数列を先頭から1文字ずつ拾っていくと、1番目の数字は「1」、2番目は「2」、3番目は「3」……と続きます。ところが9を超えたあたりで挙動が変わります。10番目の数字は「10」の1桁目である「1」になり、11番目の数字はその次の「0」になるのです。

つまり本記事の課題は、数値 n を受け取り、このように並べた自然数列の n番目の数字 を見つけて返すJavaScript関数を作成することです。

コード例

const findNthDigit = (num = 1) => {
    let start = 1;
    let len = 1;
    let count = 9;
    while(num > len * count) {
        num -= len * count;
        len++; count *= 10;
        start *= 10;
    };
    start += Math.floor((num-1)/len);
    let s = String(start);
    return Number(s[(num-1) % len]);
};
console.log(findNthDigit(5));
console.log(findNthDigit(15));
console.log(findNthDigit(11));
console.log(findNthDigit(67));

出力結果

コンソールには次のように表示されます。

5
2
0
8

アルゴリズムの解説

一見すると単純な問題ですが、n が大きくなると全数列を文字列として生成して1文字ずつ数える方法では非効率です。そこでこのコードでは桁数ごとにグループ分けして考える手法を使っています。

各桁数に含まれる数字の個数

• 1桁の数（1〜9）: 9個 × 1桁 = 9文字
• 2桁の数（10〜99）: 90個 × 2桁 = 180文字
• 3桁の数（100〜999）: 900個 × 3桁 = 2700文字

変数 len（現在の桁数）、count（その桁数の数の個数）、start（その桁数の最初の数）を用意し、whileループの中で n が現在のグループの総文字数より大きい間、その文字数分だけ減算しながら次のグループへ進みます。これにより、n 番目の数字がどの桁数のグループに属するかを特定できます。

具体的な数字の特定

グループが決まったら、start += Math.floor((num-1)/len) によって、そのグループ内で何番目の数にあたるかを計算し、対象となる数そのものを求めます。最後に数値を文字列化し、(num-1) % len でその数の中の何桁目かを割り出して返しています。

たとえば findNthDigit(11) の場合、11番目の数字は「10」の2桁目なので 0 が返り、findNthDigit(67) は数列中67番目の位置にあるため 8 が返ります。このアルゴリズムなら、n が非常に大きな値でも高速に答えを求められます。