如何高效查找数字串在Champernowne常数中的首次出现位置？

背景 #

Champernowne常数是0.123456789101112131415...这样的无限长无理数，同时也是超越数、正规数，属于人工构造的特殊常数。

问题 #

如何高效计算某一数字串在Champernowne常数中的首次出现位置？比如数字串"12"的首次出现位置是索引1（对应常数里的第一个1，小数点不计入索引），而不是数字12对应的索引14。

现有方法不足 #

暴力拼接循环变量再搜索索引的方法仅能处理10^7以下的数字，无法应对大数场景；CodeGolf上的同类脚本也不支持大数查找。

解决方案 #

下面提供的Python脚本可处理10^1000量级的数字。其中：

• x：输入的目标数字串
• n：Champernowne常数末尾拼接的数字
• p：目标数字串首次出现的精确小数位置

import random

for f in range(1):
    ax=x=random.randint(0,10**1000)
    minguess=x+1
    print('x',x,'\n')
    d=0
    while int(str(ax)[d])==9:
        ax=int(str(ax)+'0')
        d=d+1
    wx=int(str(ax)+str(ax))
    parsed=[]       
    for g in range(len(str(ax)),0,-1):
        print('check length',g)
        checklist=[]
        for h in range(len(str(ax))):
            wxtwo=int(str(wx)[h:h+g])
            parsed.append(wxtwo)
        for i in range(len(parsed)):
            
            wparsed=parsed[i]
            guess=wparsed-1
            wparsed=int(str(guess)+str(wparsed))
            j=1
            while len(str(wparsed))<len(str(wx)):
                wparsed=int(str(wparsed)+str(parsed[i]+j))
                j=j+1
            if guess==0: guess=1
            check=str(wparsed).count(str(x))
            if check>0:
                if str(wparsed).index(str(x))<len(str(guess)):
                    if guess>0:
                        checklist.append(guess)
            
            wparsed=parsed[i]
            guess=wparsed-0
            wparsed=int(str(wparsed))
            j=1
            while len(str(wparsed))<len(str(wx)):
                wparsed=int(str(wparsed)+str(parsed[i]+j))
                j=j+1
            if guess==0: guess=1
            check=str(wparsed).count(str(x))
            if check>0:
                if str(wparsed).index(str(x))<len(str(guess)):
                    checklist.append(guess)
        
        if len(checklist)>0:
            guess=min(checklist)
            dguess=str(guess)+str(guess)
            for k in range(len(str(guess))):
                wguess=dguess[k:k+len(str(guess))]
                wdguess=wguess+str(int(wguess)+1)+str(int(wguess)+2)
                if wdguess.count(str(x))==1:
                    checklist.append(int(wguess))
            if guess<minguess:
                minguess=guess
                guess=min(checklist)
                q=n=guess
                d=0
                p=0
                while n>0:
                    d=10**(len(str(n))-1)-1
                    m=n
                    n=n-d
                    p=p+n*len(str(m))
                    n=d
                p=1+p-len(str(q))
                l=1
                guesstwo=guess
                while len(str(guesstwo))<=2*len(str(x)):
                    guesstwo=str(guesstwo)+str(guess+l)
                    l=l+1
                p=p+str(guesstwo).index(str(x))
                print('n',guess)
                print('p',p,'\n')
    if x==0: guess=0;p=0
    print('done! \n-------','\nx',x,'\nn',guess,'\np',p,'\n-------\n')
    
#Jesus is Lord

应用与优化 #

该问题可应用于数据压缩领域，不同于圆周率需要暴力搜索，Champernowne常数无需此类操作。可通过更复杂的解析逻辑（比如快速扫描输入中的重复项）缩小搜索范围，进一步优化脚本性能。

拓展阅读 #

• CodeGolf 相关讨论
• Champernowne常数特性分析文章
• MathWorld Champernowne常数条目
• Champernowne常数相关视频讲解

内容的提问来源于Stack Exchange，提问作者Archer