145. 十亿内的可翻转数(How many reversible numbers are there below one-billion?)

一些正整数\(n\)具有如下性质:数\(n\)和它的翻转数\(reverse(n)\)之和用十进制表示,各位数都是奇数。比如\(36+63=69\)以及\(409+904=1313\)。我们把这种数字称为可翻转的,因此36、63、409和904是可翻转的。注意\(n\)\(reverse(n)\)的首位都不能是零。

易知一千以内有120个可翻转数,求十亿\((10^9)\)以内的可翻转数的个数。

分析:这道题很容易想到一个简单的暴力解法:编写一个判断某数是否是可翻转数的函数,然后遍历十亿以内的数字,统计可翻转数的个数就可以了。但是因为本题的数据规模较大,这个简单的暴力解法很难在一分钟时间内得到答案,所以我们需要一个更聪明的办法。问题的关键在于我们需要分析一下某数成为可翻转数,它的各位数需要满足那些性质。我们需要对十亿以内也就是九位数以内的数字逐一进行分析。因为一位数和它的翻转数的和是它自身的两倍,必定是一个偶数,不可能成为一个可翻转数,所以一位数可以全部排除。因此,对于两位数及以上的数,我们分为三种情况讨论:

一、数位为偶数(包括二、四,六、八)

我们先来看两位数,设其形式为\('ab'\),则其翻转为\('ba'\),则对各位的数的取值分析可见下表:

img

表格的前两行为两位数及其翻转的表示,第三行为对应数位之和取值范围,如果大于十则表示需要进一位,否则不需要进位。如果\(b+a>10\),则其会进一位导致\(a+b\)为偶数,不满足可翻转数的条件,所以数对\((a,b)\)之和必须要小于十。其次,两者之和都必须为奇数。第三,两者都不能为零,否则会导致首位数为零。综合三个条件,我们可以发现符合要求的数对共有二十个。

再来看四位数,设其形式为\('abcd'\),则其翻转为\('dcba'\),分析结果如下:

img

如果我们假设\((b,c)\)数对之和大于十,则会导致首位数\(a+d\)进一位,则\((a,d)\)本身的和应为偶数,但这会导致最后一位数也为偶数,不符合要求,所以\((b,c)\)数对之和必须小于十。同时\((a,d)\)数对之和也必须小于十,否则\(d+a\)进一位让\(c+b\)变为偶数。所以结果如表所示,\((a,d)\)数对有20个选择,\((b,c)\)数对有30个选择,所以总共有600个选择。

同样的道理,六位数和八位数也必须满足四位数的条件,即各个数对之和小于十且为奇数,首末两个数对中的数不能为零。因此六位数的选择数为\(20*30^2\),而八位数的选择为\(20*30^3\)个。

二、数位为\(4n+1\)型(包括一、五、九)

一位数前面已经说了,不可能包括可翻转数。看一下五位数,设其形式为\('abcde'\),则其翻转为\('edcba'\),分析结论如下:

img

在五位数中,最中间那位数会和自身相加,所以结果必然为一个偶数。为了避免它为偶数,则\(d+b\)必须大于十且为奇数,也就是说\(b+d>10\)且为奇数。为了\(a+e\)在进位后仍为奇数,所以\(a+e\)必须为偶数,所以最后一位数\(e+a\)也必须为偶数。因此不存在满足条件的数,所以在五位数情况下不会有可翻转数。

九位数的情况也是一样的,如下:

img

所以在九位数的情况下也不存在可翻转数。

三、数位为\(4n+3\)型(包括三、七)

首先来看三位数,设其形式为\('abc'\),则其翻转为\('cba'\),分析结论如下:

img

显然,三位数的最中间那位数会和自身相加,所以必然为一个偶数,为了避免出现偶数,最后一位数\(c+a\)必须要大于十同时为奇数,因此\(a+c\)也必须要大于十且为奇数。同时最中间的数\(2b\)必须要小于十以防止进一位导致\(a+c\)变成偶数。因此\(b\)有五个选择,同时\((a,c)\)数对有20个选择,所以在三位数时总共有100个选择。

再来看七位数,设其形式为\('abcdefg'\),则其翻转为\('gfedcba'\),分析结论如下:

img

同理,\(d\)作为最中间的数,其和必为偶数,所以\(e+c\)必须大于十且为奇数,则\(c+e\)大于十且为奇数。为使得\(b+f\)在进一位后仍为奇数,则\(b+f\)本身必为偶数,因此\(f+b\)为偶数且必须小于十,否则会导致\(e+c\)进一位变成偶数。因此\(g+a\)必须要大于十且为奇数,从而\(a+g\)也大于十且为奇数。综合以上条件,\((a,g)\)数对有20个选择,\((b,f)\)数对为25个选择,\((c,e)\)数对有20个选择,最后\(d\)有五个选择,故七位数情况下共有\(20*25*20*5=50000\)个选择。

四、结论

综合以上分析中总结出的模式,设数位为\(d\)位,则我们得到以下结论:

根据这个结论,我们只需要编写一个简单的代码就可以得到最终结果:

# time cost = 4.89 µs ± 19 ns

def reversible_numbers(d):
    r = d % 4
    if r == 0 or r == 2:
        return 20*30**(d//2-1)
    elif r == 3:
        return 100*(500)**((d-3)//4)
    else:
        return 0

def main():
    ans = sum([reversible_numbers(x) for x in range(2,10)])
    return ans