【思维迷宫】2的n次方能包含所有十进制序列吗？（算法测试）

Worldcovert

5 年前

我为此自己写了一段代码进行测试

[python]
import time
def find(num):
    head = 0
    while True:
        if str(num) in str(2 ** head):
            return head
        head += 1
num = 0
f = open('test.txt','w')
for _ in range(0,599999):
    timestart = time.time()
    finalnum = find(num)
    finaltime = time.time()-timestart
    print("[",finaltime,"]",num,"in",finalnum,"with",2**finalnum)
    f.writelines(['\n',str(num)," in ",str(finalnum)," ",str(2**finalnum)])
    num += 1
[python]

用这个程序会遍历一遍从0~599999所有数字在2的n次方（从n=0开始，依次递增1查找，n ∈ N）第一次出现的情况

会生成一个文件大约358MB的文件

程序无法彻底证明这个东西，但是可以初步看到结果，为此特地转发一篇文章供大家查看。

转载于知乎，原帖地址

答案是：能！

严格的表述是这样的：

定理 ：对于由组成的任意有限序列，存在自然数使得的十进制表示包含序列。

比如 =“ ”，取，此时：

直接看定理，感觉证明起来必定很难，涉及到的幂的各个十进制位数，然而这不过是个小把戏，实际上定理只是一个更强的定理的一个推论，直接证明这个更强的定理，会简单很多。

定理：在十进制表示下，对任意的正整数，存在自然数使得以的各位数开头。

比如，取，有以开头。

如果序列不是以开头，那么可以把它看成是一个十进制正整数，应用定理即得定理成立；如果以开头，则不能简单看作十进制正整数，不过可以在开头添加，再使用定理就可以证明定理了。所以接下来要做的是证明定理。

如果定理确实成立，那么肯定存在自然数使得：也就是说，这不单是要寻找合适的，还要寻找合适的。不过，利用一些技巧可以避开这个的阻挠。注意到式是幂的形式，但是如果取一下对数呢？取对数是降级运算，可以将乘除变换为加减，问题就简单很多了。不过在取对数之前，先将表示成科学计数法的形式，例如。我们设，其中。这个时候式就成了：在不等式上取以为底的对数可得：

到了这里，还是出现啊，怎么就“避开这个的阻挠”了呢？别急，我们还差一步。如果我们在这个式子里边忽视掉整数部分：因为，那么，也有，并且是个很小的数，也就是和相差很少，且它们都不大于。如果我们只取式的小数部分，由于和相差的值很小，且都不大于，那么取了小数部分之后不等式还是成立的——只有一种特殊情况：当时，这个时候取小数部分的话就变成了，就会小于了，这个情况下我们仍保留这部分，就可以保证不等式成立。

定义为取的小数部分，比如，，取式各项的小数部分可得：

这时候终于摆脱了。现在我们也不用考虑的整数部分，对每一个自然数，都产生一个小数部分，也就相当于在区间上画一点。这么多个，肯定有某些点会出现在区间上吧？只要有某些点出现在这个区间上，的解就找到了。

下面的步骤就是一些技巧了。

取正整数，也就是，将区间 等分成个小区间，每个的长度都是。让取一共个自然数值，那么就会有个的值，根据鸽巢原理，这些值中最起码有两个处于同一个小区间，换言之，存在使得：但是，会不会等于呢？如果它等于，那么就是个整数，这和是无理数矛盾。所以。令，就得到。注意小于区间的长度，所以从任一个出发，不断地加，因为每加一次，小数部分就向前增一点点，并且增量小于区间的长度，所以必会使得小数部分进入区间内。