关于一道小学题的完整证明

原贴：https://api.xiaoheihe.cn/v3/bbs/app/api/web/share?link_id=d4b670b7ed40 

今天刷到这个题，想构造一下，没忍住就写了一下构造过程证明，结果没想到黑盒评论区太长的放不下，遂单开一贴写一写具体如何找到满足这种要求的值。

考虑如何在64位整型暴力枚举这种值，已经有人给出了1e16量级的数，而64位无符号整型的量级位1e20左右，如果仅仅暴力枚举，普通家用CPU147k全核跑满也得跑两千多年，若写cuda让GPU来跑，普通家用GPU4090得跑六十多年，相对快一点，但依旧不现实。

记数x的数位和为sum(x)，我们小学学过，一个数与其数位和模9同余，即x≡sum(x)mod9，我们记小数为x、差值为d，则有2x+d≡6mod9，解得x≡5(6-d)mod9，我们其实已经知道d最小值为2，则x≡2mod9，这样枚举起来就可以九个一枚举，搜索空间一下就缩小了不少，4090只需要跑几年就能跑完了。

注意到，如果x+d只有个位数与x不同，显然不可能满足两者的数位和均为11的倍数的情况（因为此时两者的数位和差值也为d），因此加d后必然进位，以这里的2为例，能够进位的小数的个位数只有8与9，对应大数的个位数为0与1，其中小数个位数为8的情况显然不成立，因为此时个位数的值就已经为8，显然不可能满足两者和的数位和为6的条件，因此小数的个位数必然为9，即x≡9mod10，再结合前面的x≡2mod9，由中国剩余定理可以得到x≡29mod90，这样我们的搜索空间又缩小了十倍，单卡4090仅仅只需要跑几个月就能跑完！

接着我们来讨论十位的情况，前面我们已经知道x+d会导致十位加1，同时x的个位数为9、x+d的个位数为1，我们记x的十位数为a，若十位加这个1之后不会出现进位，即a+1<10，则两者的数位和的差则为(a+9)-(a+1+1)=7，数位和差7，不可能数位和均为11的倍数，因此十位也必然进位，a只能为9，即x的后两位只能为99，x+2为01，即x≡99mod100，再次可以缩小十倍范围。

同样地，我们可以讨论百位是否进位，x的百位记为a，若不进位，则数位差为(a+9+9)-(a+1+0+1)=16，具有这样差值的二者显然也不会均为11的倍数，因此x的百位依旧为9，即x≡999mod1000，再次缩小了十倍范围。

更一般地，我们可以讨论加上这个2之后从个位起有k位都会进位，记第k+1位为a，那么小数的低k位均为9、大数的低k位由k-1个0与1个1组成，两者的数位差则为(a+9k)-(a+1+1)=9k-2，要使两者的数位和均为11的倍数，因此有9k-2为11的倍数，即9k-2≡0mod11，求解可得k≡10mod11，即x的末尾的9的个数可能为10个、21个、32个……如果仅仅只是想在64位整型中寻找答案，那么就已经缩小了相当的数量级，即便是CPU跑，用时也已经从两千多年缩减到了几秒钟，到这一步就已经可以考虑暴力求解了。

但是都到这一步了，仅仅暴力枚举显然已经无法满足我们的欲望，实际我们可以进一步探讨。前面我们已经发现x的末k位为9，其中k≡10mod11，因此x可以表示为H*10^k-1，x+2则为H*10^k+1，两者的数位和为11的倍数，即为：

sum(H)+1≡0mod11，sum(H)≡10mod11，又由H最初始的定义（H-1加一后只改变个位）我们可以得到，sum(H-1)=sum(H)-1，因此sum(H-1)+1≡10mod11，得到sum(H-1)≡9mod11，即x的高位的数位和与9模11同余。

另外，由于两数之和的数位和为6，两数又分别为H*10^k-1与H*10^k+1，因此sum(2H)=6，这意味着2H的每位数必然小于等于6，这里我们记满足sum(2N)=n的数N的数位组成集合为S(n)，我们现在来讨论S(6)，2H只能由0-6这七个数组成，对应H的位数为0、1、2、3、5、6、7、8，其中当H的某位数为8时，该位对sum(2H)的贡献为1+6=7，已经超过了6，因此8排除；当H的某位数为7时，该位对sum(2H)的贡献为1+4=5，其他位的贡献只能为1，因此其他非位只能为5，因此sum(H)=5+7=12，与前面我们推出的sum(H)≡10mod11相悖，因此7也排除；类似地，当H的某位为3时，该位直接为sum(2H)贡献6，因此没有其他非零位，此时sum(H)=3，排除；当某位为2时，其他位的贡献为2，H的其他位只能为0、1、5，准确说只能是一个1或者两个5，对应的sum(H)分别为3和12，因此2排除；当H的某位为6时，该位贡献了3，其他位贡献3，因此H的其他位只可能为0、1、5、6，其中若其他某位为6，就不会有其他非零位，此时的sum(H)为12，此处排除，其他位出现1的话就需要再补一个5，此时的sum(H)为12，排除，其他位此时只可能为5，若出现5就只能为3个5，此时sum(H)为21，暂时合法；若H某位为1，其他位的贡献则为4，其他位只能为0、1、2、5、6、7，类似的讨论可以排除7、6、2、1，若为5只能为四个5；剩下只剩全5的组合，即六个5，此时sum(H)为30，也可以排除。综上所述，H（注意这个H是x+2的高位而非x的高位）只可能由一个1与四个5、或一个6与三个5构成，中间可由若干零填充，但由H的初始定义，H的末尾不能为0。

更一般地，我们可以发现，sum(2N)=2sum(N)-9c，其中c为2*N时的进位次数，因此2sum(H)-9c=6，sum(H)=3+9c/2（这个/表示普通除法），显然由于sum(H)为整数，c应当为偶数，令c=2t，则sum(H)=3+9t，又sum(H)≡10mod11，故9t+3≡10mod11，t≡2mod11；记t=2+11m，c=4+22m，sum(H)=21+99m，当m=0时，c=4、sum(H)=21，有四个会产生进位（即大于4）的数、若干个数总和为21，我们发现5*4=20，因此只可能为四个5与一个1或者三个5与一个6的组合，与前面我们的结论吻合；而对于m大于0的情况，相当于sum(H)平均每新增9，就要增添两个进位的数字，但这两个数之和至少为10，因此m只能为0，同样与前面我们的结论相符。

至此我们就完全掌握了这类数（数位和均为11的倍数、和的数位和为6、差值为2）的构造规律，即H*10^k+1与H*10^k-1，其中k≡10mod11、H由末尾不为0的由三个5一个六或四个5一个1以及若干零组成，比如显然可以写出满足要求最小的数字为55560000000001与55559999999999。