$3^{13}=1594323$并不是太大的数字，因此本题的基本思想是考察从1到n的所有数字的拼接字符串中出现了几次n，然后在n前面添加数位来获得其第n次出现的位置。
这是因为数字n可以提前出现在两个数字的拼接中，例如$3^5=243$可以出现在数字42和43的拼接中。
此处的实现十分繁琐，以下代码改编自官网论坛，代码的逻辑和注释都比较清晰，不言自明。
最终结果是$18174995535140$。
注：以下为Python 3代码，代码中打印了进度信息。
r=0
for p in range(1,14):
x=3**p
sx=str(x)
nums=set()
d=len(sx)
offset=0
# 1. All x in y1y2 with y1 shorter than x (e.g. 243 in 42, 43)
for i in range(1,d//2+1):
y=int(sx[:i])
sy=str(y+1)
if sy==sx[d-len(sy):]:
offset+=1
# 2. All rotations of x
for i in range(d):
s=sx[i:]+sx[:i]
if s[0]!='0':
nums.add(int(s))
# 3. All ___x___ and all x2___x1 ('x1x2' = 'x')
k,p10=1,10
while len(nums)+offset < x:
offset+=len(nums)
nums=set()
for y in range(p10):
sy=str(y).rjust(k,'0')
for i in range(1,k+1):
s=sy[:i]+sx+sy[i:]
if s[0]!='0':
nums.add(int(s))
for i in range(d):
s=sx[i:]+sy+sx[:i]
if s[0]!='0':
nums.add(int(s))
k+=1
p10*=10
# 4. Sort nums and get n=x-th number
nums=sorted(nums)
n=nums[x-1-offset]
# 5. Count digits before n
s=str(n)
d=len(s)
k=p10=1
pos=0
while k < d:
pos+=9*k*p10
k+=1
p10*=10
pos+=k*(n-p10)
# 6. Adjust for position in n, n+1
s+=str(n+1)
pos+=s.index(sx)+1
print(p,pos)
r+=pos
print(r)
|
