一个n位十进制正整数，如果把它的最低位上的数提至最高位后就变成了原来的两倍，那么这个数是多少

---

分析：

• 记这个n位十进制数为x，其各个位上的数为a_i(i∈[0,n-1],a₀表示个位上的数，a_n-1表示最高位上的数)，则有：

  $$x=\overbrace{\underline{a_{n-1}a_{n-2}a_{n-3}...a_2a_1a_0}}^{\text{共$n$位数}}=\sum_{i=0}^{n-1}a_i*10^i \tag{1}$$

• 将交换最低位和最高位上的数后得到的新的数记为x'，则有：

  $$x^’=\overbrace{\underline{a_0a_{n-1}a_{n-2}...a_3a_2a_1}}^{\text{共$n$位数}}=\sum_{i=1}^{n-1}a_i*10^{i-1}+a_0*10^{n-1} \tag{2}$$

• 根据题目要求，我们有

  $$x^’=2*x \tag{3}$$

• 观察公式(1)(2)，不难发现x和x^’之间存在某种联系，具体来说，x的高n-1位和x^’的低n-1位是相同的，x的最低位和x^’的最高位是相同的（这是题目最初给出的条件）。这样，我们就能给出x和x^’之间的对应关系：

$$x^’=x//10+x\%10*10^{[lgx]} \tag{4}$$

编写代码：

• 既然我们已经知道所需要的数的数学特征了，那么秉持简洁且易于代码实现的想法，自然应该首先考虑遍历所有自然数直到找到我们需要的

• 算法设计：
  程序的总体思想：对于每一个x，我们设法计算出其对应的x^’，并通过公式(3)验证该x是否是所需要的

  • Step1: 定义变量num并初始化，此变量对应公式(1)中的x；
  • Step2: 定义变量num_，此变量对应公式(2)中的x^’
  • Step3: 利用公式(4)计算出num_(num_=generateNewNum^[1] (num))
  • Step4: num_==2*num ? 打印该数字 : num++并转到Step1

