知恵袋で見つけた「自然数を順番に並べた数」の問題をPythonで解いてみた。

　知恵袋で見つけた「自然数を順番に並べた数」の問題をPythonで解いてみました。

全ての自然数を順番に並べて書いたとする。（下のように）
123456789101112131415161718192021・・・
このように並べると、例えば、10番目の数字は1であり、32番目の数字は2である。
では、100万番目の数字は何でしょうか？

　まず、1から始まる次のように段になった群数列を考えます。元になる整数ごとに、群に分け、さらにその群を桁数ごとに段に分けます。

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 0 | 1 1 | 1 2 | ... | 9 9 |
| 1 0 0 | 1 0 1 | 1 0 2 | ... | 9 9 9 |
| 1 0 0 0 | 1 0 0 1 | 1 0 0 2 | ...| 9 9 9 9 |
| 1 0 0 0 0 | 1 0 0 0 1 | 1 0 0 0 2 | ...| 9 9 9 9 9 |
...

　1段目は9個、2段目は90個、3段目は900個…で、第ｎ段の群数は個であり、第ｎ段の群はどれもｎ個の項を含んでいるので、第ｎ段の末項までの項数は、
　
これを使えば、前からn番目の数(項)が第何段にある(属する)かを調べることができます。
　また、属する段で第何群目かを調べて、前からn番目の項が前から通して第何群にあるのかとその群の末項までの項数が分かると題意の「ｎ番目の数字」を求めることができます。
　次に、検算用の別解を検索していたら、オンライン整数列大事典でいいのを見つけました。それによると、チャンパーノウン定数に関連があるようです。ここに出ている下の式をちょっと変形して、整数だけで計算できるように、Ceil2(x,y)関数を作って、検算用の関数を作りました。

　mod(floor(10^(mod(n+(10^i-10)/9,i)-i+1)*ceiling((9*n+10^i-1.0)/(9*i)-1)),10)

　ちなみに、検算用の方がちょっと速いようです。(^_^;

● Champernowne2.py

# coding: UTF-8
# Champernowne2.py

from time import time
from math import log10

# 第n段の末項までの項数を求める
def kosDanLst(n):
    return n*10**n+(1-10**n)//9

# 前からn番目の項が第何段に属するか求める
def getDan(n):
    if n<=1: return 1
    #j=log10(n); i=int(j-log10(j))+1
    i=int(log10(n)-log10(log10(n)))+1
    while kosDanLst(i)< n:
         i+=1
    return i

# 前からn番目の項が前から第何群にあるか調べてその群の末項までの項数を求める
def getGunAndKosGunLst(n):
    k=getDan(n)
    j=kosDanLst(k-1)    # 第(k-1)段の末項までの項数
    i=Ceil2(n-j,k)      # 属する段で第何群目かを調べる
    return 10**(k-1)+i-1, j+k*i

# x の 10**n の位の数を取り出す
def getNum(x,n):
    return (x//10**n)%10

# n番目の数字(項)
def NthChampernowne(n):
    i,j=getGunAndKosGunLst(n)
    return getNum(i,j-n)

# 検算用
def NthChampernowne2(n):
    i=getDan(n) # 何段目にあるか調べる
    j=9*n+10**i-1
    return getNum(Ceil2(j,9*i)-1,i-1-(j//9-1)%i)

def Ceil2(x,y):
    return x//y if x % y==0 else x//y+1

def main():
    pass # code goes here
    tm=time()  # Timer Start
    s = t = ""
    for n in range(1,34):
        s+="%d "%NthChampernowne(n)
    print(s[:-1])
    for n in range(1,34):
        t+="%d "%NthChampernowne2(n)
    print(u"%s… 検算"%t)
    m = 1000000
    print(u"100万番目: %d"%NthChampernowne(m))
    print(u" 〃(検算): %d"%NthChampernowne2(m))
    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1
1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 … 検算
100万番目: 1
 〃(検算): 1
Runtime : 0.016 [sec]

※参考URL
http://mathworld.wolfram.com/ChampernowneConstant.html
●知恵袋で見つけた「自然数を順番に並べた数」の問題をJavaで解いてみた。

パーフェクトPython (PERFECT SERIES 5)