奇怪的六位数大全

· · 个人记录

（持续更新中……）

众所周知，银行的动态口令生成器每分钟会生成一个随机的、含有前导零的六位数，000000至999999。我就有一个过期的动态口令生成器。虽然已经过期，但它还是会继续生成新的随机数。于是，一种消磨时间的新方法便诞生了……

有时候，这个生成器会生成一些比较令人满意的六位数，比如345678。但是，大多数时候，它生成的都是像925216这样平平无奇的数。一个六位数，到底能有那些奇特的性质？最稀有的六位数性质是什么呢？下面，我们就来看一看各种数六位数的性质的“稀有度”。

在圆周率的小数展开中出现：1000000个

计算难度：0/10（指手算）

没错，所有的六位数（以下若不做特殊说明，均为可含有前导零的六位数）都会在圆周率中出现。圆周率是一个无理数，它的小数展开每一位都是随机、均匀分布的，因此任何数字串迟早都会在圆周率中出现。就算是很特殊的999999，也出现在了圆周率小数展开后的762至767位。

含有2的幂：953356个

计算难度：3/10

没想到吧，居然有这么多！在这里，含有2的幂指有某一个子串为2的幂，例如214748（1、2、4、8是2的幂）或者765536（65536是2的幂）。如何算出这个值呢？首先，注意到，所有不超过一百万的2的幂除了65536外，均含有1、2、4或8。因此，先计算含有1、2、4或8的六位数个数：不含有这些数位的数每一位只能有6种选择，一共有六位，因此有46656个；那么含有1、2、4或8的数就有953344个。再加上含有65536且不含1、2、4或8的数：655360、655363、655365、655366、655367、655369、065536、365536、565536、665536、765536、965536共12个。于是，总共就有953356个含有2的幂的数。

是一个质数：78498个

计算难度：9/10

好吧，要想得到这个答案，不借助网络和计算机恐怕是不能手算了。目前为止，求出n以内所有质数的最快方法（复杂度最低）是运用线性筛，复杂度为O(n)，但是，你还需要一个列数为1000000的表格才行……

相邻两位组成的两位数全部是质数：1138个

计算难度：5/10

071973、173797和897119都是拥有此性质的数。计算这个答案需要一些图论知识。

把每个数字看成一个点，如果\overline{ab}是质数，那么从a到b连一条有向边。注意这张图可能有自环。最终，连出的图看起来像是这样：

G(E,V)=

由于绘图编辑器不支持自环，1其实有一条边指向1自身。

现在，我们只需要求出点数为6的可以重复的路径条数。于是，轮到大名鼎鼎的“标数法”上场了：

定义f(i,k)表示以i结尾的、长度为k的路径条数。则我们有如下的递推公式：

f(i,k)=\sum_{(j,i)\in E}f(j,k-1)

这相当容易理解：要想长度为k的路径以i结尾，就必须要有一条长度为k-1的路径以一个能到达i的点为结尾，二者一一对应。显然，f(i,1)=1。因此，我们能求出所有的f(i,k)。形象一点，就是在每个点上标一个数表示方法数，每一轮用上一轮的数更新这一轮每个点的值。例如，在每一轮中，用上一轮1、3、4、6、7的值之和作为本轮节点1的值。最终答案就是\sum_{i\in[0,9]\cap\mathbb{Z}}f(i,6)。

hk变换的值是自身加1：2个

计算难度：8/10

不得不说一下hk变换。狭义hk变换将所有正整数映射到正整数集，方法为：对于一个数n\ge2，可将n写成p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}的形式，其中p_{1}至p_{k}为互不相同的质数，且p_{1}<p_{2}<\cdots<p_{k}，\alpha_{1},\alpha_{2},\cdots,\alpha_{k}>1均为正整数（算数基本定理）。将p_{1}至p_{k}依次写下组成一个新数y，则称x的hk变换为y，记作hk(x)=y。特别地，hk(1)=1。例如，hk(521)=521，hk(925)=537，hk(2926)=271119，hk(4294967296)=2。

可以发现，hk变换的结果忽上忽下，难以寻找规律。这就是满足hk(x)=x+1的数x只有2个的某种解释。你能找到这两个数吗？

先公布一下答案，这两个数分别为022856和025640。如何找到它们呢？

不难发现，$hk(x)$只能以1、2、3、5、7或9结尾。如果$hk(x)$以2结尾，那么$x$只能是2的幂（因为较小的质因子会被排在前面）且$hk(x)$=2。这意味着$x=1$。然而，$hk(1)=1\ne2$。如果$hk(x)$以5结尾，类似地可以得到$hk(x)\in \{5,25,35,235\}$。一一验证可得它们都不满足条件。因此，$hk(x)$以1、3、7或9结尾。从而，$x$是偶数。这说明$hk(x)$以2开头。 接下来，我们似乎也无法再得到更多的信息了，因此直接分类讨论。 第一类：$hk(x)$有6位。我们设$x$的最大质因子为$p$，则$hk(x)$必然表示为$\overline{2?p}$的形式，一共有6位。 $p$只有1位是不可能的，因为1位质数只有4个。 若$p$有2位，设$hk(x)$前面的$\overline{2?}$为$a$，则必然有$100a+p=kp+1$，其中$k$为正整数（$100a+p$即为$hk(x)$，$kp$为$x$）。因此，$100a-1=(k-1)p$，并且$k$的值受到前面$a$的值的限制。 由假设，得知$a$有3位。若$a$是由3个1位质数组成的，则只能有$a=357$，从而$(k-1)p=35699$，且$k$的所有质因子恰好为$\{2,3,5,7\}$。$35699=29\times1231$，故$p=29$。而此时$k=1232$不含有因数5，不满足条件。 若$a$是由1个1位质数和1个2位质数组成的，则一共有63种情况，规模不大，用类似的方法一一验证后可以发现全部无解。故$p$有2位时无解。 若$p$有更多的位数，经过作者试验，$a$的组合方案一共有28种。同样地，一一验证后也可以发现全部无解。至此，我们说明了$hk(x)$不可能有6位。坚持就是胜利！ 若$hk(x)$有5位，此时情况就变得简单多了，$a$的组合方案也降低到了28种（6位是92种）。其中，我们在$p$有3位、$a=25$时发现了解：此时$(k-1)p=24999=39\times641$，而40恰好有2和5两个质因数！真是如此巧合！于是，我们到了一个解：$x=25640$（注意要减1）。类似地，在$p$有4位、$a=2$时也有一个解22856. 若$hk(x)$的位数小于5，这时$a$一共只有9种情况，很容易就能一一验证无解了。先考虑最复杂的类别（$hk(x)$6位）真是一个明智的选择啊！ 于是，这个问题就做完了。总共只讨论了129种情况，如果你是一个有耐心的人，一定能做到考虑周全（这花不了半个小时）。但是这题仍然有一些降低类数的技巧：先分析$hk(x)$的奇偶性，确定能确定的位；然后利用正整数的性质列出方程，巧妙地省去了讨论$p$的过程而化为解方程，这大大降低了需要讨论的类数。