• 代码实现：

  • 代码实现的关键在于实现generateNewNum函数，generateNewNum的实现逻辑由公式(4)确定

  import math
  def generateNewNum(n):
      return n//10+n%10*10**math.floor(math.log10(n))

  完整的代码如下：

  import time
  import math
  
  num=11 #显然小于10的数不是我们所需要的
  def generateNewNum(n):
      return n//10+n%10*10**math.floor(log10(n))
  
  if __name__ == '__main__':
      start_time=time.time()
  
      while True:
          if generateNewNum(num) == 2 * num:
              break
          num += 1
  
      end_time = time.time()
  
      file=open('result.complete','w',encoding='utf-8')
      file.write(num.digits())
      file.write(f'\n{end_time-start_time}s')

  这段代码将搜索到的第一个符合要求的数和所耗时间一同写入名为result.complete的文件中。
  很好，代码写完了。但当运行时才会发现，我们写了一个几乎用不了的代码！

  • debug
    这个代码真的用不了吗？如用。（乐.jpg）
    为什么说几乎用不了呢？可以试着运行一下代码。

  Imporove

  为什么上面代码的运行这么耗费时间呢？
  从最初设计算法的流程中可以看到，我们的想法是遍历每一个从11开始的自然数，直到找到所需要的。
  这段逻辑看起来十分简单且易于算法实现，但仔细一想，如果我们要找的这个数特别特别地大呢？程序将从11开始一直循环成千上万上亿上十亿次，直到找到所需的数。因此这段代码的搜索效率并不高。
  那么改进的关键就在于，如何缩小搜索范围。
  让我们看回公式(3)：

  $$x^’=2*x \tag{3}$$

  显然，x^’是一个偶数，那必然有a₁∈{0,2,4,6,8}。这样，我们就把x^’的范围给缩小了。但是，我们已经写好了的代码是对x进行搜索的，如何将对x^’的范围限制用到x上？
  解决的办法很简单，只需要在运行generateNewNum函数之前检测一下输入的数的十位是不是个偶数：

  while True:
    if (num//10)%2==0:
      if generateNewNum(num) == 2 * num:
          break
    num += 1

  这段代码额外添加了一个if语句来减少generateNewNum函数计算的次数，但和原始代码比起来，似乎代码运行的过程仅仅减少的是乘法、幂、取整、对数运算，代码把这些运算转为了判断跳转语句。显然后者比前者更高效。但是修改后的代码它的搜索范围仍然没有减少，减少的只是generateNewNum函数的计算次数，尽管将计算语句变为if语句就已经把计算量减少了许多了。

  Improve of improve（别管语法了，你懂意思就好了）

  既然我们已经缩小了x^’的搜索范围了，那为什么不去搜索x^’呢？
  根据公式(4)，从理论上，我们可以得到一个x^’关于x的函数，但(4)看起来实在是不太友善。那回到最初得到的式子，公式(1)和公式(2)。通过这两个公式，我们可以轻松地得到下式：

  $$x=(x^’\%(10^{[lgx^’]})*10+x^’//10^{[lgx^’]}) \tag{5}$$

  根据公式(5)和x^’是偶数的条件，我们可以重写代码，将遍历的搜索量减小一半。

Improve in another way

尽管我们已经将搜索量减小了一半，但是似乎加速效果并不明显(还没试过，服务器还在跑使用C++重构的Improve之前的代码)。在这一段中，我们将改变方法以使得计算机能快速解决这个问题。

• 将公式(1)的第二个等号后式子调整为与公式(2)相同的形式:

$$x=\sum_{i=0}^{n-1}a_i*10^i=\sum_{i=1}^{n-1}a_i*10^i+a_0 \tag{6}$$

此时可以发现，(2)和(6)形式上高度相似：

$$x^’=\overbrace{\underline{a_0a_{n-1}a_{n-2}...a_3a_2a_1}}^{\text{共$n$位数}}=\sum_{i=1}^{n-1}a_i*10^{i-1}+a_0*10^{n-1} \tag{2}$$

$$x=\sum_{i=0}^{n-1}a_i*10^i=\sum_{i=1}^{n-1}a_i*10^i+a_0 \tag{6}$$

观察可得，(2)和(3)的求和部分正好差了10倍，因此对(2)做如下变换：

$$10x^’=10*(\sum_{i=1}^{n-1}a_i*10^{i-1}+a_0*10^{n-1})=\sum_{i=1}^{n-1}a_i*10^i+a_0*10^n \tag{7}$$

将(3)带入(7)可得：

$$10x^’=20x=10*(\sum_{i=1}^{n-1}a_i*10^{i-1}+a_0*10^{n-1})=\sum_{i=1}^{n-1}a_i*10^i+a_0*10^n \tag{8}$$

此时，(6)和(8)的累加和部分完全一致，故二式做差消去累加和，可得：

$$(8)-(6)=19x=a_0*10^n-a_0=a_0(10^n-1) \tag{9}$$

现在，我们继续对公式(9)进行变形:

$$x=\frac{a_0(10^n-1)}{19} \tag{9}$$

回想我们最初得到的条件：a₀∈[0,9]，同时19是一个质数，因而a₀(10ⁿ-1)必然是19的倍数。（不考虑a₀=0的情况，因为这时x=0）
那么新的算法流程就清晰了起来：
- Step1: 定义变量n，初始化为11
- Step2: 检验a₀(10ⁿ-1)是否是19的倍数，若是，转到Step4，否则转到Step3
- Step3: n+=1,转到Step2
- Step4: 遍历每一个a的取值，根据公式(9)计算x，检查x的位数是否和n一致，若一致输出，否则在遍历结束后跳转到Step3

• 参考代码:

import math
import sys

n = 1
while True:
    num = 10**n - 1
    tail = num % 19
    if tail == 0:
        for a in range(1, 10):
            x = a*num//19
            if n == math.floor(math.log10(x)) + 1:
                print(x)
                sys.exit(0)
    n += 1

这段代码能够迅速计算出题目需要的数字，算出来的最小的数字为105263157894736842。你也可以将sys.exit(0)这段代码注释掉以搜索更多的符合条件的数字。当你这么做的时候，建议使用gmpy2.mpz来代替Python自己的高精度以提高计算效率。

至此，问题已被解决。

1. 这是一个自定义的函数，用于将x转换成x^’ ↩