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

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

[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的文件

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

转载于知乎,原帖地址

答案是:能!

严格的表述是这样的:

定理 [公式] :对于由 [公式] 组成的任意有限序列 [公式] ,存在自然数 [公式] 使得 [公式] 的十进制表示包含序列 [公式]

比如 [公式] =“ [公式] ”,取 [公式] ,此时:

[公式]

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

定理 [公式] :在十进制表示下,对任意的正整数 [公式] ,存在自然数 [公式] 使得 [公式][公式] 的各位数开头。

比如 [公式] ,取 [公式] ,有 [公式][公式] 开头。

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

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

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

定义 [公式] 为取 [公式] 的小数部分,比如 [公式][公式] ,取[公式] 式各项的小数部分可得: [公式]

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

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

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

再回到开头,要使 [公式] 的十进制表示开头出现 [公式] ,最起码必要求 [公式] 出发不断地加 [公式] ,根据上一段的讨论,必会有某个 [公式] 使得 [公式] 进入区间 [公式] 内,亦即这个 [公式] 满足 [公式] 式。

此时,根据 [公式] 式逆向推导,因为取的是以 [公式] 为底的对数,取小数部分而省去的整数如果补回来后也不过相当于乘以 [公式] 的幂,所以最后 [公式] 的十进制表示的开头就是 [公式] 了。定理 [公式] 证毕。

如果仔细分析就会发现,这个定理之所以成立,很大程度取决于 [公式] 是无理数,而非 [公式] 次幂或者十进制的特殊性。所以,把证明方法稍微改一下,就可以证明:

定理 [公式] :如果 [公式] 为无理数,在 [公式] ,存在自然数 [公式] 使得 [公式][公式] 的各位数开头。

同样有相应形式的定理 [公式]


转载于知乎,原帖地址

Related posts

【Python学习实验室】Python实现路由器的重启和查看实时流量

最近因为要使用一个可以插卡上网的4G路由器,但是不知道怎么回事,这个路由器总是在一个随机的时刻无法访问互联网(SIM卡是没有问题的),就是那种在网上刷着视频听着音乐看着直播突然就没有互联网的感觉,就非常非常的让人不舒服。

Latest posts

【科技小知识】如何在2021年使用flash player ?并且如何替代它?

Flash Player作为一款已经过时的软件已经陪我们走过太多太多,包括传统的Flash 游戏,Flash视频播放器都是Flash时代的一大佳作,可惜这个昔日王者终有一天坠落的一天,今天这个文章就来告诉你如何在2021年使用Flash Player,或者是使用其他的方法来替代他。

【Python学习实验室】Python实现路由器的重启和查看实时流量

最近因为要使用一个可以插卡上网的4G路由器,但是不知道怎么回事,这个路由器总是在一个随机的时刻无法访问互联网(SIM卡是没有问题的),就是那种在网上刷着视频听着音乐看着直播突然就没有互联网的感觉,就非常非常的让人不舒服。